CKKS スキーム (HEAAN)

CKKS スキーム

Cheon-Kim-Kim-Song が論文「Homomorphic Encryption for Arithmetic of Approximate Numbers」で提案した、実数・複素数の近似演算に特化した準同型暗号。実装名から HEAAN とも呼ばれる。固定小数点演算をネイティブに扱えるため機械学習応用の主流。

エンコード

$N/2$ 次元の複素ベクトル $z$ を、スケーリングファクタ $\Delta$ を掛けて多項式環 $\mathcal{R}=\mathbb{Z}[X]/(X^N+1)$ の元へ写す:

$m(X)={\sigma }^{-1}(\lfloor \Delta \cdot {\pi }^{-1}(z)\rceil )$

$\sigma$ は標準埋め込み（Vandermonde 行列で表せる）。$\Delta$ が大きいほど精度が上がる代わりにノイズ余裕を食う。

スキーム

• 鍵生成はRing-LWE 性 $b+as=e$ を満たす pk と、$s^2$ を暗号化した evk を持つ。
• Add: $\mathrm{ct}+{\mathrm{ct}}^{\prime }$
• Mult: 暗号文を掛けると 3 成分になるので evk でrelinearizeして 2 成分へ。
• Rescale: 乗算後に modulus chain $q_{\ell }=p^{\ell }$ を 1 段降り、スケールを $\Delta$ に戻してノイズを抑える。レベルを消費する。
• Rotation / Conjugation: $\{1,5,\dots \}$ が ${\mathbb{Z}}_{2N}^{\times }$ の部分巡回群をなすことを使い、$Y\mapsto Y^5$ で slot を回転。回転鍵 rk・共役鍵 ck が必要。

RNS variant

係数をRNS（中国剰余定理）表現で複数の機械語素数に分解し、多倍長演算を排して高速化する。実装はほぼこの RNS-CKKS を使う。

Bootstrapping

CKKS は本来 leveled だが、復号写像 $[t{]}_q$ を $S(t)=\frac{q}{2\pi }\sin (\frac{2\pi t}{q})$ で近似評価して FHE 化する。詳細は fhe-bootstrapping。CoeffToSlot→EvalExp→SlotToCoeff の流れで、線形変換は BSGS で最適化する。

安全性の注意

近似であるため復号結果がノイズを漏らす攻撃が指摘されている（On the Security of HE on Approximate Numbers）。

実装: Microsoft SEAL。関連クラスタ: _moc-crypto