大規模な暗号化データに準同型演算を適用する
現在、PALISADEライブラリを使用して準同型暗号化を実験しています。
大きな暗号化された入力に加算や乗算などの単純な彼の操作を適用したいと思います。たとえば、入力A[3200]と入力のB[4096]両方のint値のベクトル/配列が暗号化されます。これら2つの入力を持つEnc(A)とEnc(B)私は乗算を適用します：
EvalMult(Enc(A[0]), Enc(B[42]))
*0 and 42 denoting the indexes of the corresponding inputs
** no SIMD needed
私に関する限り、上記の要件の実装は、2つの異なる方法で解決できます。
入力を単一の暗号文（SIMDのような）にパックし
EvalIndexAt()、暗号化された入力から適切な値を取得するために使用できる操作を行います。AとBの各値を個別に暗号化します。
説明されているソリューションのどれが効率の点で最良であるかはよくわかりません。最初のアプローチには、入力全体に対して1つの暗号化プロセスのみが必要であるというこの大きな利点がありますが、これには、EvalAtIndex()メソッドを使用して常に正しい要素にアクセスする必要があり、入力が大きいほど取得の計算が遅くなるという欠点がありEvalAtIndexKeyGen()ます。（少なくとも私のマシンでは）
2番目のアプローチEvalAtIndex()は必要ないため、より適切に見えますが、各値を個別に暗号化するコストがかかり、かなりの時間がかかります。
何か考えの推奨事項はありますか？
回答
質問ありがとうございます。
アプローチ＃1（SIMD）の主な利点は、単一の準同型加算または乗算（非常に効率的）を使用して、（4096以上の整数/実数の）ベクトルの加算および乗算を実行できることです。ローテーション（EvalAtIndexPALISADEで呼ばれる）は、個々のインデックスにアクセスしたり、効率的な合計（内積の場合のように）、行列の乗算などを実行したりできる追加の操作です。このアプローチでは、暗号化テキストの拡張係数が（4096倍以上）はるかに小さくなります。アプローチ＃2。通常、実際にはオプション＃1が推奨されます（オプション＃2を使用したい実際のユースケースは考えられません）。
乗算のコストを最小限に抑えるために、ベクトルを連続したブロックにパックして、1つのブロックに対して1回の回転が必要になるようにすることができます。例えば、
EvalMult(Enc(A[0:5]),Enc(B[42:47))
使用できるもう1つの手法は、EvalFastRotation（PALISADE v1.10.xのCKKSおよびBGVrnでのみ使用可能）です。同じ暗号文の複数のローテーションが必要な場合は、暗号文用に何かを事前に計算してから、より安価なローテーションを使用できます（BVキーの切り替えで最大のメリットが得られます）-を参照してください。https://gitlab.com/palisade/palisade-development/-/blob/master/src/pke/examples/advanced-real-numbers.cpp 例として。
複数の回転が必要な場合に生成されるキーの数を最小限に抑える方法もあります（必要な回転数の平方根のみを計算します）。たとえば、で説明されているbaby-step-giant-step手法を使用します。 https://eprint.iacr.org/2018/244 （これらの手法は、PALISADEベースのアプリケーションに実装できます）。
乗算を実行するパターンがわかっている場合は、ベクトルをパックする特別な順序を使用することもできます（このようにして、回転は1回の回転操作を使用してベクトル全体に複数のブロックを準備します）。＃プレーンテキストスロット（バッチサイズ）がring dimension/ 2に等しい場合、回転はCKKSとBGVrnsの両方で周期的（ラップアラウンド）です。それよりも小さいベクトルがある場合は、いつでも必要な回数だけ小さいベクトルを複製/複製できます。満たすring dimension/ 2。
要約すると、SIMDのようなベクトルの観点から問題を考えると、最大の効率改善を達成できます。次に、問題/モデルを再定式化して、HEが提供するツールセットを最大限に活用できます。ある意味で、これは、AVXなどのベクトル化された命令を使用したプログラミング、または（MATLABのような）行列指向プログラミングに似ています。