Anatomy of CKKS Bootstrapping

Topics We'll Cover

• Why Bootstrap, and the Four Steps
• ModRaise
• CoeffToSlot: A Homomorphic DFT
• Baby-Step Giant-Step Rotations
• EvalMod: Modular Reduction as a Polynomial
• SlotToCoeff
• Where the Levels Go
• Operation Counts per Stage
• The Data-Movement Profile
• Interactive: Stage Breakdown
• Algorithmic Levers
• Checked Against a Real OpenFHE Bootstrap
• What to Take Away

Why Bootstrap, and the Four Steps

Each multiplication consumes a level (deck 01). When a ciphertext reaches level 0 it cannot be multiplied again. Bootstrapping homomorphically evaluates (an approximation of) decryption to produce an equivalent ciphertext at a high level. For CKKS the standard pipeline is that of Cheon, Han, Kim, Kim and Song (EUROCRYPT 2018, ePrint 2018/153), refined by Han & Ki (ePrint 2019/688) and Bossuat et al. (EUROCRYPT 2021, ePrint 2020/1203):

The orange stages are rotation-heavy and key-hungry; EvalMod is multiplication-heavy and reuses one relinearisation key. That difference drives everything in decks 03–05.

ModRaise

• What: reinterpret a level-0 ciphertext (one limb, modulus q₀) modulo the full Q. Decrypting it now gives m + q₀·I for a small integer polynomial I; the rest of bootstrapping exists to remove q₀·I.
• Cost: cheap. iNTT the single limb of both polynomials, then NTT the coefficients into all L+1 limbs: 2 + 2(L+1) = 50 limb transforms for the ark set, no key switch.
• Sparse packing: with fewer slots than N/2, a SubSum of log₂(N/2 / slots) rotations follows. OpenFHE's 8-slot configuration in our calibration does 12 of them.

CoeffToSlot: A Homomorphic DFT

Encoding uses a DFT-like map (the canonical embedding). To operate on the polynomial's coefficients, which is where q₀·I lives, bootstrapping applies the inverse encoding map homomorphically.

• As a matrix, the map is dense, (N/2)×(N/2). Evaluated naively through its diagonals it would need N/2 rotations.
• FFT factorisation: like any FFT it factors into log₂(N/2) = 15 sparse stages. Merging stages into a radix-2^k step gives 2^k+1−1 non-zero diagonals per step, at one level per step.
• The trade-off: the ark set merges 15 stages into 3 levels of radix 2⁵, giving 63 diagonals per level. Fewer levels means more rotations per level; more levels means fewer rotations but fewer levels left for the application.
• Each diagonal is a plaintext (12 MiB at the top level) that is multiplied in, and each rotation needs its own evaluation key.

ARK (arXiv:2205.00922) quotes the same structure: with k = 5 over 3 levels, "40 HRots and 158 PMults" per homomorphic DFT. The companion model, without ARK's further optimisations, does 43 and 189.

Baby-Step Giant-Step Rotations

A matrix-vector product with d diagonals needs d rotations if done directly. BSGS splits d = n₁ × n₂: rotate the input n₁−1 times (baby steps), form n₂ inner sums with pre-rotated diagonals, and rotate each sum once (giant steps).

• Hoisting (Halevi & Shoup, CRYPTO 2018, ePrint 2018/244): the baby steps rotate the same ciphertext, so its decomposition and ModUp are done once and shared, which saves NTTs. The keys are still all different.
• Every rotation amount is a distinct key: 14 keys per level here, 43 across CoeffToSlot. This is the pattern ARK's Min-KS attacks (slide 11).

EvalMod: Modular Reduction as a Polynomial

After CoeffToSlot the slots hold the coefficients t = m + q₀·I (scaled). EvalMod computes t mod q₀, which is not a polynomial, so it is approximated: (q₀/2π)·sin(2πt/q₀) is close to t mod q₀ when m is small. In practice this means a scaled cosine evaluated with Chebyshev polynomials, followed by double-angle steps cos(2x) = 2cos²x − 1.

• Two copies for full slots. After CoeffToSlot a conjugation (one more rotation) splits the real and imaginary parts, and EvalMod runs on each: 36 HMults in total.
• One key, reused 36 times: the relinearisation key. EvalMod is NTT-heavy and cache-friendly, the opposite of the DFT stages.
• The degree, the double-angle count and the use of a sine or cosine are accuracy choices; libraries differ. OpenFHE v1.5.1 with uniform ternary keys uses an 89-coefficient (degree-88) Chebyshev series and six double-angle steps, read from its source and confirmed by its recorded trace (slide 12).

