🔒

Modern Cryptography Series · Presentation 08

Fully Homomorphic
Encryption

Compute on ciphertext without decrypting — from Gentry's blueprint through CKKS, TFHE and hardware acceleration to real-world deployment

Lattices BGV · BFV · CKKS TFHE · FHEW Bootstrapping HW Acceleration

Arrow keys or swipe to navigate · Esc for overview · F for fullscreen

← Back to series

The Holy Grail of Cryptography

"Can we delegate computation to an untrusted party without revealing our data?"

🔴 Traditional Cloud

Encrypt data at rest & in transit
Must decrypt to compute
Cloud provider sees plaintext
Data breaches expose secrets

🟢 FHE Cloud

Client encrypts input locally
Server computes on ciphertext
Server never sees plaintext
Client decrypts result only

Enc(x) ⊕ Enc(y) = Enc(x + y) Enc(x) ⊗ Enc(y) = Enc(x · y)

FHE supports arbitrary functions over encrypted data — both addition and multiplication, composable without limit

Homomorphic Encryption Taxonomy

Class	Operations	Depth	Example
PHE — Partially	+ or × (not both)	Unlimited	Paillier, El Gamal
SHE — Somewhat	+ and ×	Limited L	BGV (small circuits)
LHE — Levelled	+ and ×	Fixed L (no boot)	BFV, CKKS, BGV (levelled)
FHE — Fully	+ and ×	Unlimited	BGV+Boot, TFHE, FHEW

Why depth matters

Each multiplication consumes a "level" of noise headroom. Without bootstrapping (refreshing the ciphertext), depth is bounded. FHE = LHE + bootstrapping.

Part I

Mathematical Foundations

Ring Learning With Errors, polynomial rings, and the noise growth that makes FHE both possible and hard

Learning With Errors (LWE)

The LWE Problem

Given many samples (aᵢ, bᵢ) where:

bᵢ = aᵢ · s + eᵢ (mod q)

s — secret vector ∈ ℤ_qⁿ
aᵢ — uniformly random ∈ ℤ_qⁿ
eᵢ — small error from χ (Gaussian)

Finding s is computationally hard — as hard as worst-case lattice problems (Regev 2005).

Why error?

Without noise, solving for s is trivial Gaussian elimination. The error makes the system overdetermined and noisy — no efficient algorithm known.

Security

Worst-case GapSVP and SIVP reduce to LWE (a quantum reduction, Regev 2005) — believed hard even for quantum computers.

Ring-LWE — Compact & Efficient

Polynomial Ring

R = ℤ[x] / (xⁿ + 1)

n — power of 2 (512, 1024, 2048, 4096…)
Cyclotomic polynomial xⁿ + 1 gives good structure
Rq = R / qR for ciphertext modulus q

RLWE Sample

(a, b = a·s + e) ∈ Rq × Rq

One polynomial encodes n coefficients — RLWE packs n × more data per sample than plain LWE.

Why xⁿ + 1?

NTT-friendly — enables O(n log n) polynomial multiplication
Negacyclic convolution keeps coefficients bounded
Hardness rests on worst-case problems on ideal lattices (a quantum reduction, Lyubashevsky–Peikert–Regev 2010), not on general LWE

Parameters

n	log₂ q	Security
1024	27	~128-bit
2048	54	~128-bit
4096	109	~128-bit
8192	218	~128-bit

Source: HE Security Standard v1.1 (2018), ternary secret, classical 128-bit.

Noise Growth — The Central Challenge

Noise after operations

Addition: noise grows linearly — eᵣ = e₁ + e₂
Multiplication: noise grows multiplicatively — in BGV it roughly squares (hence modulus switching); in BFV it is multiplied by roughly t·n (eᵣ ≈ t·(I₁e₂ + I₂e₁)). Relinearisation adds a little more

In BFV, noise bits grow linearly with depth: a depth-L circuit needs about L·log₂(t·n) extra bits of q (Fan–Vercauteren 2012).

Decryption failure

Decryption needs the noise below half the gap between message steps: |m + t·e| < q/2 in BGV, |e| < Δ/2 ≈ q/(2t) in BFV — the same headroom. Beyond it, decryption returns garbage — the hard ceiling on depth for SHE/LHE.

Noise management techniques

Modulus switching — divide by one prime of q after each multiplication; the noise magnitude stays roughly constant while q loses one prime per level (BGV)
Relinearisation — a key switch that turns the degree-2 product (needs s²) back into a ciphertext under s
Rescaling — CKKS: divide by Δ (drop one prime); noise becomes rounding error in the low bits
Bootstrapping — homomorphically decrypt to reset noise to fresh level

Part II

FHE Scheme Landscape

BGV, BFV, CKKS, TFHE, FHEW — design rationale, native plaintext space, and target workloads

Gentry's Blueprint (2009)

The Breakthrough

Craig Gentry (Stanford / IBM) proved the first FHE construction. Key insight: self-referential bootstrapping — use the scheme to evaluate its own decryption circuit.

Bootstrappable: depth(C_dec) + 1 ≤ L

Squashing trick

Original SHE decryption was too deep. Gentry added a hint in the public key that reduces decryption to a sparse-subset-sum — shallow enough to evaluate homomorphically.

