PaperlayerView exact revision on arXiv

Source-linked AI summary

Gazelle: A Low Latency Framework for Secure Neural Network Inference

Chiraag Juvekar, Vinod Vaikuntanathan, Anantha Chandrakasan

arXiv:1801.05507v1cs.CR

TL;DR

Secure neural network inference must protect client inputs from the server while preserving the server’s model privacy. Gazelle combines packed additive homomorphic encryption, garbled circuits, optimized linear algebra, and switching protocols for complete CNN inference. It reports substantially lower online latency and bandwidth than two-party and purely homomorphic alternatives.

  • Problem

    Securely classifying private client images requires protecting client inputs from the server while preserving the server’s neural-network privacy.

  • Method

    Gazelle combines packed additively homomorphic encryption, garbled circuits, optimized linear-algebra kernels, and protocols that switch between representations.

  • Results

    Gazelle reports 20−30× lower latency and 2.5−88× lower online bandwidth than multiple two-party systems, and more than three orders of magnitude lower latency than purely homomorphic approaches.

  • Takeaways & Limitations

    The paper’s results support combining homomorphic encryption and garbled circuits to achieve low-latency secure CNN inference.

Abstract

from arXiv · show

The growing popularity of cloud-based machine learning raises a natural question about the privacy guarantees that can be provided in such a setting. Our work tackles this problem in the context where a client wishes to classify private images using a convolutional neural network (CNN) trained by a server. Our goal is to build efficient protocols whereby the client can acquire the classification result without revealing their input to the server, while guaranteeing the privacy of the server's neural network. To this end, we design Gazelle, a scalable and low-latency system for secure neural network inference, using an intricate combination of homomorphic encryption and traditional two-party computation techniques (such as garbled circuits). Gazelle makes three contributions. First, we design the Gazelle homomorphic encryption library which provides fast algorithms for basic homomorphic operations such as SIMD (single instruction multiple data) addition, SIMD multiplication and ciphertext permutation. Second, we implement the Gazelle homomorphic linear algebra kernels which map neural network layers to optimized homomorphic matrix-vector multiplication and convolution routines. Third, we design optimized encryption switching protocols which seamlessly convert between homomorphic and garbled circuit encodings to enable implementation of complete neural network inference. We evaluate our protocols on benchmark neural networks trained on the MNIST and CIFAR-10 datasets and show that Gazelle outperforms the best existing systems such as MiniONN (ACM CCS 2017) by 20 times and Chameleon (Crypto Eprint 2017/1164) by 30 times in online runtime. Similarly when compared with fully homomorphic approaches like CryptoNets (ICML 2016) we demonstrate three orders of magnitude faster online run-time.

I. INTRODUCTION

Gazelle addresses secure neural network inference by keeping client inputs private from the server and the server’s model private from the client. It combines homomorphic encryption with garbled circuits to improve efficiency over prior approaches.

  • Publicly releasing a hospital’s model can forfeit monetization and expose information derived from private patient data.
  • A machine-learning-as-a-service deployment leaves users concerned about input privacy and may expose the hospital to data-breach liability.
  • The secure inference goal is for the user to obtain predictions without learning the model while the hospital learns nothing about user inputs.
  • Gazelle combines homomorphic encryption and garbled circuits because each technique has limitations whose trade-offs can be managed jointly.
  • Gazelle uses packed additively homomorphic encryption for fast matrix-vector multiplication and convolution, rather than CryptoNets’ leveled homomorphic approach.
  • On CIFAR-10, Gazelle reduces online bandwidth from MiniONN’s 6.2GB to 0.3GB and online LAN latency from 72s to 3.6s.
  • Gazelle achieves a 30× reduction in online runtime and a 2.5× reduction in online bandwidth versus Chameleon while using a pure two-party solution.

(F)HE or Garbled Circuits? The Million-dollar Question:

