PrivFT: Private and Fast Text Classification with Homomorphic Encryption

• Kim Laine is listed with Microsoft Research.Source: I2R, A*STAR · p. 1

• Machine learning is used in high-stakes domains including healthcare, law, and finance.Source: §1 · p. 1
• Private data for these systems comes from individuals or institutions such as hospitals, financial institutions, and civil departments.Source: §1 · p. 1
• In-house model development and maintenance require dedicated ML and domain experts, adding cost as models become more complex.Source: §1 · p. 1

1.1 System Overview

• Inference uses a plaintext model in the cloud and returns an encrypted class prediction for client-side decryption; its runtime is reported as under 0.66 seconds.Source: §1.1 · p. 2
• Training operates entirely in ciphertext space using backpropagation, but is substantially more computationally demanding than inference.The encrypted model is returned to the client for decryption and local inference.Source: §1.1 · p. 2
• 0.23–0.66 seconds per inference across six datasets, with zero accuracy loss versus plaintext; encrypted training took 5.04 days on eight V100 GPUs.The GPU CKKS implementation achieved 1–2 orders of magnitude speedup over the compared CPU implementation.Source: §1.1 · p. 2

I2R, A*STAR

• PrivFT uses an RNS variant of CKKS and GPU parallelism to evaluate encrypted inputs and train models on encrypted datasets.The paper also describes application-level parallelism through packing, task decomposition, and multi-GPU scheduling.Source: §1.1 · p. 2

1.1 System Overview

• The authors present the first GPU implementation of an RNS variant of the CKKS levelled FHE scheme, to their knowledge.Source: §1.1 · p. 2

1.2 Organization of the paper

• The paper is organized to review related work and background, describe PrivFT, give implementation details, present experiments, and conclude with future directions.Source: §1.2 · p. 3

• FHE supports non-interactive computation on encrypted data but has high computational requirements and supports only addition and multiplication on ciphertexts.MPC requires high interaction and is described as bandwidth-bound.Source: §2 · p. 3
• The authors report classifying unstructured texts from different standard datasets in less than a second at 91.49%–98.80% accuracy, versus HEng’s 19 minutes per tweet and 78 minutes per email at high accuracy (>94%).HEng’s classifier runs on plaintext; providing it the full English dictionary could reveal all words in Alice’s text.Source: §2 · p. 3
• The cited MPC system [19] achieved 28.3-second latency and 74.4% accuracy on a 10,000-tweet dataset, with 60% tagged as hate speech.Its classifiers operate on secret-shared data.Source: §2 · p. 3

3 Preliminaries

• The section establishes notation for sets, vectors, matrices, rounding, and remainders, and describes GPU acceleration and packing as ways to improve FHE performance.CKKS is presented as a scheme designed for floating-point numbers; GPU acceleration is reported to provide 1 to 2 orders of magnitude over CPU implementations.Source: §3.1 · p. 4, §3.2 · p. 4

3.2 Fully Homomorphic Encryption

• FHE evaluates computations on ciphertexts using homomorphic addition and multiplication, while noise growth limits multiplicative depth in levelled CKKS.CKKS uses levels to bound supported multiplicative depth; rescaling moves ciphertexts to a lower level, and bootstrapping refreshes noise but is computationally intensive.Source: §3.2 · p. 4

3.3 Text Classification

• Recurrent models and stacked Transformer attention can exceed FHE’s practical multiplicative-depth limits, motivating fastText’s two-layer embedding-and-output architecture.A fastText inference pass has multiplicative depth 3: two vector-matrix multiplications and the averaging computation.Source: §3.3 · pp. 4–5

3.4 The CKKS levelled FHE Scheme

• CKKS represents computations in polynomial rings modulo X^N + 1 and a level-dependent modulus q_l, with L setting the maximum supported multiplicative depth.Its encoding and decoding map vectors and polynomials, while rescaling reduces the modulus level to maintain fixed precision.Source: §3.4 · pp. 5–6
• CKKS packs up to N/2 complex values in one plaintext, enabling component-wise SIMD operations across independent slots; slots can also be rotated.Packing supports vectorized operations without extra cost, while homomorphic addition and multiplication operate component-wise on packed ciphertexts.Source: §3.4 · p. 6