Bootstrapping in one line

Let ct = Enc(m) with high noise
Publish sk encrypted: ct_sk = Enc(sk)
Evaluate Dec_sk(ct) homomorphically using ct_sk
Result: fresh Enc(m) with reset noise

Historical impact

2009: Gentry STOC (ideal lattices)
2011: BGV — ring-based, practical
2012: BFV — Brakerski; Fan–Vercauteren
2016: TFHE — fast gate bootstrapping (ASIACRYPT 2016)
2016–18: full-RNS BFV — Bajard et al.; Halevi–Polyakov–Shoup
2017: CKKS — approximate arithmetic

BGV & BFV — Integer Arithmetic

BGV (Brakerski-Gentry-Vaikuntanathan 2011)

Plaintext space: ℤₜ[x]/(xⁿ+1) — small integer polynomial ring modulo plaintext prime t
Noise management: modulus switching — drop one modulus level per multiplication
Multi-level ciphertext modulus: q = q₀·q₁·…·qₗ (RNS representation)
Efficient for levelled FHE; bootstrapping optional

BFV (Fan-Vercauteren / Brakerski 2012)

Plaintext space: same — ℤₜ[x]/(xⁿ+1)
Key difference: noise managed via scale invariance — divide by Δ = q/t after multiplication
Simpler modulus structure: one q throughout (implemented in RNS by the full-RNS variants)
Preferred for: integer lookup tables, exact arithmetic, database queries

BGV vs BFV — practical guidance

BGV is faster when circuit depth L is known at compile time (levelled mode). BFV's simpler structure makes it easier to implement and tune. Both are available in Microsoft SEAL (BGV since v4.0) and OpenFHE; HElib implements BGV (and CKKS), not BFV. Choose BGV for deep circuits, BFV for shallow encrypted integer operations.

CKKS — Approximate Real Arithmetic

Cheon-Kim-Kim-Song (2017)

Treats noise as rounding error rather than decryption failure. Enables native floating-point-like operations over encrypted real (and complex) numbers.

Dec(ct) ≈ m (error small relative to Δ)

Encode real vector m via SIMD slots using CRT/FFT
Scaling factor Δ (typically 2⁴⁰–2⁵⁰) sets the fractional precision
Rescaling after × absorbs noise into least-significant precision bits

CKKS SIMD packing

A single ciphertext encodes n/2 complex values simultaneously (Galois automorphism rotations allow inter-slot operations).

n = 8192 → 4096 slots
n = 16384 → 8192 slots
Throughput counts per slot: one HMult (N = 2¹⁶, 32,768 slots) takes 17.4 ms on a V100 GPU ≈ 2 million slot-multiplies/s (Jung et al. 2021)

Best for

Neural network inference on private data
Private genomics (GWAS, PRS)
Encrypted statistics and ML training
Financial risk models

TFHE & FHEW — Fast Gate-Level FHE

FHEW (Ducas-Micciancio 2015)

