整数演算のためのBGVとBFV方式

BGV（Brakerski-Gentry-Vaikuntanathan、2012）は、RLWEに基づくレベル型FHE方式です。パックされた整数平文に対して、任意の加算と乗算を実行できます。レベル型とは、ブートストラッピングなしで、固定された深さLまでの回路を処理できるという意味です。

BGVとBFVでは、平文をZ_t[x]/(x^n+1)の多項式として符号化します。ここでtは小さい平文法です（例: t=65537）。各多項式は、係数ごとに1つ、n個の整数値を符号化します。暗号文に対する演算はn個すべての値に同時に適用され、SIMD並列性が実現されます。

BGVでは、モジュラススイッチングによってノイズを低減します。各乗算の後、暗号文の法qをQ_LからQ_{L-1}に減らします。これによりノイズがQ_L/Q_{L-1}で割られ、復号可能な範囲に収まります。回路の深さLは、L個のモジュラスレベルに対応します。

BFV（Brakerski/Fan-Vercauteren、2012）はBGVに似ていますが、異なるノイズ管理戦略であるスケール不変方式を使用します。BFVではモジュラススイッチングは必要ありません。代わりに、乗算後に暗号文を再スケーリングします。実装がより簡単で、Microsoft SEALで使用されています。

平文環上の中国剰余定理により、各暗号文にn/2個の独立した整数値（スロット）を格納できます。暗号文の加算操作では、n/2個の組をすべて並列に加算します。乗算では、すべての組を乗算します。スループットは、暗号文操作1回あたりn/2個の整数演算です。

次数1の暗号文を2つ乗算すると、結果は次数2（3つの成分）になります。再線形化では、評価鍵（relin keys）を使用して、ノイズの増加というコストを伴いながら次数1に戻します。この手順は、乗算のたびに必要です。

from seal import EncryptionParameters, scheme_type, SEALContext, KeyGenerator, Encryptor, Evaluator, Decryptor parms = EncryptionParameters(scheme_type.bfv) parms.set_poly_modulus_degree(4096) parms.set_coeff_modulus(CoeffModulus.BFVDefault(4096)) parms.set_plain_modulus(PlainModulus.Batching(4096, 20))

暗号文の回転では、n/2個の平文スロットを巡回シフトします。これは、スロットの総和を1つに集約するsum-reduce、回転と累積による行列ベクトル積、シフトと乗算による畳み込みに役立ちます。Galois keys（事前計算された回転キー）が必要です。

n=8192のBFVでは、加算は約10 µs、乗算は約5 msです（再線形化を含む）。必要な場合のブートストラッピングには30-60秒かかります。4096個の整数をバッチ処理すると、乗算1回あたり整数1個の償却コストは約1 µsです。リアルタイム処理には実用的ではありませんが、オフライン分析には利用できます。

nとqを選ぶ際、SEALではQ < 2^109の128ビットセキュリティにn=4096、大規模な回路にn=8192を推奨しています。HE標準（homomorphicencryption.org）にはパラメータ表が用意されています。必ず推奨パラメータを使用してください。独自の選択によって、セキュリティが簡単に損なわれる可能性があります。

暗号化データベースクエリでは、復号せずに暗号化されたレコードを検索できます。プライベートゲノム解析では、暗号化されたDNAに対して統計を計算できます。暗号化された金融集計では、個々の残高を見ずに暗号化された口座残高を合計できます。安全なモデル評価にも利用できます。

BGVは、乗算後のノイズの増加を管理するためにどのような手法を使用しますか？

BGVとBFVは、RLWEを使用して暗号化された整数演算を実行します。バッチ符号化によってSIMD並列性が得られます。BGVはモジュラススイッチングを使用し、BFVはスケール不変方式を使用します。再線形化によって、乗算後の次数を元に戻します。次は、近似演算とMLのためのCKKSについて学びます。