TAPAS: Tricks to Accelerate (encrypted) Prediction As a Service

1 Introduction

• Fully homomorphic encryption does not scale to real-world machine-learning applications without model changes and improved algorithmic tools.Clients may be unwilling or unable to share private data with service providers.Source: §1 · p. 1
• Binary neural networks can support efficient, highly accurate encrypted prediction using a binary-data FHE scheme and specialized circuits for fully connected, convolutional, and batch-normalization layers.The approach also sparsifies encrypted computation to further reduce computation time.Source: §1 · p. 2

1.1 Our contributions

• The contribution targets faster encrypted prediction of complex models through changes to neural-network training and design, plus algorithmic acceleration and parallelization.Source: §1.1 · p. 2
• Two proposed circuit designs—reduce trees and sorting networks—compute inner products between unencrypted and encrypted data.The paper compares their runtimes.Source: §1.1 · p. 2
• The +1 trick sparsifies encrypted computation, and the paper reports parallelized timings and classification accuracies on real-world datasets.Source: §1.1 · p. 2

2 Encrypted Prediction as a Service

• In encrypted prediction as a service, clients seek predictions from a provider's model without giving the provider sensitive raw data.Source: §2 · p. 3

2.1 Privacy and computational guarantees

• The desired guarantees protect both client data and the server's model, while limiting external parties, communication rounds, and client dependence on the model.The client sends encrypted data and a public key; the server evaluates the model on the ciphertext and returns an encrypted prediction for the client to decrypt.Source: §2.1 · p. 3

2.2 Existing approaches

• Prior approaches differ in whether they satisfy the specified guarantees; the paper reports that its method is significantly faster than Meehan et al. (2018), with little sacrifice in accuracy.CryptoNets violates P2 and C3(i), while Bourse et al. (2017) may not satisfy C3(i).Source: §2.2 · p. 4, Table 1 · p. 4
• The authors propose a tailored homomorphic-encryption technique to meet the privacy and computational requirements.Source: §2.2 · p. 4

3 Background

• The paper assumes binary data and defines homomorphic computation as operating on ciphertexts to produce an encryption of the corresponding plaintext operation.Public-key encryption uses a public key, while decryption requires the secret key.Source: §3 · pp. 4–5

3.1 Fully Homomorphic Encryption

• FHE permits arbitrary computation on encrypted data, but computation noise accumulates; bootstrapping reduces it without decryption, though it remains slow and memory-intensive.The cited optimized implementation takes roughly six minutes per bootstrap.Source: §3.1 · p. 5

3.1.1 Encrypted Prediction with leveled HE

• Leveled encrypted prediction approximates existing algorithms with few operations to avoid bootstrapping, requiring parameter tuning for security, memory, and runtime.CryptoNets is given as a prominent example.Source: §3.1.1 · p. 5

3.1.2 Encrypted Prediction with FHE

• TFHE bootstrapping was reduced to under 0.1 seconds, making encrypted computation modular, with each added neural-network layer incurring its own cost.The section connects this modularity to the importance of deep networks with many layers.Source: §3.1.2 · pp. 5–6

3.2 Binary Neural Networks

• BNNs map binary inputs through binary weights and sign activations; evaluation uses XNOR and popcount, then applies a bias-adjusted threshold.TFHE is restricted to binary operations.Source: §3.2 · p. 6
• The approach targets binary activations; implementation of related ternary and quantized models on encrypted data is left for future work..Source: §3.2 · p. 6

4 Methods

• TFHE circuits implement fully connected, convolutional, and batch-normalization layers for binary neural networks on encrypted data.The circuits operate on encrypted data and unencrypted weights and biases.Source: §4 · p. 6
• The encrypted computations are designed as data-oblivious circuits, whose gates at the same tree level can be evaluated in parallel.The paper favors shallow circuits for parallelization.Source: §4 · p. 7

4.1 Binary OPs

• The binary-operation circuits cover inner products, binary activations, and bias handling, with the inner product computed by XNORs followed by summation.The paper considers reduce-tree addition and a sorting network for summation; the reduce tree supports encrypted threshold comparison for the activation.Source: §4.1 · p. 7, §4.1.1 · pp. 7–8

4.1.2 Batch normalization

• At evaluation time, batch-normalization scaling and translation can be folded into the bias when the activation is the sign function.The scale and translation factors are plaintext parts of the model.Source: §4.1.2 · p. 8

4.2 Sparsification via “+1”-trick

• The “+1”-trick uses clear ±1 weights to compute each inner product by summing at most half the encrypted inputs, with a shared sum computed once.When a weight vector has more −1s than +1s, the computation can instead use (1 − w) and (1 − x).Source: §4.2 · pp. 8–9
• The “+1”-trick roughly halves one layer’s computation time, with savings sometimes greater when fewer than half the inputs need summing.Bit shifts add no homomorphic operations, and the shared encrypted sum is computed once per layer.Source: §4.2 · p. 9

4.3 Ternarization (Weight Dropping)

• Ternarizing binary-network weights can set roughly a quarter to zero while maintaining the same test accuracy, allowing corresponding encrypted inputs to be dropped.The remaining elements are processed with the sparsification method.Source: §4.3 · p. 9

5 Experimental Results

• The experiments report encrypted BNN prediction timings across datasets and computational settings, then compare BNN accuracies with floating-point networks.The authors also make their code freely available.Source: §5 · p. 9

5.1 Reduce tree vs. sorting network

• The reduce tree is strictly faster than the sorting network with or without parallelization, so the experiments use it for inner products.The comparison is notable because the sorting network has fewer gates, while the reduce tree has fewer computation levels.Source: §5.1 · p. 9

5.2 Datasets

• The evaluation spans Cancer, Diabetes, Faces, and MNIST, covering health-related and surveillance applications alongside a standard digit benchmark.The tasks include tumor classification, hospital-readmission labels, gender identification from faces, and digit classification.Source: §5.2 · p. 10

5.3 Timing

• With complete output parallelism, all methods finish under two hours; 16-machine output parallelism brings Faces below 1.5 days and MNIST to 2 hours.Without output parallelism, fully connected Cancer and Diabetes predictions take seconds or minutes, while convolutional Faces and MNIST predictions take multiple days; the +1-trick halves MNIST time and saves 200 hours on Faces.Source: §5.3 · pp. 10–11, Table 2 · p. 11

5.4 Accuracy

• BNN and floating-point accuracies differ by at most 1.2% on MNIST; Faces shows a 5.1% gap using a different floating-point network.The table also compares weight dropping; 10% dropping reduces accuracy by at most 1.2% on Faces, while 20% has small effects except on Cancer.Source: Table 3 · p. 11, §5.4 · p. 11

• The paper presents techniques for practical encrypted prediction as a service, with non-binary quantized networks and encrypted model training left for future work.Source: §6 · p. 12