Sun et al. 2020 — Private Machine Learning Classification Based on FHE

TL;DR

The authors propose an efficiency-improved BGV-style FHE scheme that swaps the order of relinearization and modulus switching (and skips both when the next operation is additive), then use it to build private hyperplane, Naive Bayes, and decision-tree classifiers with a single-interaction homomorphic comparison protocol [Abstract][§I.A].

Problem and motivation

Outsourced machine-learning classification on sensitive data (medical, genomic, spam) leaks user privacy if the cloud sees plaintexts [§I]. Prior privacy-preserving classifiers either rely on additive-only cryptosystems (Paillier, Quadratic Residuosity) that need many client/server interactions to emulate multiplications, or on FHE libraries (HElib, Khedr) whose multiplicative-homomorphic step is expensive. The threat model is an honest-but-curious cloud server holding ciphertexts; only the user holds the secret key [§V]. Security target is CPA under RLWE [§III.D].

Key contributions

FHE setup

ML setup

Datasets

Dataset Task Size (train/test) Modality Notes
Wisconsin Breast Cancer (Original), UCI Binary classification Not reported Tabular (clinical features) Used for all three classifiers; k=4 classes/branches and n=3 features in the experiments [§VI]

Pipeline diagram

flowchart LR
    subgraph Client_in [Client]
        A[Encode rational input] --> B[Encrypt w pk]
    end
    subgraph Server [Cloud server]
        C[Homomorphic inner product] --> D[Homomorphic compare]
        D --> E[Homomorphic argmax]
    end
    subgraph Client_out [Client]
        F[Decrypt w sk] --> G[Read class index]
    end
    B -. ciphertexts .-> C
    E -. ciphertext .-> F

Pipeline steps (text)

  1. Client encodes rational features using Bos’s fractional encoder [§IV.B].
  2. Client encrypts inputs (and, depending on the classifier, weights / probabilities / class labels) using the improved BGV scheme and uploads them [§V.A–C].
  3. Server computes the model-specific homomorphic sum-of-products (inner product for hyperplane; Π of conditional probabilities for Naive Bayes; comparison-bit polynomial for decision tree) [§V].
  4. Server runs the one-round homomorphic comparison protocol c_b = c_t +_h c_0 -_h c_1 and returns c_b for each comparison [§IV.C, Fig. 2].
  5. Server runs the homomorphic-maximum loop to obtain the argmax ciphertext c_{k*} [§IV.D, Fig. 3].
  6. Client decrypts the returned ciphertext(s) and reads off the class index k* (decision tree: k* = Σ P_i · 2^i) [§V.C].

Architecture diagram

flowchart LR
    I([Encrypted x, w_i]) --> M{Classifier type}
    M --> H[Hyperplane: enc inner product]
    M --> N[Naive Bayes: enc Pi of probs]
    M --> T[Decision tree: enc compare bits]
    H --> AM[Homomorphic argmax]
    N --> AM
    T --> POLY[Enc polynomial P_i]
    POLY --> SUM[Enc Sigma P_i times 2^i]
    AM --> O([Enc class index])
    SUM --> O

Results

All times are microseconds, averaged over 3 runs on the VM described under Hardware [§VI]. There is no plaintext-accuracy comparison — the paper does not report classification accuracy, only runtime.

Metric This paper (ours + SIMD) Baseline Hardware
10 hom. ops, mult-depth 1, λ=55 0.84 µs HElib+SIMD: 98.77 µs; Khedr: 790.26 µs i5-3470 @ 3.2 GHz, 1 core, 3.7 GB RAM [§VI, Tab. 1]
10 hom. ops, mult-depth 2, λ=55 23.41 µs HElib+SIMD: 214.66 µs; Khedr: 2310.10 µs same [§VI, Tab. 2]
10 hom. ops, mult-depth 3, λ=55 132.62 µs HElib+SIMD: 316.24 µs; Khedr: 3107.92 µs same [§VI, Tab. 3]
Homomorphic comparison, λ=55 0.13 µs Not compared (different primitive) same [§VI, Tab. 4]
Private hyperplane classification, λ=55 2.41 µs (SIMD) / 9.22 µs (no SIMD) — same [§VI, Tab. 5]
Private Naive Bayes, λ=55 141.95 µs (SIMD) / 568.07 µs (no SIMD) — same [§VI, Tab. 6]
Private decision tree, λ=55 177.06 µs (SIMD) HElib+SIMD: 1788.60 µs; Khedr: 2329.26 µs same [§VI, Tab. 7]

Single-inference number for the comparison table is taken from private decision tree at λ=55 with SIMD: 177.06 µs = 0.000177 s.

Limitations and assumptions

Code and artifacts

Not released. Implementation is described as custom C++ over NTL, compiled with GCC [§VI]. No repository URL given.

Extra diagrams (optional)

Threat model

flowchart LR
    U[User holds sk] -- enc(x), enc(w) --> S[Cloud server, honest-but-curious]
    S -- enc(c_b) per comparison --> U
    U -- enc(b) bit --> S
    S -- enc(class index) --> U

Open questions