TL;DR

The paper implements a bootstrappable Gentry-style FHE scheme together with bitwise logic circuits (add, multiply, max, mean, exp) to run a small single-convolution CNN on MNIST under encryption, and quantifies how security parameters and fixed-point precision drive accuracy and (very large) latency [§I, §IV].

Problem and motivation

Cloud-delegated ML on sensitive inputs (medical images, behavioral, health) needs an untrusted server (Bob) to compute on encrypted client (Alice) data without seeing plaintext [§I]. Prior partially-homomorphic ciphers (Paillier, RSA) support only one operation, and the YASHE-based CryptoNets approach is leveled — its security parameters must be tailored to the network depth and cannot grow without re-tuning [§I]. The authors therefore focus on bootstrapped FHE so arbitrarily complex networks can in principle be evaluated [§I]. Threat model: honest-but-curious server holding ciphertext only; circular security is assumed for the encrypted secret key used in bootstrapping [§II-A].

Key contributions

FHE setup

ML setup

Datasets

Dataset Task Size (train/test) Modality Notes
MNIST [12] 10-class digit classification 60,000 train / 10,000 test (NI=30 used for PR/ASSE plaintext-fixed-point evaluation) 28×28 grayscale images Plaintext-float baseline accuracy 91.2% [§IV, §V-A]

Pipeline diagram

flowchart LR
    subgraph Client
        A[28x28 MNIST image] --> B[Fixed-point Q12.6]
        B --> C[Bitwise encrypt pk*]
    end
    subgraph Server
        D[Conv bitwise circuit]
        D --> E[ReLU a AND notMSB]
        E --> F[Mean pool circuit]
        F --> G[Softmax exp circuit]
        G --> H[Bootstrap per gate]
    end
    subgraph ClientDec [Client]
        I[Bitwise decrypt sk*] --> J[Argmax label]
    end
    C -. ciphertext bits .-> D
    H -. ciphertext bits .-> I

Pipeline steps (text)

  1. Client trains the CNN in plaintext IEEE-754 double precision and obtains 10,810 weights [§IV].
  2. Client encodes each pixel in two’s-complement fixed-point Q12.6 (19-bit) [§II-D, §V-A].
  3. Client encrypts every bit with the extended scheme Enc(pk, m) producing c = (c, z) [Alg. 2].
  4. Server runs the bitwise addition circuit (5n−7 XORs, 3n−5 ANDs) for every convolution sum [§III-C, eq. (12)].
  5. Server runs the bitwise multiplication circuit for every conv product [eq. (12)].
  6. Server applies ReLU as a·¬MSB(a) per feature-map element [§III-C, eq. (14)].
  7. Server applies 2×2 mean pooling via the mean circuit f_mean [eq. (15)].
  8. Server computes softmax via the exponential circuit f_exp on each of 10 logits [eq. (13)].
  9. After every gate the server bootstraps to refresh noise (t_boot ≈ 20.66 s at λ=9) [Table I].
  10. Client decrypts the encrypted class-probability bits with Dec(sk, c) and takes argmax [Alg. 3, §II-A].

Architecture diagram

flowchart LR
    I([Input 28x28]) --> C1[Conv 10ch 9x9]
    C1 --> A1[ReLU bitwise]
    A1 --> P1[Mean pool 2x2]
    P1 --> F[Flatten 4000]
    F --> FC[Dense to 10]
    FC --> S[Softmax exp circuit]
    S --> O([Argmax 0-9])

Results

Metric This paper Baseline Hardware
Plaintext-float CNN test accuracy 91.2% on 10,000 MNIST test images — Intel i5-3570k @ 3.4 GHz, 8 GB RAM [§IV]
Prediction Rate (Q12.6 vs float) 1.0 — all NI=30 predictions match float l<6 bits: degraded PR i5-3570k [§V-A, Fig. 3]
ASSE (Q12.6 vs float) Reaches “satisfactory” minimum at l=6 larger at l<6 i5-3570k [§V-A]
t_add (bitwise) plaintext 3.65 × 10⁻⁷ s — i5-3570k [Table I]
t_mult (bitwise) plaintext 3.4 × 10⁻⁷ s — i5-3570k [Table I]
t_add (bitwise) ciphertext 1.26 × 10⁻³ s — i5-3570k, λ=9 [Table I]
t_mult (bitwise) ciphertext 9.54 × 10⁻³ s — i5-3570k, λ=9 [Table I]
t_boot per gate 20.66 s — i5-3570k, λ=9 [Table I]
Predicted single-image inference t_pred ≈ 10¹² s (n_add·(t_add+t_boot) + n_mult·(t_mult+t_boot)) at λ=9 CryptoNets [11]: 250 s for batch of 4096 (LFHE/YASHE) i5-3570k, λ=9 [§V-B]
Training time (plaintext) ≈ 36 hours over 60,000 images — i5-3570k [§IV]
Key size 23.4 KB — λ=9, α=2, β=1 [§V-B]

Limitations and assumptions

Code and artifacts

Source code released by the authors at https://github.com/comsyslab/homomorphic-paper-code (Møller, Hansen, Jacobsen, Hernández Marcano, 2019) [ref. 16]. License not reported.

Extra diagrams (optional)

Threat model

flowchart LR
    A[Alice client] -- enc bits of image --> B[Bob untrusted server]
    B -- enc bits of softmax probs --> A
    A -. holds sk* .- A
    B -. holds pk*, E_pk(sk) for bootstrap .- B

Open questions