Gazelle assigns different neural-network computations to homomorphic encryption and garbled circuits according to their computational structure. Its system combines optimized homomorphic layers, linear-algebra kernels, and representation-switching protocols for CNN inference.

  • Homomorphic encryption suits convolutional and fully connected layers because their computations are quadratic in input size, whereas garbled circuits suit linear-size nonlinearities.
  • Our System:: Gazelle comprises a homomorphic layer, linear-algebra kernels, and a network-inference component that combines garbled circuits with those kernels.
  • Our System:: The Gazelle Homomorphic Layer implements SIMD addition, SIMD scalar multiplication, and automorphisms using division-free arithmetic and lazy modular reduction.
  • Our System:: The Gazelle Linear Algebra kernels implement homomorphic matrix-vector multiplication and convolution algorithms that minimize expensive automorphism operations.
  • Our System:: Gazelle Network Inference switches intermediate results between secret-sharing and homomorphic representations to compose garbled circuits with linear-algebra kernels.
  • Linear Layers: A convolutional layer applies filter banks across input channels, computes single-input single-output convolutions, and sums the resulting intermediate images.
  • Linear Layers: Valid convolution uses wo = wi − fw + 1 and ho = hi − fh + 1, while same convolution preserves input image size through zero padding.
  • Linear Layers: Stride parameters determine filter-stepping granularity and modify valid or same convolution output dimensions.

FC Layers:

FC layers are linear components whose quadratic computation makes them well suited to homomorphic encryption. Gazelle’s secure inference setting separates network architecture and parameters while protecting the parties’ sensitive inputs and outputs.

  • FC Layers:: FC layers perform computations that are quadratic in the input size, guiding Gazelle toward homomorphic rather than garbled-circuit evaluation.The number of FC-layer multiplications is n_i·n_o.
  • FC Layers:: CNNs combine linear and non-linear layers, with ReLU and max-pooling representing common non-linear operations.The supplied CNN example contains convolutional and fully connected layers, uses ReLU, and adds max-pooling after the first convolution.
  • FC Layers:: Non-linear functions can be evaluated with circuits linear in input size, avoiding additional asymptotic communication penalties in conventional 2PC.This observation supports using garbled circuits for non-linear components while reserving homomorphic methods for linear layers.
  • FC Layers:: Gazelle models two parties in which A holds the CNN and B holds the input, distinguishing the network architecture from its parameters.Architecture includes layers, layer sizes, and activations; parameters include the numerical values in convolutional and fully connected layers.
  • FC Layers:: The protocol gives B the final classification result while A obtains nothing, under a semi-honest ideal/real security model.Both parties follow the protocol but may infer information about the other party’s input from the transcript.
  • FC Layers:: Gazelle hides weights, convolution filter and stride sizes, and layer types, but reveals the number and sizes of layers unless padding is used.The entire image is hidden from A, although its size is not; the architecture is therefore not completely hidden.

A. Ciphertext Addition: SIMDAdd

SIMDAdd combines packed ciphertexts componentwise, while plaintext scalar multiplication provides componentwise products. Bit decomposition reduces the otherwise large noise growth of scalar multiplication but requires low-noise encryptions.

  • A. Ciphertext Addition: SIMDAdd: SIMDAdd takes ciphertexts [u] and [v] and outputs an encryption of their componentwise sum [u + v].Its asymptotic runtime is n·CostAdd(q), and noise grows by at most η_u+η_v.
  • A. Ciphertext Addition: SIMDAdd: Plaintext scalar multiplication outputs [u◦v] from ciphertext [u] and plaintext v when the plaintext modulus satisfies p ≡1 mod m.The operation’s asymptotic runtime is n·CostMult(q).
  • A. Ciphertext Addition: SIMDAdd: Direct scalar multiplication can incur multiplicative noise growth as high as p·√n·η_u, even for binary plaintext vectors.The bound follows from the largest coefficient in the packed plaintext representation.
  • A. Ciphertext Addition: SIMDAdd: Bit decomposition splits v into w_pt-sized chunks, representing v as Σ 2^(w_pt·k)·v_k to reduce scalar-multiplication noise.The resulting product is represented as Σ[u_k◦v_k], with each chunk bounded by 2^w_pt.
  • A. Ciphertext Addition: SIMDAdd: The noise reduction requires access to low-noise encryptions [u_k] rather than only the original ciphertext [u].This is the stated caveat of the bit-decomposed multiplication approach.

C. Scalar Multiplication: Perm