Encrypts single bits (or small integers) using plain LWE
Bootstrapping in about 0.5 s per gate on a PC (the paper's "less than a second") — the first practical gate bootstrapping
Key tool: ring GSW external product for blind rotation
Evaluate any Boolean gate and bootstrap simultaneously

TFHE (Chillotti et al., ASIACRYPT 2016; J. Cryptology 2020)

Torus LWE: coefficients in ℝ/ℤ (the torus 𝕋)
Gate bootstrapping in 13 ms on one CPU core (the TFHE authors measured FHEW at 690 ms)
Later work (Chillotti et al. 2021) named programmable bootstrapping: gate + function evaluation in one step
Used in: Concrete (Zama), OpenFHE

TFHE vs CKKS — choosing the right tool

Property	TFHE	CKKS
Plaintext	Bits / small integers	Reals / complex (SIMD)
Per-gate boot	Yes — automatic	No — amortised over slots
Best for	Control flow, exact logic	ML inference, statistics
Bootstrapping	~10 ms / gate (CPU)	Seconds / level refresh

GSW & the External Product

GSW Encryption (Gentry-Sahai-Waters 2013)

Encrypts message μ as a matrix C ≈ μ · G where G is a gadget matrix. Multiplication with another ciphertext uses the gadget decomposition:

C₁ ⊗ C₂ = C₁ · G⁻¹(C₂)

Noise grows linearly in the decomposition bound rather than multiplicatively — key to efficient bootstrapping.

Blind Rotation (FHEW/TFHE)

Bootstrap = evaluate f(x) = testVector[x mod N] homomorphically using a polynomial accumulator rotated by encrypted LWE coefficients:

Initialise ACC = testVector · Xᵇ ∈ RLWE
For each LWE coefficient aᵢ: ACC ← blind-rotate by aᵢ using RGSW(sᵢ)
Extract LWE sample from ACC
Key-switch back to original LWE key

Programmable bootstrapping

The testVector can encode any function f: ℤ_N → ℤ_N — including non-linear activations like ReLU — making TFHE natural for encrypted neural inference.

Bootstrapping — Noise Reset

CKKS Bootstrapping (Cheon, Han, Kim, Kim, Song — EUROCRYPT 2018)

Four steps (improved by Han–Ki, CT-RSA 2020):

ModRaise — read the exhausted ciphertext modulo the full top modulus; the plaintext becomes m + q·I for a small unknown integer polynomial I
CoeffToSlot — homomorphic DFT-like linear map that moves coefficients into slots
EvalMod — remove q·I with a polynomial approximation of a scaled sine (reduction mod q)
SlotToCoeff — inverse linear map

Bootstraps n/2 slots in parallel, so the cost is shared: 135.4 s for 65,536 slots is ~2 ms per slot on one CPU thread.

Bootstrapping cost (CKKS)

N	Slots	CPU, 1 thread	V100 GPU
2¹⁶	32768	79.4 s	328 ms
2¹⁷	65536	135.4 s	527 ms

Source: Jung et al., TCHES 2021, Table 3 (2¹⁷ set: 173-bit security, 19-bit precision). Times vary widely with library, precision and parameters — see Hardware section.

Amortisation

Bootstrapping all n/2 slots at once divides the cost: Jung et al. (TCHES 2021) bootstrap 65,536 slots in 527 ms on one V100 GPU, about 8 μs per slot.

Part III

Key Operations & Building Blocks

Relinearisation, key switching, rotation, RNS representation and NTT — the building blocks of every FHE library

Relinearisation & Key Switching

The degree problem

Multiplying ciphertexts (c₀, c₁) × (c₀', c₁') produces a degree-2 ciphertext (d₀, d₁, d₂) — decryptable only with s² in the secret key. Each further multiply increases degree.

Relinearisation (Relin)

Uses a relinearisation key rlk = Enc(s²) to homomorphically eliminate d₂, returning to degree-1 at the cost of one extra inner product with rlk.

(d₀, d₁, d₂) + d₂ · rlk → (d₀', d₁')

Key Switching

Reencrypts a ciphertext under a different secret key. Uses a key switching key ksk = Enc_{sk_new}(sk_old). Required after:

Relinearisation (degree reduction)
Galois rotations (slot rotation)
Bootstrapping key change

Cost: split the input into dnum digits, multiply each by its own key part (≈ 2·dnum NTT-domain products, plus NTTs and base conversions). Typically the bottleneck (Han–Ki 2020).

Galois Rotations

Rotating the slots by k applies the automorphism X ↦ X^e with e = 5^k mod 2N (conjugation uses e = −1), then a key switch; each rotation amount needs its own key, or is composed from power-of-two rotation keys. Required for inner products and convolutions across slots.

RNS & NTT — The Computational Engine

Residue Number System (RNS)

Large ciphertext modulus q is decomposed as product of small NTT-friendly primes:

q = q₀ · q₁ · … · q_{L-1} (each ~60 bits)

All arithmetic stays within 64-bit machine words
No multi-precision arithmetic — but modular reduction is not free: every multiply needs a Barrett or Montgomery reduction, a large share of the datapath
Modulus switching = drop one qᵢ, rescale
Used by: OpenFHE, SEAL, HElib (CKKS, BGV, BFV)

Number Theoretic Transform (NTT)

Polynomial multiplication in Rq via pointwise product in NTT domain:

a · b = INTT(NTT(a) ⊙ NTT(b))

O(n log n) vs O(n²) schoolbook
Each NTT: (n/2)·log₂n butterfly operations
Hardware: same butterfly datapath as post-quantum (ML-KEM, ML-DSA)
NTT is shared IP across FHE, PQC, ZK-SNARKs

Dominant cost breakdown

Key switching takes most of the time in HMult and rotation (Jung et al., TCHES 2021); NTTs and base conversions dominate its arithmetic. At bootstrappable parameters, memory bandwidth is often the true bottleneck (de Castro et al. 2021).

Part IV

FHE Libraries & Ecosystem

Open-source FHE libraries, standards efforts (HE-Std), and the compiler toolchain from high-level program to encrypted circuit

FHE Library Landscape

Library	Schemes	Language	Focus
Microsoft SEAL	BFV, BGV, CKKS	C++17, Python	Industry-grade, well-documented
OpenFHE	BFV, BGV, CKKS, FHEW, TFHE	C++17	Research + production; successor to PALISADE
HElib	BGV, CKKS	C++	IBM; first practical FHE library
HEAAN	CKKS	C++	Original CKKS reference (Seoul Nat'l Univ)
Concrete	TFHE	Rust + Python	Zama; compiler from Python to FHE circuit
Lattigo	BFV, BGV, CKKS, RLWE	Go	Multiparty FHE, cloud-native

HE-Std / HomomorphicEncryption.org

Open consortium of industry, government and academia. Its Homomorphic Encryption Security Standard (v1.1, 2018) gives RLWE parameters for 128/192/256-bit security — the basis for library default parameters.

Code: CKKS Encrypted Dot Product (1/2)

import seal
from seal import EncryptionParameters, scheme_type, SEALContext
from seal import KeyGenerator, Encryptor, Evaluator, Decryptor, CKKSEncoder

# ── Parameters ──────────────────────────────────────────────────────────────
parms = EncryptionParameters(scheme_type.ckks)
parms.set_poly_modulus_degree(8192)                  # n = 2^13 → 4096 slots
parms.set_coeff_modulus(seal.CoeffModulus.Create(
    8192, [60, 40, 40, 60]))                         # RNS chain: 60+40+40+60 bits
scale = 2**40                                        # Δ encodes ~12 decimal digits

ctx   = SEALContext(parms)
keygen   = KeyGenerator(ctx)
pk, sk   = keygen.create_public_key(), keygen.secret_key()
relin_ks = keygen.create_relin_keys()
gal_ks   = keygen.create_galois_keys()              # for rotations

enc  = Encryptor(ctx, pk)
evl  = Evaluator(ctx)
dec  = Decryptor(ctx, sk)
coder = CKKSEncoder(ctx)

Code: CKKS Encrypted Dot Product (2/2)

# ── Encode and encrypt two real vectors ─────────────────────────────────────
a = [1.5, 2.3, 0.7, 4.1]
b = [0.5, 1.0, 2.0, 0.25]

pt_a = coder.encode(a, scale)
pt_b = coder.encode(b, scale)

ct_a = enc.encrypt(pt_a)
ct_b = enc.encrypt(pt_b)

# ── Compute encrypted dot product via multiply-then-rotate-and-add ──────────
ct_prod = evl.multiply(ct_a, ct_b)
evl.relinearize_inplace(ct_prod, relin_ks)
evl.rescale_to_next_inplace(ct_prod)               # scale: Δ² → Δ

# Sum the 4 used slots: log-step rotate-and-add (by 1, then by 2)
ct_sum = ct_prod
for i in [1, 2]:
    ct_rot = evl.rotate_vector(ct_sum, i, gal_ks)
    ct_sum = evl.add(ct_sum, ct_rot)

# ── Decrypt ─────────────────────────────────────────────────────────────────
pt_result = dec.decrypt(ct_sum)
result = coder.decode(pt_result)

print(f"Encrypted dot product ≈ {result[0]:.4f}")  # expect ≈ 5.4750 (a·b summed)
print(f"Plaintext reference   = {sum(x*y for x,y in zip(a,b)):.4f}")

Uses Microsoft SEAL Python bindings. All arithmetic — multiply, relinearise, rescale, rotate — runs entirely on ciphertext. The server never sees a or b.

FHE Compiler Toolchain

The compilation problem

Mapping a high-level program to FHE requires:

Circuit extraction — replace branches, loops with arithmetic gates
Scheme selection — CKKS for reals, BFV/TFHE for integers/bits
Parameter generation — n, q chain, scale, levels sufficient for circuit depth
Operator scheduling — minimise bootstraps via level optimisation
Slot packing — SIMD batching across data items

Compiler projects

HEIR (Google, 2024) — MLIR-based FHE compiler; CKKS/CGGI backends, open source
Concrete (Zama) — Python to TFHE; transparent parameter selection
EVA (Microsoft) — CKKS vectoriser; automatic rescaling insertion
HECO (ETH Zürich, USENIX Security 2023) — MLIR-based; batching and rotation optimiser, SEAL back end
Cingulata / Parasol — Boolean circuit compilers for FHEW/TFHE

HEIR architecture

Source → MLIR high-level dialect → secret-type propagation → scheme selection → parameter synthesis → LLVM → CPU/GPU/FPGA

Part V

Hardware Acceleration

GPU, FPGA, and ASIC approaches — NTT units, key-switching datapaths, and the state of FHE silicon

GPU Acceleration

Why GPUs?

NTT and polynomial multiply are embarrassingly parallel — thousands of independent butterfly units map directly to GPU SIMD lanes
RNS decomposition: all qᵢ operations are independent → SIMD across RNS limbs
A ciphertext at N = 2¹⁶, L = 44 is 2·N·(L+1)·8 B ≈ 47 MB — larger than GPU L2, so HBM bandwidth, not arithmetic, sets the speed (Jung et al. 2021)

GPU libraries

cuFHE — CUDA TFHE gate bootstrapping
"100x" paper — Jung et al. (SNU, TCHES 2021), CKKS on a V100: HMult 152× and bootstrapping 257× faster than one CPU thread
PhantomFHE — CUDA library for CKKS, BFV and BGV

Benchmarks (CKKS, Jung et al. 2021)

Operation	CPU, 1 thread (ms)	V100 GPU (ms)	Speedup
HMult	2,645	17.4	152×
HRotate	2,579	16.8	153×
Rescale	145	0.64	229×
Bootstrap (2¹⁶ slots, N=2¹⁷)	135,400	527	257×

Source: Jung et al., "Over 100x Faster Bootstrapping…", TCHES 2021 (4). First three rows: Table 2 (N=2¹⁶, L=44, dnum=45, λ≈98 — below 128-bit). Bootstrap: Table 3 (N=2¹⁷, L=29, dnum=3, λ=173). Newer GPUs and libraries are faster still.

FPGA Acceleration

FPGA advantages for FHE

Custom bit-widths — word sizes chosen to map onto the DSP blocks' 27×18 multipliers (FAB uses 54-bit limbs built from them)
Deterministic latency — no OS jitter, predictable timing for real-time FHE services
Power efficiency — an integer-only datapath, with no idle floating-point units (the case made by FAB)
Reconfigurability — adapt n, q chain, or scheme per workload

Architecture: NTT unit

Radix-2 DIT butterfly with configurable twiddle factor ROM
Fully pipelined: one butterfly per cycle per unit at a few hundred MHz (FAB runs at 300 MHz)
Multi-bank memory feeds several butterfly units per cycle (at most n/2 per NTT stage)

Published results

Design	FPGA	Reported (paper abstract)
HEAX	Intel Arria 10, Stratix 10	CKKS mult + key switching 164–268× over CPU
FAB	Xilinx Alveo U280	Fully-packed CKKS bootstrapping 213× over CPU, 1.5× over GPU
FAB (8 FPGAs)	8 × Alveo U280	Logistic-regression training 456× over CPU
Poseidon	Xilinx Alveo U280	CKKS including bootstrapping

Key FPGA papers

HEAX (Riazi, Laine, Pelton, Dai — UCSD / Microsoft, ASPLOS 2020) — CKKS
FAB (Agrawal et al. — Boston Univ. / MIT, HPCA 2023) — CKKS bootstrapping
Poseidon (Yang et al., HPCA 2023) — CKKS with bootstrapping

FHE ASIC — Dedicated Silicon

ASIC vs FPGA for FHE

ASIC: better perf/area and perf/W than FPGA, from a custom memory hierarchy built for FHE data access patterns
Large on-chip scratchpads cut off-chip traffic: BTS models 512 MB at 38.4 TB/s against 1 TB/s of HBM
Custom datapath: many lanes of narrow modular arithmetic over RNS limbs (F1: 32-bit)
Fixed cost: parameter changes require full respin

Published FHE ASICs / chips

F1 (Feldmann, Samardzic et al., MICRO 2021) — first programmable FHE accelerator; 14/12 nm, 64 MB scratchpad; 5,400× (gmean) over CPU, simulated; no packed bootstrapping
BTS (Kim et al., SNU/KAIST, ISCA 2022) — bootstrappable CKKS; 7 nm, 512 MB scratchpad, simulated
CraterLake (Samardzic et al., ISCA 2022) — ASIC follow-up to F1 for unbounded depth, simulated
Intel HERACLES — DARPA DPRIVE programme; near-memory architecture

Bottleneck analysis — where silicon wins

FHE is memory-bandwidth limited: bootstrapping does under 1 op per byte and wants over 100 MB of cache (de Castro et al. 2021). ASICs put SRAM next to the NTT clusters: F1 pairs 64 MB of scratchpad and a 24 TB/s on-chip network with 1 TB/s of HBM.

Code: NTT Butterfly Unit (SystemVerilog) (1/2)

// Cooley-Tukey NTT butterfly — negacyclic, Barrett reduction
// Parameters: N=poly_degree, Q=RNS prime (30-bit here; FHE uses up to ~60), twiddle from ROM
module ntt_butterfly #(
  parameter int N     = 4096,
  parameter int Q     = 32'd1073479681,   // NTT-friendly prime: Q-1 divisible by 2N
  parameter int K     = 62               // Barrett shift: k ≥ 2·log2(Q)
)(
  input  logic        clk, rst_n,
  input  logic        valid_in,
  input  logic [63:0] a_in, b_in,        // two polynomial coefficients
  input  logic [63:0] w,                 // twiddle factor W^i mod Q from ROM
  output logic        valid_out,
  output logic [63:0] a_out, b_out
);
  // Registered pipeline: 3 stages for multiply-reduce
  logic [127:0] wb_full;
  logic [63:0]  wb_red;    // w * b mod Q via Barrett
  logic         v1, v2;

  logic [63:0]  a_d1, a_d2;  // delay a to match multiply + Barrett latency

Code: NTT Butterfly Unit (SystemVerilog) (2/2)

  // Stage 1: multiply
  always_ff @(posedge clk) begin
    wb_full <= w * b_in;              // 64×64 → 128-bit
    v1      <= valid_in;
    a_d1    <= a_in;
    a_d2    <= a_d1;                  // assumes barrett_reduce has 1-cycle latency
  end

  // Stage 2: Barrett reduction (128→64-bit mod Q)
  barrett_reduce #(.Q(Q), .K(K)) u_bar (
    .clk(clk), .in(wb_full), .out(wb_red), .valid_in(v1), .valid_out(v2)
  );

  // Stage 3: butterfly outputs
  always_ff @(posedge clk) begin
    a_out     <= (a_d2 + wb_red >= Q) ? a_d2 + wb_red - Q : a_d2 + wb_red;
    b_out     <= (a_d2 >= wb_red) ? a_d2 - wb_red : a_d2 - wb_red + Q;
    valid_out <= v2;
  end
