FHE Bootstrapping

暗号文に溜まったノイズを、復号写像そのものを準同型評価することでリセットし、ふたたび乗算可能な状態へ戻す操作。Gentry が初めて示した FHE 化の鍵で、これにより leveled HE が任意深さの回路を扱える真のFHEになる。

CKKS の bootstrapping

CKKS の recryption は次の流れ（Cheon らの 2018 論文）:

MODRAISE → COEFFTOSLOT → EVALEXP → IMGEXT → SLOTTOCOEFF

• Modulus raising: $\mathrm{ct}(\mathrm{mod}q)$ を大きな modulus $Q_0$ へ持ち上げると $t=qI+m$ の形になる。
• CoeffToSlot: 係数表現 $(t_0,\dots ,t_{N-1})$ を slot へ移す線形変換。
• EvalExp: 復号の剰余 $[t{]}_q$ を直接評価できないので $S(t)=\frac{q}{2\pi }\sin (\frac{2\pi t}{q})$ で近似。$\exp (i\theta /2^r)$ を $r$ 回 2 乗する 2 倍角公式で実装する。
• SlotToCoeff: 逆変換で元へ戻す。

誤差は $|F(t)-S(t)|=\mathcal{O}(q\cdot |m{|}^3/q^3)$（マクローリン展開 $x-\sin x<x^3/3!$ より）。

高速化の系譜

• Better Bootstrapping: Taylor は高次で不安定なので回避。
• Improved Bootstrapping: Chebyshev 補間で深さを最適化、CoeffToSlot を FFT 風に分解。Lattigo v2 に実装。
• Non-Sparse Keys（2021）: 多項式評価・key-switch を最適化し double-hoisting を導入、約 14 倍高速。
• GPU / memory-centric: モジュラ乗算をメモリ中心に最適化し 100 倍超の高速化。

線形変換（CoeffToSlot/SlotToCoeff）はbaby-step giant-step (BSGS)で回転回数を減らすのが定石。TFHE の bootstrapping は逆にビット単位で頻繁に回し、関数評価も兼ねる（programmable bootstrapping）。

関連クラスタ: _moc-crypto