Perm rearranges packed ciphertext slots according to supported scheme permutations, with available groups determined by the cyclotomic order. Permutations are computationally expensive and add noise, motivating careful parameter and implementation choices.

  • C. Scalar Multiplication: Perm: Perm maps [u] to [u^π] by rearranging ciphertext slots according to a primitive permutation π.The supported permutation set depends on the multiplicative group modulo m.
  • C. Scalar Multiplication: Perm: For m=2^k with m≥8, the permutation group supports half-rotations, including rotations within two halves and swapping those halves.This structure is illustrated by the plaintext permutation example.
  • C. Scalar Multiplication: Perm: A permutation costs Θ(n log n log q) and increases noise additively from η_u to η_u+η_rot.The cost combines one number-theoretic transform with Θ(log q) inverse transforms.
  • C. Scalar Multiplication: Perm: GAZELLE’s lattice-based PAHE uses packed SIMD operations that are cheaper than Paillier’s modular multiplication and exponentiation operations.Paillier’s large ciphertexts also make encryption costly, making it an unsuitable substitute for Gazelle’s linear algebra.
  • C. Scalar Multiplication: Perm: Parameter selection balances homomorphic evaluation capability with a target security level of 128 bits, using approximately 20-bit plaintext and 64-bit ciphertext moduli.The supplied text describes choosing q close to but below 64 bits so each ciphertext slot fits in one machine word.
  • C. Scalar Multiplication: Perm: Choosing a power-of-two m enables an 8× more efficient Cooley-Tukey NTT but restricts permutations to half-rotations.A prime m instead gives simpler cyclic permutations but requires the more expensive Bluestein transform.
  • C. Scalar Multiplication: Perm: The prime-selection procedure searches candidates satisfying congruence, reduction, and pseudo-Mersenne conditions before testing q for primality.The listed steps sample p, compute candidate δ values, and accept pairs with prime q and sufficiently small δ.
  • C. Scalar Multiplication: Perm: With p≈2^20 and q≈2^64, the prime-selection procedure is very fast.The implementation also uses Barrett reduction when ⌊log(p)⌋·3<64.

IV. OUR PROTOCOL AT A HIGH LEVEL

Gazelle alternates packed additively homomorphic encryption for linear layers with garbled circuits for nonlinear layers, converting between encodings through additive secret shares. This structure supports full-network inference while keeping communication linear in layer count and input sizes.

  • Gazelle evaluates linear layers with PAHE and nonlinear layers with Yao garbled circuits, alternating these techniques through the network.The server homomorphically evaluates convolutional or fully connected layers, then the parties use garbled circuits for activations such as ReLU.
  • The ciphertext-to-share step masks the encrypted vector with a random server vector before client decryption, yielding additive shares of the input.The server sets its share to the random mask, while the client holds the masked decryption modulo p.
  • Garbled-circuit evaluation applies nonlinear functions componentwise and returns an additive share of the nonlinear output for the next linear layer.The protocol uses a Boolean circuit to reconstruct the masked value modulo p and compute functions such as ReLU.
  • The protocol repeats homomorphic linear evaluation and garbled-circuit nonlinear evaluation until the complete network is evaluated.After garbled-circuit evaluation, the resulting share can be freshly encrypted for the next homomorphic layer.
  • Using AHE for linear layers makes communication linear in the number of layers and the size of each layer's inputs.Fresh encryption after garbled-circuit evaluation also acts as interactive bootstrapping that clears previously introduced homomorphic noise.

V. FAST HOMOMORPHIC MATRIX-VECTOR MULTIPLICATION

Gazelle's matrix-vector kernels progress from a simple row-wise method to output-packing strategies that reduce ciphertext expansion, while managing rotation costs, noise growth, and leakage from unused slots.

  • The Naïve Method: The naïve method encodes each matrix row separately, multiplies it componentwise with the encrypted input, and sums slots to obtain each output.A rotate-and-sum procedure performs log2 ni rotations to place each row's inner product in the first slot.
  • The Naïve Method: The naïve method requires no SIMD scalar multiplications, no · log2 n rotations, and no · log2 n SIMD additions.Its noise grows through the scalar multiplication followed by repeated rotations and additions.
  • The Naïve Method: The naïve method produces no separate ciphertexts, making bandwidth quadratic in input size and motivating packed output representations.The desired representation places the entire result in one packed ciphertext.
  • The Naïve Method: When n is not a power of two, unused slots leak partial sums and must be randomized to destroy that extraneous information.The leakage affects all slots except the first slot.
  • Output Packing: Output packing masks all but the first coordinate, rotates ciphertexts into distinct slots, and adds them together.Although this combines outputs, two serial SIMD scalar multiplications cause unacceptable noise growth and may require larger-than-64-bit moduli.