endmodule

Fully pipelined 3-cycle butterfly. One N = 4096 NTT is (N/2)·log₂N = 2,048 × 12 = 24,576 butterflies; 8 RNS limbs make 196,608. With one butterfly unit (one per cycle at 400 MHz) that is ≈ 492 μs; with 64 units per limb (512 in all) it is 384 cycles ≈ 0.96 μs, ignoring pipeline fill and memory stalls.

Part VI

Real-World Applications

Private ML inference, genomics, regulated finance, multi-party computation, and emerging use cases

Encrypted Neural Network Inference

Problem setup

A healthcare client wants to run a diagnostic ML model hosted by a cloud provider, without revealing patient data. The cloud should learn nothing about the input or output.

CKKS NN mapping

Linear layers: encrypted matrix-vector multiply via slot rotations + inner product
Activation (ReLU): high-degree polynomial approximation (Chebyshev or composite minimax); it consumes many levels and forces many bootstraps
BatchNorm: absorbed into linear weights (pre-compiled)
Softmax: approximated; argmax via comparison circuits (expensive)

Published results

Workload (CKKS)	Platform	Time
ResNet-20, CIFAR-10 (92.43%)	CPU	10,602 s
ResNet-20, CIFAR-10	BTS ASIC (simulated)	1.91 s
Logistic-regression training, per iteration	8-thread CPU	31.0 s
Logistic-regression training, per iteration	V100 GPU	0.775 s