4.1 Homomorphic Inference with FHE

• The client encodes input words as a multi-hot vector and encrypts it, avoiding the expensive homomorphic dictionary lookup required by the original inference procedure.Repeated words increase the corresponding vector value; the server computes the embedding through a vector-matrix multiplication and scales by the plaintext word count.Source: §4.1 · p. 6
• PrivFT’s homomorphic inference uses ciphertext-plaintext operations and returns encrypted class scores without loss of prediction accuracy.The server evaluates packed vector-matrix operations; the client decrypts the scores and selects the best class in plaintext.Source: §4.1 · p. 7

4.2 Homomorphic Training with FHE

• PrivFT trains with minibatch SGD and large batches with fewer epochs to reduce model updates and the training circuit’s multiplicative depth.True SGD updates after every example and compounds depth across subsequent predictions; minibatch SGD accumulates gradients before one update per batch.Source: §4.2 · p. 7
• A shallow polynomial approximates softmax for encrypted training with no noticeable accuracy loss, while GPU memory limits require tiling encrypted-dataset computations.The reported approximation is (1/8 X^2 + 1/2 X + 1/4); tiling moves data between CPU and GPU memory to fit the computation.Source: §4.2 · p. 8

5.1 GPU implementation of CKKS

• The GPU CKKS implementation uses RNS division to approximate RESCALE, with experimental results finding its added error negligible.The implementation performs encoding and decoding on CPU, but handles RESCALE on the cloud computation path; an ordered prime chain avoids expensive RNS base extension.Source: §5.1 · pp. 8–9

5.2 PrivFT Implementation

• PrivFT has CPU and NVIDIA-GPU implementations; GPU memory limits require tiling, while parallelism techniques are used on both platforms.The CPU version uses Microsoft SEAL, while the GPU version uses the paper’s GPU CKKS implementation.Source: §5.2 · p. 9

5.2.1 Homomorphic Inference Implementation

• Inference parallelizes each hidden-matrix column and output-matrix row across processing units, and its small ciphertext workload fits in CPU or GPU memory.The server performs two vector-matrix multiplications; the implementation counts 3 HMULPLAIN operations, ⌈m/t⌉ HADD operations, and log2 N ROTATE operations.Source: §5.2.1 · p. 9

5.2.2 Homomorphic Training Implementation

• Training uses minibatch gradient updates on encrypted weights, with suitable batch size and epoch count assumed based on experience with similar public-data tasks.Prediction uses HMUL for encrypted weight matrices; gradients accumulate over examples in a batch before the model update.Source: §5.2.2 · pp. 9–10
• Encrypted training parallelizes minibatch evaluation across CPU threads, but encrypted matrices exceed GPU local memory and must be tiled between CPU and GPU.The hidden matrix is divided vertically and the output matrix horizontally for transfer between memories.Source: §5.2.2 · pp. 9–10

6.1 Methodology

• The evaluation compares GPU CKKS primitive latency with a CPU implementation, measures inference on six public datasets, and also times encrypted training.Communication cost is assessed by calculating the number and size of exchanged messages.Source: §6.1 · p. 10
• Inference and CKKS primitive timings average 100 runs, while encrypted training is run once and evaluated on a single dataset.The training dataset restriction reflects limited access to the borrowed multi-GPU platform.Source: §6.1 · p. 10

6.2 Platform Configuration

• The testbed comprises a commodity server with 104 CPU cores and an NVIDIA DGX-1 system with eight V100 GPUs.The CPU count includes hyper-threading.Source: §6.2 · p. 10, Table 1 · p. 10

6.3 Datasets

• The six datasets cover sentiment analysis, spam detection, and topic classification, with binary tasks and multiclass tasks of four and fourteen classes.The evaluation includes IMDB, Yelp, AGNews, DBPedia, YouTube Spam Collection, and Enron Email.Source: §6.3 · pp. 10–11

6.4 CKKS Parameter Selection

