Privacy-Preserving Machine Learning with Fully Homomorphic Encryption for Deep Neural Network

In plain words

Imagine a company that wants to classify your photos with its neural network, but must never see the photos in readable form. Fully homomorphic encryption makes this possible in principle: the server computes on scrambled data and the result comes back still scrambled, so only the owner of the key can read it. The catch is that such computing is very slow, and the tricks that make ordinary networks work, such as the ReLU activation and repeated refreshing of the scrambled numbers, were hard to do under encryption.

This paper takes a standard image classifier, ResNet-20, trained on the usual CIFAR-10 pictures, and runs the whole network on encrypted images without changing its trained weights. It handles the hard parts by replacing the ReLU with a close polynomial approximation and by periodically "refreshing" the encrypted numbers so that more layers can be computed. The authors report that the encrypted network gives almost the same answers as the normal one. The price is time: one image takes hours.

TL;DR

The paper builds ResNet-20 over the RNS-CKKS scheme with bootstrapping, so that a deep network can be evaluated on encrypted CIFAR-10 images §1.1, §3. ReLU is approximated by a composition of minimax polynomials, the softmax by a polynomial exponential and an approximate inverse §3.4, §3.7, app. A.1. The author-reported result is 98.67% agreement with plaintext ResNet-20 on 75 encrypted images and 90.67% accuracy on those images, at about 4 hours per image tab. 4, §4.2. Use it as a reference for the design of encrypted deep inference, not as a fast deployable system.

Problem

Previous privacy-preserving models on FHE data were limited to simple, non-standard networks, mostly because they replaced non-arithmetic activations such as ReLU by low-degree arithmetic functions and did not use bootstrapping §1. The authors report that the best earlier word-wise FHE result on CIFAR-10 was 77% accuracy §1, §1.2, §4.2. Models that evaluated the activations with multiparty computation instead were said to leak the activation choice and to need the client to take part in computation §1.2.

The paper also argues that earlier FHE models returned pre-softmax scores, which lets the client extract the model from many input-output pairs; computing the softmax under encryption is presented as a fix §1.1.

Bootstrapping in CKKS is the costly, error-prone step that lets a ciphertext be refreshed for further multiplications §2.2. The authors state that no prior work had applied bootstrapping to a deep neural network §2.2.

Method

Scheme and library. The network is evaluated with the RNS-CKKS scheme, using Microsoft SEAL 3.6.1, which has no bootstrapping, so the authors implemented bootstrapping on top of it §1.1, §3.5. Weights are the plaintext parameters of a ResNet-20 trained on CIFAR-10; only the input image is encrypted §1.1, §4.1.

Architecture. The network is ResNet-20 with bootstrapping added. Its layers are convolution, batch normalization, ReLU, bootstrapping, average pooling, a fully connected layer and softmax §3.1, fig. 1. The specification table lists a first convolution with 16 filters, three stages of three residual blocks with 16, 32 and 64 filters, a 1x1 convolution on the shortcut at each of the two stage changes, average pooling over 8x8 and a 10-way fully connected layer tab. 1.

Packing. One 32x32 image is processed at a time. Each channel of the image is put in its own ciphertext, using 2^10 sparse slots, because bootstrapping a sparsely packed ciphertext is faster than a fully packed one §3.2.2.

Convolution with stride 1. The authors use the single-input single-output packed convolution from Gazelle, with zero padding to keep the size §3.3.

Convolution with stride 2. Instead of rearranging slots, which costs extra rotations, the stride-2 convolution is computed as a stride-1 convolution followed by multiplication with a 0/1 window that keeps the valid values. This needs no additional rotations §3.3, fig. 2.

Batch normalization. Because it is a linear map with constant coefficients, it is done with homomorphic addition and multiplication by a scalar §3.3.