Sources: Kim et al., BTS, ISCA 2022, Table 6 (CPU figure from Lee et al. 2022; BTS also uses channel packing — without it the speedup is 311×); Jung et al., TCHES 2021.

Practical toolkits

CryptoNets (Microsoft 2016) — first encrypted NN demo
nGraph-HE (Intel) — TensorFlow + SEAL
Zama Concrete ML — scikit-learn + TFHE

Genomics, Finance & Private Queries

Private Genomics

GWAS — genome-wide association study over encrypted SNP data: compute χ² statistics using encrypted integer BGV
PRS (Polygenic Risk Score) — encrypted inner product of genotype × weights (CKKS, one ciphertext per chromosome)
iDASH competition — annual secure-genomics benchmark with homomorphic-encryption tracks

Regulated Finance

Private credit scoring — bank evaluates client's encrypted financial features without learning them (CKKS logistic regression)
Dark pool matching — encrypted order book matching; buyer/seller reveal nothing until match (TFHE comparisons)
Risk aggregation — Duality Technologies: FHE-based regulatory reporting across banks

Private database queries

PIR (Private Information Retrieval) — retrieve DB record without server knowing which row
CKKS + BFV for encrypted SQL-like aggregates
Spiral (Menon & Wu, IEEE S&P 2022) — fast single-server PIR built from Regev and GSW encryption