SlotToCoeff

• What: the forward encoding DFT, homomorphically, taking the corrected coefficients back to slots. It has the same BSGS structure as CoeffToSlot: 3 levels, 42 rotations (no conjugation) and 189 plaintext multiplies in the ark set.
• Cheaper per operation: it runs after EvalMod, at levels 10 down to 8, where a key needs only 2 of its 4 digits and 15–17 of its 30 limbs. Its key traffic is 1.41 GB against 5.22 GB for CoeffToSlot.
• Why ordering matters: moving the expensive DFT to the bottom of the level ladder is a standard optimisation. It changes the data-movement profile far more than it changes the operation count.

Where the Levels Go

• Bootstrapping is expensive per useful level. With 7 levels left, a deep computation bootstraps every 7 multiplications. The cost per useful level is the number that matters to applications (ARK and 100x use an amortised metric, T_A.S., for this reason).
• Bigger L buys more useful levels but makes every ciphertext, key and transform bigger, and pushes up PQ against the security bound.
• These level counts come from the companion trace generator. A test checks them against the closed form CtS + (2 + ⌈log₂(b−1)⌉ + ⌈log₂g⌉ + r) + StC where g is a power of two; for the two OpenFHE rows they equal the bootstrap depth OpenFHE itself reports (16 and 20).

Operation Counts per Stage

One full-slot bootstrap of the ark set, baseline algorithm (hoisted BSGS). "Requested" bytes are what the operations need, before any on-chip reuse; deck 03 turns them into actual HBM traffic.

• 203 HE operations, 85 rotations, 36 multiplications, 378 plaintext multiplies and 13,710 limb transforms (7.2 billion butterflies) per bootstrap.
• EvalMod has the most transforms, but its 2.66 GB of key requests are all the same key; the DFT stages' 6.6 GB are 85 different keys.

The Data-Movement Profile

Interactive: Stage Breakdown

"All three" is Min-KS + seeded keys + on-the-fly plaintexts (slide 11). This runs the simulator's trace generator in the browser (the same JavaScript that powers deck 03) and counts operations and requested bytes per stage. No timing here, only the workload.

Algorithmic Levers

Each technique changes the workload, not the hardware. Effects on one ark-set bootstrap, from the companion trace generator:

Min-KS, seeded keys and on-the-fly plaintexts trade arithmetic for bytes; OpenFHE's BSGS trades bytes for arithmetic; SlotToCoeff first saves both. Whether that wins depends on whether the design is memory-bound or compute-bound, which is exactly what the simulator in deck 03 decides.

Checked Against a Real OpenFHE Bootstrap

OpenFHE v1.5.1 was instrumented (an 82-line patch) to log every NTT, base conversion, key switch, automorphism, rescale and plaintext multiply of a bootstrap. Below is N = 2¹⁴, 8,192 slots, level budget {3, 3}, dnum 3, against the model at the same parameters, run with the default (balanced) BSGS split and with OpenFHE's. Each cell reads OpenFHE / model / model with OpenFHE's BSGS (HMults: OpenFHE / model).

• Agrees exactly where the algorithms agree. Bootstrap depth is 20 in both, and in the N = 2¹⁶, 8-slot recording the 12 SubSum rotations match OpenFHE on keys and key bytes exactly, and on transforms to within 3%.
• The DFT split was the big difference. OpenFHE keeps rotated ciphertexts in the extended Q·P basis and uses many more baby steps (16 against 8 per radix-2⁵ level). Modelling that (slide 11) brings transforms to within 20%.
• EvalMod differs by library policy. OpenFHE's FLEXIBLEAUTO scaling rescales copies of each input before every multiplication: 542 polynomial rescales for 48 HMults, against 2 per HMult in the model. That roughly doubles its EvalMod transforms. An accelerator compiler would rescale once, so the model keeps that schedule and the difference is documented and tested.

What to Take Away

• Four stages: ModRaise (cheap), CoeffToSlot and SlotToCoeff (homomorphic DFTs: rotations, distinct keys, plaintexts) and EvalMod (a polynomial: multiplications, one key).
• BSGS turns a 63-diagonal level into 14 rotations; hoisting shares the ModUp; the keys stay distinct.
• Levels: the ark set spends 16 of 23 levels bootstrapping, leaving 7.
• Per bootstrap: 203 HE ops, 85 rotations, 36 HMults, 13,710 limb transforms, and about 9.3 GB of keys and 3.3 GB of plaintexts requested.
• Two personalities: the DFT stages stream data, EvalMod computes. Simulate the sequence, not the totals.