C. Input Packing

Input packing improves slot utilization by replicating inputs and processing multiple rows in parallel; diagonal and hybrid layouts further reduce ciphertext count and expensive rotations.

  • Input Packing: Input packing places n/ni copies of the input and corresponding matrix rows into one ciphertext, enabling parallel output computation.Rotations are applied block-by-block, requiring log(ni) rotations rather than rotating the entire ciphertext.
  • Input Packing: Input packing makes communication and computation behave as if the matrix had n′o = (no × ni)/n rows.This effective row count is especially useful when ni is much smaller than n.
  • Diagonal Method: The diagonal method arranges matrix elements so interacting terms never share a ciphertext, allowing all output elements to be formed in one packed ciphertext.Matrix diagonals are multiplied with rotated input vectors and added to produce the output vector.
  • Diagonal Method: The diagonal method costs ni SIMD scalar multiplications, ni − 1 rotations, and ni − 1 SIMD additions.Its noise is higher than the naïve method's but substantially better than naïve output packing for the stated parameters.
  • Diagonal Method: Hoisting amortizes common rotation work when one ciphertext is rotated by multiple shift amounts.The shared decomposition and transform computation is denoted PermDecomp and has Θ(n log n) complexity.
  • Hybrid Approach: The hybrid method combines extended diagonals with row-style accumulation to bring permutation counts closer to no for rectangular matrices.It trades hoistable input rotations for output rotations on distinct ciphertexts.
  • Hybrid Approach: The hybrid method almost always outperforms the naïve and diagonal methods because it reduces input rotations multiplicatively while increasing output rotations logarithmically.The paper reports benchmarks over a selection of matrix sizes in Table VIII.

VI. FAST HOMOMORPHIC CONVOLUTIONS

Gazelle's convolution kernels progress from padded single-image convolution to tightly packed and multi-channel schemes. Diagonal grouping organizes intermediate convolutions so they can be accumulated efficiently into packed outputs.

  • SISO Convolution: The padded SISO convolution maps a zero-padded input image into one ciphertext and uses filter-sized rotations to compute the convolution.The approach assumes the padded image fits within the ciphertext's n slots.
  • Packed SISO Convolution: Tightly packed convolution avoids the slots wasted by zero padding by using slot-specific scalar multiplication and filter-sized rotations.The server can precompute punctured plaintexts independently of the encrypted image and client key.
  • Multi-Channel Convolution: For multi-channel convolution, distinct input-channel ciphertexts can be reused across output filters, reducing the number of required permutation operations.The straightforward approach uses ci · fh · fw permutations on inputs while producing co outputs.
  • Channel Packing: Channel packing fits cn channels into each ciphertext, enabling cn SISO convolutions in parallel without additional padding.Packed SISO convolution starts from tightly packed input channels and preserves SIMD parallelism.
  • Channel Packing: Diagonal grouping places intermediate SISO convolutions so no ciphertext contains convolutions sharing an input or output channel.The grouped intermediates are accumulated into output ciphertexts containing packed channel results.
  • Channel Packing: Partitioning intermediate ciphertexts into cn-sized rotation sets reveals that each set can be generated from different rotations of the same input.This structure supports hoisted rotation strategies for computing intermediate ciphertexts.

Input Rotations:

Gazelle optimizes convolution evaluation by reusing rotations and choosing between input- and output-rotation strategies. It also decomposes strided convolutions into sums of simple convolutions, while exposing a throughput trade-off for padded SISO processing.

  • Input Rotations:: The output-rotation approach reuses rotations across channels, reducing input rotations by a factor of cn.It generates cn convolutions from each rotation set and then rotates intermediate ciphertexts to obtain the remaining outputs.
  • Input Rotations:: The input- and output-rotation variants trade off performance according to the 2D filter size.The choice is governed by filter dimensions and is evaluated with concrete benchmarks.
  • Input Rotations:: Strided convolutions are decomposed into sums of simple convolutions handled by the same convolution routines.The paper illustrates this decomposition for fw = fh = 3 and sx = sy = 2.
  • Input Rotations:: Padded SISO convolutions make noise growth depend on filter coefficients rather than plaintext modulus size p.For batched classification, channel packing can improve throughput, but it lowers slot utilization and reveals the filter size.

VII. IMPLEMENTATION AND MICRO-BENCHMARKS