FHE + Multi-Party Computation

Why combine?

FHE gives computation on encrypted data; MPC gives distributed trust — no single party holds the full decryption key. Together: verifiable, distributed encrypted computation.

Threshold FHE

Split secret key sk among n parties: sk = sk₁ + sk₂ + … + skₙ
An additive split needs all n parties to decrypt; Shamir sharing allows t-of-n
Used in: Lattigo multiparty, OpenFHE multiparty extension
Applications: privacy-preserving ML training across hospitals with no central authority

FHE + ZK Proofs

Combine FHE with Zero-Knowledge Proofs to prove correctness of computation on encrypted data — server proves it executed the agreed function without cheating.

SNARK-based FHE verifiability (Fiore et al. 2014+)
Verifiable FHE (vFHE): prover generates succinct proof alongside FHE output
Emerging: NTT shared between FHE and PLONK/Groth16

Applications

Private federated learning with verified aggregation
Auditable encrypted cloud databases
Private on-chain smart contracts (FHE blockchains)

Part VII

Security & Standardisation

Security models, RLWE hardness assumptions, the HE-Std parameter tables, and FHE in the NIST PQC transition

FHE Security Model

IND-CPA security

All FHE schemes above target IND-CPA (indistinguishability under chosen-plaintext attack). An adversary given Enc(m₀) and Enc(m₁) cannot determine which is which with non-negligible advantage.

Warning: Standard FHE is NOT IND-CCA2 — ciphertext malleability is inherent (homomorphic operations modify ciphertext). Ordinary MACs do not survive homomorphic evaluation; integrity of a result needs verifiable computation (e.g. SNARK-based verifiable FHE).

CKKS "leakage" controversy

Li & Micciancio (2021) showed CKKS decryption reveals information beyond the intended plaintext when used in certain interactive protocols — approximate decryption leaks exact-ish values. Mitigations:

Smudging noise: add large noise before revealing decryption
Use CKKS only in non-interactive (client decrypts) settings
Li-Micciancio noise flooding countermeasure in OpenFHE

Quantum security

RLWE hardness is believed quantum-resistant — known quantum algorithms give only modest speedups for lattice problems (Shor's algorithm doesn't apply). Same assumption underlies ML-KEM/ML-DSA.

Standardisation Landscape

HomomorphicEncryption.org (HE-Std)

Homomorphic Encryption Security Standard (v1.1, November 2018), written by industry, government and academic authors. It:

Specifies BGV, BFV and GSW (and mentions CKKS)
Gives concrete RLWE parameter sets at 128/192/256-bit levels, classical and post-quantum
Computes them with the LWE estimator (Albrecht et al.)

ISO/IEC 18033-6 (2019)

International standard for partially homomorphic encryption (Paillier, El Gamal). FHE itself is being standardised as ISO/IEC 28033 (Part 1 at Draft International Standard stage). NIST has no FHE standard.

FHE in the NIST context