ReLU. ReLU is written as one half of x times (1 plus sign(x)). The sign function is approximated by a composition of three minimax polynomials of degrees 15, 15 and 27, using a precision parameter alpha equal to 13 §3.4, app. A.1. Evaluation uses the odd baby-giant method and an optimal level-consumption method §3.4. Because the composition is too deep to finish without refreshing, the ReLU is bootstrapped once in its middle and once at its end §3.4.

Bootstrapping. Bootstrapping has three steps: CoeffToSlot, a modular reduction (ModReduction) and SlotToCoeff §2.2. CoeffToSlot and SlotToCoeff use a collapsed FFT with depth 2. ModReduction uses a cosine function, two double-angle formulas and an inverse sine, each approximated by a multi-interval Remez method §3.5.

Average pooling and fully connected layer. The 64 channel ciphertexts are not packed into one. Combining them would need 63 extra rotations for the fully connected matrix product, so they are kept separate, at the cost of more memory §3.6, fig. 3.

Softmax. The output scores are evaluated as exp(x/4) divided by the sum of exp(x_j/4), not as exp(x) divided by the sum of exp(x_j), so that exponentials stay within the encryption's range §3.7. The exponential is a least-squares polynomial of degree 12 on [-1, 1], applied to x/64 and then squared four times §3.7. The reciprocal of the sum is approximated on [0, 2] with an inverse-function method from the cited work, with inputs scaled by 10^-4 before and after §3.7. The softmax needs 22 bootstraps §3.7.

# Forward pass of ResNet-20 on one encrypted image  [§3.1, fig. 1]
# Input:  the image as ciphertexts, one per input channel  [§3.2.2]
# Output: 10 ciphertexts, one class score each

def encrypted_resnet20(channels, weights):
    # Stem: convolution, batch norm, ReLU  [§3.1, tab. 1]
    maps = conv_stride1(channels, weights.conv1)
    maps = batch_norm(maps, weights.bn1)          # scale and shift [§3.3]
    maps = encrypted_relu(maps)                   # [§3.4, app. A.1]
    # Three stages of three residual blocks  [tab. 1]
    for stage in weights.stages:
        for block in stage.blocks:
            # Stride 2 at the first block of stages 3 and 4  [tab. 1] [§3.3]
            maps = residual_block(maps, block, stage.stride)
    # Average pooling and fully connected layer  [§3.6, fig. 3]
    pooled = average_pool_no_repack(maps)         # 64 ciphertexts kept
    scores = fully_connected(pooled, weights.fc)  # no slot rotations
    # Softmax under encryption  [§3.7]
    return encrypted_softmax(scores)

# Softmax under encryption, as described in the paper  [§3.7]
# Input:  10 ciphertexts, one per logit
# Output: 10 ciphertexts of softmax(logits / 4)

def encrypted_softmax(logits):
    exps = []
    for logit in logits:
        # Divide by 64 to bring the input into [-1, 1]  [§3.7]
        scaled = logit * (1 / 64)
        # Degree-12 least-squares fit of exp on [-1, 1]  [§3.7]
        value = exp_poly_deg12(scaled)
        # Four squarings give exp(x/64) to the 16th, i.e. exp(x/4)  [§3.7]
        for _ in range(4):
            value = value * value
        exps.append(value)
    total = sum(exps)
    # Reciprocal on [0, 2]; inputs scaled by 1e-4 before and after  [§3.7]
    inverse = inverse_poly(total * 1e-4) * 1e-4
    return [value * inverse for value in exps]

Bootstrapping is a black-box step in the pseudocode above; its internals are described in the bullet on bootstrapping and in §3.5.

Hyperparameters

Results

Author-reported. Setup: CIFAR-10, ResNet-20, plaintext parameters from the authors' own training, one encrypted image per inference, dual Intel Xeon Platinum 8280 §4.1. The baseline is plaintext ResNet-20 tab. 4.