• The discrete Gaussian standard deviation σ is set to 3.2; precision ρ is selected experimentally, and modulus size is estimated as |qL| = L×ρ bits.Ring dimension N is chosen from practical power-of-two values, with security estimated using the LWE estimator and an 80-bit minimum recommendation.Source: §6.4 · p. 11
• Inference uses L = 5 levels, while training uses L = 46 to accommodate its feed-forward phase and loss computation across two epochs.The inference depth supports three subsequent multiplications and vector rotations in dot products.Source: §6.4 · p. 11

6.5 CKKS Micro-Benchmarks and Comparison

• The benchmark includes inference parameters (log2 N, log2 q) = (13,200) and training parameters (log2 N, log2 q) = (16,2300); SEAL was adapted to support N = 2^16.The comparison is against Microsoft SEAL's RNS CKKS implementation.Source: §6.5 · p. 11
• 33.78× to 244.62× for HMULPLAIN and 26.88× to 48.22× for HMUL versus SEAL-CKKS; GPU-CKKS outperforms SEAL-CKKS across primitives.HMULPLAIN is heavily used in inference, while HMUL is heavily used in training.Source: §6.5 · p. 11
• Rotation latency varies with the Hamming weight of the requested rotations; at high parameters, rotation keys do not fit in GPU memory and must be migrated from CPU memory.Pre-generating rotation keys can reduce rotations to one Galois automorphism, but the keys may be huge.Source: §6.5 · p. 11

6.6.1 PrivFT Inference Task

• The inference models covered six tasks and used fasttext with a 500,000-word vocabulary, 50-dimensional representations, and added bi-gram and tri-gram terms.Unlike ULMFit, BERT ITPT, and XLNet, these models used only each task's training data, without large out-of-domain pretraining.Source: §6.6.1 · p. 12, Table 3 · p. 12
• <0.66 seconds per example was the GPU inference runtime, with 12× speedup over CPU and unchanged fasttext accuracy on encrypted inputs.The reported GPU runtime applies to inference on examples from the evaluated datasets.Source: §6.6.1 · p. 12, Table 4 · p. 13
• 384.375 MB was the client-to-server inference message, while the server returned one 6.25 MB ciphertext when classes numbered at most N/2.The class-count condition held for all evaluated datasets.Source: §6.6.1 · p. 12

6.6.2 PrivFT Training Task

• Training used two epochs and a batch size of 1,007,500 tokens; five minibatches required 45 multiplicative-depth levels, plus one extra level to match plaintext accuracy.The selected CKKS parameters provided 46 levels of multiplicative depth.Source: §6.6.2 · p. 12
• 120.96 hours on 8 GPUs achieved 2.2× speedup over CPU training, which took 266.4 hours on 104 cores; both encrypted-training implementations matched fasttext's 86.3% accuracy.The GPU run took 5.04 days, compared with 11.1 days on CPU; tiling and CPU–GPU data migration limited training speedup.Source: §6.6.2 · pp. 12–13
• Encrypted training hyperparameters require trial and error or heuristic search, but the server cannot evaluate model validity and client cooperation may be undesirable.The discussion identifies learning rate, epoch count, and minibatch size as parameters needing fine-tuning.Source: §6.6.2 · p. 13
• More epochs or a higher-degree loss function proportionally increase circuit depth, potentially requiring ultra-large CKKS parameters or bootstrapping.Deeper circuits also increase fixed-point precision loss and may require precision unsupported by existing libraries.Source: §6.6.2 · p. 13
• The approach requires very large minibatches and few epochs, a setting that may not work for every task.The paper notes prior work reporting effective large-minibatch SGD and competitive results from K-FAC, but leaves FHE implementation of K-FAC as an open question.Source: §6.6.2 · p. 13

7 Conclusions

• PrivFT supports inference on encrypted inputs with a pre-learned plaintext model and training on encrypted data to produce an encrypted model.Source: §7 · p. 13
• The GPU implementation achieved 1–2 orders of magnitude speedup across parameter settings, with inference taking less than 0.66 seconds on various datasets.Source: §7 · p. 13
• Encrypted training took 11.1 days on CPU and 5.04 days on GPU; the Microsoft SEAL source code was to be released upon publication.Source: §7 · p. 13, Availability · p. 13