FHE schemes rest on the same LWE/RLWE-type assumptions as FIPS 203 (ML-KEM) and FIPS 204 (ML-DSA), which use module lattices. NIST does not set FHE parameters; FHE parameter selection follows the HE Security Standard and lattice-estimator runs.

lattice-estimator (Albrecht et al.)

Open-source Sage/Python tool for concrete security estimation of RLWE instances. Given (n, q, σ), outputs best-known attack costs (BKZ, uSVP, primal/dual hybrid). Used by all major FHE libraries to validate parameters.

Scheme Selector — Which FHE for Your Task?

Performance: FHE Today vs Tomorrow

Operation	Scheme	CPU	GPU	ASIC (simulated)
HMult (N=2¹⁶, L=44, λ≈98)	CKKS	2,645 ms (1 thread)	17.4 ms (V100)	—
Bootstrap (2¹⁶ slots, N=2¹⁷)	CKKS	135.4 s (1 thread)	527 ms (V100)	—
Gate bootstrap	TFHE	13 ms (1 core)	—	—
ResNet-20 inference	CKKS	10,602 s	—	1.91 s (BTS)
Logistic regression, 1 training iteration	CKKS	31.0 s (8 threads)	0.775 s (V100)	—

Sources: Jung et al., TCHES 2021; Chillotti et al., J. Cryptology 2020; Kim et al. (BTS), ISCA 2022. Each row is from one paper; rows are not directly comparable.

Still far from plaintext

Even on a GPU an encrypted multiply takes milliseconds, against nanoseconds in plaintext. DARPA's DPRIVE programme set the goal of FHE within 10× of plaintext speed — a target for dedicated silicon. Today FHE suits high-value, privacy-critical work.

Trend: closing fast

2009 (Gentry): theoretical only
2012: AES-128 in 36 hours (≈ 40 min per block, batched; Gentry–Halevi–Smart)
2018: minutes per NN inference
2021–22: simulated ASICs (F1, BTS) — ResNet-20 in ~2 s
Goal: real-time encrypted ML

Limitations & Open Problems

Current limitations

No native comparison — equality/order tests require expensive bit-decomposition or polynomial approximation in CKKS
No native branching — FHE circuits must be branch-free (TFHE mitigates via bit-level gates)
Large ciphertext expansion — a CKKS ciphertext is ~0.45 MB at N = 2¹³ (218-bit q) and ~47 MB at N = 2¹⁶, L = 44; amortised only when its n/2 slots are well packed
Key material size — one key-switching key at N = 2¹⁶ is ~0.2–2 GB depending on dnum, so a full set of rotation keys can reach tens of GB
Parameter tuning complexity — non-expert users struggle; compilers help but don't solve all cases

Open research problems

Efficient bootstrapping — target <1ms per CKKS bootstrap at high precision
Transciphering — convert AES-encrypted stream to FHE ciphertext homomorphically (reduces client bandwidth)
FHE-native NNs — train networks with polynomial activations that are FHE-efficient from the start
Multiparty FHE at scale — distributed decryption without trusted dealer
Functional encryption — a related primitive: a key reveals only f(x), not x

FHE Ecosystem (2025)

Commercial

Zama — Concrete / fhEVM; FHE blockchain, ML
Duality Technologies — OpenFHE commercialisation; finance/healthcare
Cornami — FHE streaming ASIC
Microsoft — SEAL, HEAX
Intel — HERACLES chip, HEXL acceleration library
IBM — HElib, homomorphic encryption services

Research groups

MIT CSAIL — F1, CraterLake
Seoul Nat'l Univ — HEAAN/CKKS; BTS design (with KAIST)
EPFL — Lattigo; multiparty FHE
Boston Univ. / MIT — FAB FPGA accelerator
ETH Zürich — HECO compiler

Standards / consortia

HomomorphicEncryption.org — parameter standards
FHE.org — community & annual FHE.org conference
OpenFHE governance board

Summary & Future Directions

What we covered

Foundations — LWE, RLWE, noise growth, cyclotomic rings
Schemes — BGV, BFV, CKKS, TFHE/FHEW: tradeoffs and selection
Operations — relinearisation, key switching, RNS, NTT
Hardware — GPU (100–250× over one CPU thread), FPGAs (HEAX, FAB, Poseidon), ASICs (F1, BTS, CraterLake)
Applications — private ML, genomics, finance, MPC+ZK
Limits — no branches, ciphertext expansion, key size

Watch this space

FHE-native AI chips — dedicated ASIC for real-time encrypted inference
FHE blockchains — fully private smart contracts (fhEVM)
Transciphering at scale — remove AES pre-processing overhead
FHE standardisation — ISO/IEC 28033 in draft
Quantum + FHE — FHE security assumptions robust to quantum; synergy with QKD?

Series connection

FHE builds on: 07 PQC (RLWE), 01 Finite fields (NTT), 10 Hardware (NTT ASICs), 09 Side-channel (power attacks on FHE chips)

References

Foundational papers