Runtime share by component (author-reported) tab. 5: the abbreviations PC, BN, CR, Boot, AP+FC and Softmax are used in the table but not defined in the text. Shares: PC 34.30%, BN 0.20%, CR 32.63%, Boot 29.97%, AP+FC 0.06%, Softmax 2.83%. The text names convolution, ReLU and bootstrapping as the most time-consuming parts §4.2.

The 98.67% agreement corresponds to 74 of 75 encrypted predictions matching the plaintext network; the paper states that only one differed §4.2.

Paper vs code

No official code. Searched GitHub for "ResNet-20 RNS-CKKS", "privacy-preserving ResNet CKKS bootstrapping", "fhe resnet", "rns-ckks bootstrapping", "resnet20 ckks", and the authors' names; no repository with an author owner was found. The paper gives no project or code link in its text or metadata.

Pitfalls

• Simulation or real encryption? Section 4.1 says the model is "simulated" with SEAL. Section 4.2 reports accuracy "on 75 encrypted images". The text does not say whether the encrypted numbers come from full encrypted runs or from a simulator. Treat this as unclear until the paper says more.
• Small test set. The encrypted comparison uses 75 images. The 95% intervals are wide (±6.58% on accuracy, ±2.59% on agreement). The paper trains the model once and does not average over seeds §5.
• Security margin. The parameters target 98-bit security, which the paper itself calls the minimum it considers secure. It says the level can be raised by changing parameters at the cost of run time §5. An implementation should decide the security level first.
• Bootstrapping failure. A single failed bootstrap can distort the whole network §3.5. Appendix A.2 estimates the network-level failure probability as about 2 N_b n p, where n is the number of slots, N_b the number of bootstraps and p the per-coefficient failure probability app. A.2. The paper says the earlier approximation had a failure rate near 2^-23 and that its target is below 2^-40 §3.5.
• Input range assumption. The approximation regions are chosen for inputs below 40, and the observed maximum is 37.1. The paper says the bound holds "with a very high probability", which is conjecture from sampled images, not a proof §3.2.3.
• Inverse range. The reciprocal is valid on [0, 2] after scaling by 1e-4. The bound of 1e4 on the raw sum is a heuristic finding §3.7. A sum outside that range is not covered by the paper.
• Softmax is a changed function. The network outputs softmax(x/4), not softmax(x) §3.7. The paper says the outputs are "almost the same" but does not quantify the difference.
• Learning-rate schedule is ambiguous. The text says the rate starts at 0.001 and is "divided by 10 after 80 epochs and 100 after 120 epochs". Whether the second factor is cumulative, or the total epoch count, is not stated §4.1.
• Unstated training details. The optimiser, the number of epochs and the momentum or weight decay are not stated §4.1.
• Bootstrap placement. The paper states two bootstraps per ReLU and 22 in the softmax §3.4, §3.7, and 1,149 in total §3.5. Where the remaining bootstraps occur is not stated.
• Stride-2 trick. The 0/1 window is a multiplication that the paper does not cost against the rotations it saves §3.3, fig. 2.
• One image at a time. Run time is about 4 hours per image, and the paper notes that packing across images could reduce this, which it leaves as future work §5.
• Accelerators. The paper names GPU, FPGA or ASIC accelerators as the essential future work for run time §5. It reports no measurements with them.
• Sparse slots. Only 2^10 of the 2^15 available slots are used per channel §3.2.2. The paper does not discuss the cost of this choice beyond the bootstrapping speed.

Lineage

• Builds on: the minimax-composed ReLU approximation of Lee et al., cited in the paper as [MinimaxRelu] with no arXiv id given in the text §3.4, app. A.1. RNS-CKKS and CKKS bootstrapping from the cited CKKS works §2.1, §2.2. The stride-2 convolution follows Gazelle §3.3.
• Compared against: the word-wise FHE CIFAR-10 CNN at 77% accuracy, cited as HCNN §1.2, §4.2. The TFHE model by Lou and Jiang is discussed as a leveled scheme without bootstrapping §1.
• Superseded by: not stated in this wiki.