Gazelle implements PAHE and garbled-circuit primitives at a 128-bit security level, then benchmarks their arithmetic, permutation, and evaluation performance. Optimized modular reduction and permutation preprocessing substantially improve selected operations.

  • VII. IMPLEMENTATION AND MICRO-BENCHMARKS: Gazelle combines a BFV-based PAHE scheme with Yao garbled circuits, with parameters selected for 128-bit security.Yao is chosen because its constant number of rounds performs well over long-latency links.
  • VII. IMPLEMENTATION AND MICRO-BENCHMARKS: Gazelle’s benchmarks use four-threaded AWS c4.xlarge instances in a LAN setting with AES-NI enabled.The implementation runs on Ubuntu 16.04.2 and is compiled with GCC 5.4.0 using -O3.
  • Arithmetic and PAHE Benchmarks:: Roughly 7× faster NTT and inverse NTT operations result from pseudo-Mersenne moduli and lazy modular reduction.Barrett reduction improves plaintext NTT runtimes by more than 5×.
  • Arithmetic and PAHE Benchmarks:: An individual permutation after decomposition is roughly 8-9× faster than one without pre-computation.Permutation runtime grows linearly with the number of windows, creating a noise-versus-runtime trade-off.

2) Linear Algebra Benchmarks:

Gazelle benchmarks packed matrix-vector multiplication, convolution, and activation kernels using one-time preprocessing and hybrid homomorphic/garbled-circuit techniques. Window sizing and rotation reuse improve online performance while preserving compact communication.

  • 2) Linear Algebra Benchmarks:: Gazelle compares naive, diagonal, and hybrid packed matrix-vector multiplication methods across three matrix sizes.The comparison reports online computation and one-time setup time, with different plaintext-window choices for each method.
  • 2) Linear Algebra Benchmarks:: Optimal window sizing can further reduce matrix-multiplication online runtime, but all corresponding relinearization keys must be sent during setup.This shifts communication and storage requirements to the initial setup phase.
  • 2) Linear Algebra Benchmarks:: The two-way online message size for each matrix is (w + 1) * ctsz, with ctsz equal to 32 kB for the reported parameters.The scheme is described as extremely parsimonious in online bandwidth.
  • 2) Linear Algebra Benchmarks:: Output rotation is usually faster for 2D convolution because it reuses the same input multiple times.Larger filters save more rotations, whereas input rotation is faster for the 1×1 case.
  • 2) Linear Algebra Benchmarks:: Square pooling uses additive homomorphic encryption, while ReLU and MaxPool use garbled-circuit protocols.The activation and pooling implementations are evaluated separately in Table XI.

VIII. NETWORK BENCHMARKS AND COMPARISON

Gazelle composes its optimized layers into MNIST and CIFAR-10 secure-inference networks and compares them with prior systems. It reports substantially lower latency and bandwidth, while future work targets larger applications and broader computation support.

  • VIII. NETWORK BENCHMARKS AND COMPARISON: Gazelle evaluates complete CNNs on MNIST and CIFAR-10, separating comparisons by CNN topology.This design distinguishes implementation gains from gains caused by changing network structure.
  • MNIST: Over 3 orders of magnitude lower latency and bandwidth are reported against CryptoNets for the evaluated MNIST comparison.Networks A and B use square activation and avoid garbled circuits through an additive-homomorphic interactive protocol.
  • MNIST: Roughly 30× and 17× lower runtime are reported for MNIST networks C and D compared with Chameleon and MiniONN, respectively.These networks use garbled circuits for ReLU and MaxPool, while Gazelle does not rely on a trusted third party unlike Chameleon.
  • CIFAR-10: 50× faster offline processing and 20× lower per-inference latency are reported on CIFAR-10 despite a network with 500× more multiplications than a cited MNIST network.The comparison is presented as evidence that the results scale to larger networks.
  • Conclusions and Future Work: Across cited two-party systems, Gazelle reports 20-30× lower latency and 2.5-88× lower online bandwidth.Compared with purely homomorphic approaches, it reports more than 3 orders of magnitude lower latency and 2 orders of magnitude lower bandwidth.
  • Conclusions and Future Work: Future work includes larger application-specific networks, alternative two-party protocols, and a compiler that factors computations into PAHE and two-party primitives.The proposed extensions target medical and financial analytics, face recognition, bandwidth trade-offs, and broader programmability.
Loading 1801.05507v1…