Gentry, "A Fully Homomorphic Encryption Scheme," Stanford PhD thesis (2009)
Regev, "On Lattices, LWE, Random Linear Codes…" STOC (2005)
Lyubashevsky, Peikert, Regev, "On Ideal Lattices and RLWE" EUROCRYPT (2010)
Brakerski, Gentry, Vaikuntanathan (BGV), "(Leveled) Fully Homomorphic Encryption without Bootstrapping" ITCS (2012)
Brakerski, "Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP" CRYPTO (2012)
Fan, Vercauteren (BFV), "Somewhat Practical Fully Homomorphic Encryption" ePrint 2012/144
Bajard, Eynard, Hasan, Zucca, "A Full RNS Variant of FV-like SHE Schemes" SAC (2016); Halevi, Polyakov, Shoup, "An Improved RNS Variant of BFV" CT-RSA (2019)
Cheon, Kim, Kim, Song (CKKS), "Homomorphic Encryption for Arithmetic of Approximate Numbers" ASIACRYPT (2017)
Ducas, Micciancio (FHEW), "FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second" EUROCRYPT (2015)
Chillotti, Gama, Georgieva, Izabachène (TFHE), ASIACRYPT (2016); "TFHE: Fast Fully Homomorphic Encryption over the Torus" J. Cryptology (2020)
Cheon, Han, Kim, Kim, Song, "Bootstrapping for Approximate Homomorphic Encryption" EUROCRYPT (2018)
Gentry, Sahai, Waters (GSW) CRYPTO (2013)
Li, Micciancio, "On the Security of Homomorphic Encryption on Approximate Numbers" EUROCRYPT (2021)

Hardware & systems

Feldmann, Samardzic et al. (F1), MICRO 2021
Kim et al. (BTS), ISCA 2022
Samardzic et al. (CraterLake), ISCA 2022
Agrawal et al. (FAB), HPCA 2023
Riazi, Laine, Pelton, Dai (HEAX), ASPLOS 2020
Yang et al. (Poseidon), HPCA 2023
Jung et al., "Over 100x Faster Bootstrapping in FHE through Memory-centric Optimization with GPUs" TCHES 2021
de Castro et al., "Does Fully Homomorphic Encryption Need Compute Acceleration?" arXiv 2112.06396 (2021)
Viand, Jattke, Haller, Hithnawi (HECO), USENIX Security 2023
Han, Ki, "Better Bootstrapping for Approximate Homomorphic Encryption" CT-RSA 2020
Homomorphic Encryption Security Standard v1.1, HomomorphicEncryption.org (2018)
Albrecht et al., "Estimate all the {LWE, NTRU} schemes!" SCN (2018) — lattice-estimator

← Back to series landing page

Fully HomomorphicEncryption

The Holy Grail of Cryptography

🔴 Traditional Cloud

🟢 FHE Cloud

Homomorphic Encryption Taxonomy

Why depth matters

Mathematical Foundations

Learning With Errors (LWE)

The LWE Problem

Why error?

Security

Ring-LWE — Compact & Efficient

Polynomial Ring

RLWE Sample

Why xⁿ + 1?

Parameters

Noise Growth — The Central Challenge

Noise after operations

Decryption failure

Noise management techniques

FHE Scheme Landscape

Gentry's Blueprint (2009)

The Breakthrough

Squashing trick

Bootstrapping in one line

Historical impact

BGV & BFV — Integer Arithmetic

BGV (Brakerski-Gentry-Vaikuntanathan 2011)

BFV (Fan-Vercauteren / Brakerski 2012)

BGV vs BFV — practical guidance

CKKS — Approximate Real Arithmetic

Cheon-Kim-Kim-Song (2017)

CKKS SIMD packing

Best for

TFHE & FHEW — Fast Gate-Level FHE

FHEW (Ducas-Micciancio 2015)

TFHE (Chillotti et al., ASIACRYPT 2016; J. Cryptology 2020)

TFHE vs CKKS — choosing the right tool

GSW & the External Product

GSW Encryption (Gentry-Sahai-Waters 2013)

Blind Rotation (FHEW/TFHE)

Programmable bootstrapping

Bootstrapping — Noise Reset

CKKS Bootstrapping (Cheon, Han, Kim, Kim, Song — EUROCRYPT 2018)

Bootstrapping cost (CKKS)

Amortisation

Key Operations & Building Blocks

Relinearisation & Key Switching

The degree problem

Relinearisation (Relin)

Key Switching

Galois Rotations

RNS & NTT — The Computational Engine

Residue Number System (RNS)

Number Theoretic Transform (NTT)

Dominant cost breakdown

FHE Libraries & Ecosystem

FHE Library Landscape

HE-Std / HomomorphicEncryption.org

Code: CKKS Encrypted Dot Product (1/2)

Code: CKKS Encrypted Dot Product (2/2)

FHE Compiler Toolchain

The compilation problem

Compiler projects

HEIR architecture

Hardware Acceleration

GPU Acceleration

Why GPUs?

GPU libraries

Benchmarks (CKKS, Jung et al. 2021)

FPGA Acceleration

FPGA advantages for FHE

Architecture: NTT unit

Published results

Key FPGA papers

FHE ASIC — Dedicated Silicon

ASIC vs FPGA for FHE

Published FHE ASICs / chips

Bottleneck analysis — where silicon wins

Code: NTT Butterfly Unit (SystemVerilog) (1/2)

Fully Homomorphic
Encryption