近似算術と機械学習のためのCKKS

BGV/BFVは整数上で動作し、厳密な演算を行います。機械学習では、浮動小数点数による近似演算を使用します。CKKS（Cheon-Kim-Kim-Song、2017）は実数や複素数を符号化し、精度の損失を制御できます。そのため、ML推論やデータ分析に適しています。

CKKSでは、ノイズを符号化精度の一部として扱います。ノイズを除去して誤り訂正するのではなく、CKKSは結果を、精度の保証範囲を持つ近似値として扱います。このトレードオフにより、連続値の計算に対して、より効率的なHEが可能になります。

CKKSでは、複素数ベクトルを多項式として符号化します。ベクトル(z_0, ..., z_{n/2-1})は、逆FFTによってR上の多項式に写像されます。スケーリング係数Δ（例: 2^40）によって、浮動小数点数を整数に写像します。1つの暗号文にはn/2個の実数スロットがあります。

乗算後、スケーリング係数は二乗されてΔ^2になります。CKKSでは再スケーリングを行い、Δで割って単一のスケーリングに戻します。これにより、BGVのモジュラススイッチングと同様に暗号文のモジュラスレベルも下がり、暗号文を扱いやすい状態に保ちます。

乗算を1回行うごとにモジュラスレベルを1つ消費し、精度が約log2(Δ)ビット低下します。スケーリング係数Δ = 2^40で深さLの回路を処理する場合、精度の総損失は約L*40ビットです。この精度の予算を収容できるように、初期法Qを十分に大きく選択してください。

線形層（行列ベクトル積）は、回転と累積によって効率的に処理できます。活性化関数（ReLU、sigmoid）には、多項式近似が必要です。ReLUは7次のチェビシェフ多項式で近似します。精度の損失は、平文での推論と比べて約0.1-1%です。

病院はCKKS公開鍵を使って患者データを暗号化します。クラウドはCKKSの演算を使い、暗号化されたデータに対して診断用ニューラルネットワークを実行します。暗号化された予測結果を返します。病院は秘密鍵で復号します。クラウドが患者データや平文の診断結果を見ることはありません。

HEAAN/OpenFHEでは、深いML回路に対してn=2^15（32768）を推奨しています。モジュラスチェーンは、Δ=2^50で30段の乗算レベルを処理する場合、初期Q ≈ 2^1500です。セキュリティは、これらのパラメータを使用するCKKSがRLWEと同程度に困難であると仮定して、128ビットです。メモリ使用量は暗号文1つあたり約1 MBです。

CKKSのブートストラッピング（Cheon et al.、2018）では、剰余還元を準同型的に評価して暗号文をリフレッシュします。計算量の大部分は、複素数上で正弦関数を多項式近似によって評価することにあります。ブートストラッピング1回あたり約30秒で、回路の深さを無制限にできます。

BFV: 正確な整数、整数平文、精度の損失なし。CKKS: 近似的な実数/複素数、浮動小数点平文、深さに応じて精度が低下。BFVはデータベース、クエリ、厳密な計算に使用します。CKKSはML、統計、科学技術計算に使用します。

HEAAN（元祖CKKS、Seoul National University）。Microsoft SEAL（CKKS + BFV）。OpenFHE（CKKS + BGV + BFV）。Concrete-ML（Zama.ai、scikit-learnおよびPyTorchモデル向けにOpenFHEをラップ）。TF-HE（TensorFlow + HE統合の実験）。

機械学習の推論で、CKKSがBFVより好まれるのはなぜですか？

CKKSは近似的な実数演算をサポートし、暗号化データに対するML推論や統計に適しています。再スケーリングによってスケーリング係数を管理し、活性化関数は多項式近似で置き換えます。次は、耐量子暗号、つまりShorのアルゴリズムとGroverのアルゴリズムについて学びます。