Homomorphic encryption

Overview

Homomorphic encryption (HE) lets a party compute on ciphertexts so that the decrypted result equals the result of the same computation on the plaintext. Fully homomorphic encryption (FHE) allows arbitrary circuits in principle. In machine learning the typical setting is private inference: the client encrypts an input, the server evaluates its model on the ciphertext, and only the client can decrypt the output.

One card lists the concept. It applies a leveled CKKS-type scheme to a standard image classifier and reports results from that single design 2106.07229 §1.1. The paper's framing is that earlier FHE models were limited to simple networks, mostly because they replaced ReLU with low-degree arithmetic functions and did not use bootstrapping 2106.07229 §1. Two things make a deep network hard under encryption:

1. Non-arithmetic functions. Comparisons such as ReLU and the softmax cannot be computed by addition and multiplication alone, so they are replaced by polynomial approximations 2106.07229 §3.4, §3.7.
2. Noise and depth. Each multiplication grows the noise, and the number of multiplications is limited by the parameters. Bootstrapping refreshes a ciphertext so that computation can continue 2106.07229 §2.2.

The page covers the variant on the card, the constraints it fits, and the figures its author reports. For the other main cryptographic approach to private inference, see secure multi-party computation and garbled circuits.

Variants

Bootstrapped CKKS for a full CNN (ResNet-20)

The card's design runs every layer of ResNet-20 on encrypted input. The model weights stay in plaintext and only the input image is encrypted 2106.07229 §1.1, §4.1. Card: ResNet-20 under encryption, 2106.07229.

The main ingredients, each reported by the paper:

• Scheme. RNS-CKKS, which works on approximate real numbers. The authors use Microsoft SEAL 3.6.1 and add bootstrapping on top, because that version does not include it 2106.07229 §1.1, §3.5.
• Parameters. Ring degree 2^16, a sparse secret key with Hamming weight 64, 11 levels for evaluation and 18 for bootstrapping. The paper targets 98-bit security 2106.07229 §3.2.1, tab. 2, §5.
• Packing. Each input channel goes into its own ciphertext, using 2^10 of the 2^15 slots, because sparse packing makes bootstrapping faster 2106.07229 §3.2.2.
• Linear layers. Convolutions use a packed single-input single-output method that the paper takes from Gazelle. Stride 2 is handled by a stride-1 convolution followed by a 0/1 mask, which avoids extra rotations 2106.07229 §3.3, fig. 2. Batch normalization becomes a scalar multiply and add 2106.07229 §3.3.
• ReLU. ReLU is written with a sign function, which is approximated by a composition of three minimax polynomials of degrees 15, 15 and 27. The ReLU is bootstrapped twice, once in the middle and once at the end 2106.07229 §3.4, app. A.1.
• Bootstrapping. Three stages: CoeffToSlot, a modular reduction and SlotToCoeff. The modular reduction uses a cosine approximation, double-angle steps and an inverse sine approximation 2106.07229 §2.2, §3.5.
• Pooling and output layer. The 64 channel ciphertexts are not repacked into one. This avoids extra rotations for the fully connected layer, at the cost of memory 2106.07229 §3.6, fig. 3.
• Softmax. Computed under encryption, using an exponential polynomial of degree 12 and an approximate inverse. The network outputs softmax(x/4), not softmax(x) 2106.07229 §3.7.

The paper reports 1,149 bootstraps for the whole model, 2 per ReLU and 22 in the softmax, without a per-layer split 2106.07229 §3.4, §3.5, §3.7.

When to use which

The page has one variant on record, so the table compares this design with the constraints it can and cannot meet. Each row is limited to what the card reports.

Implementation sketch

The core is the same for the CKKS variant on the card: keep the weights in plaintext, encrypt the input once, evaluate each layer with additions and multiplications, and replace each non-arithmetic function by a polynomial. Bootstrap wherever the remaining depth runs out. The steps below follow the card's layer order 2106.07229 §3.1.

# Encrypt the input once, one ciphertext per channel  [§3.2.2]
# Weights are plaintext and never encrypted  [§1.1]
def private_inference(image, weights):
    cts = [encrypt(channel) for channel in image]

    # Each linear layer: packed convolution, scalar batch norm  [§3.3]
    cts = conv_packed(cts, weights.stem)
    cts = scale_and_shift(cts, weights.bn)

    # Non-arithmetic step: polynomial ReLU, bootstrapped mid and end  [§3.4]
    cts = relu_poly(cts, bootstrap_mid=True, bootstrap_end=True)

    # Residual stages; stride 2 by stride-1 conv plus a 0/1 mask  [§3.3]
    for block in weights.blocks:
        cts = residual_block(cts, block)

    # Keep channels separate, avoiding repacking  [§3.6]
    cts = average_pool_no_repack(cts)
    scores = fully_connected(cts, weights.fc)

    # Softmax of x/4 using a polynomial exp and an approximate inverse  [§3.7]
    return softmax_poly(scores)  # ciphertexts for the client to decrypt

Bootstrapping is a black box in this sketch. Its internal steps are in §2.2 and §3.5.

Contradictions

No disagreement between papers: one card on record. Within the one paper, the card records these points as unresolved:

• Simulated or real encryption. Section 4.1 says the model is simulated in SEAL. Section 4.2 reports accuracy on "encrypted images". The text does not say whether the encrypted results come from real encrypted runs 2106.07229 §4.1, §4.2.
• Softmax. The network outputs softmax(x/4). The paper says the outputs are almost the same as the standard softmax but gives no measure of the difference 2106.07229 §3.7.

Papers

• ResNet-20 under encryption, 2106.07229: bootstrapped RNS-CKKS evaluation of ResNet-20 on encrypted CIFAR-10 images, with author-reported accuracy and run time.