技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

学習リソース:
完全準同型暗号 I: 理論と基礎 (上海交通大学の Yu Yu 先生)
完全準同型暗号 II: 完全準同型暗号の理論と構築 (教師 Xiang Xie)

---

現在、第 2 世代 (BGV や BFV など) と第 3 世代の完全準同型暗号化方式はすべて LWE に基づいています。現在、高度な完全準同型暗号化方式も LWE に基づいているため、この記事では LWE の基礎知識をまとめます。
まず、数値を暗号化したいと考えます。$s$、現在は一連のを使用しています${1つの}_{私}$右$s$暗号化して取得する${1つの}_{私}s$、実際には、最大公約数 GCD を解くことで解決できます。$s$ 。ただし、ランダムノイズが加わると$e_{私}$、得る${1つの}_{私}s+e_{私}$、それなら解決するのは難しいでしょう$s$価値。このプロセスは、LWE についての私の単純な理解です。いわゆるエラーはノイズです。

完全準同型暗号の計算プロセスは、鍵生成KeyGen、暗号化Enc、準同型計算Eval、復号Decの3ステップに分かれます。 、

キージェネレーション：

まず上記の方程式を構築します。$s\cdot あ+e=sあ+e$、公開キー pk を取得します ($-あ$そして$sあ+e$スプライシング)、および秘密鍵 sk ($s$および1)。したがって、pkとskの乗算結果はランダムノイズe(0に近い)となる。

添付：

暗号化に使用される公開鍵 pk、r は 0 または 1 のみを含むランダムなベクトル、m は暗号化される情報 (ベクトルの最下位ビットに入れられます) です。

12月：

復号に使用した秘密鍵 sk と ct の内積を計算した後、mod 2 を求めて復号結果を取得します。

正しさの証明:

sk と pk を乗算して 2e (KeyGen が満たした条件) を取得し、次に r と内積を実行して小さな均一ノイズを取得します。最終結果は m+ 小さな均一ノイズなので、ノイズは mod 2 で除去できます。復号結果 m を取得します。これが、構築されたノイズが e ではなく 2e である理由です。私の理解では、偶数のランダム ノイズを構築することで、復号化中にノイズを除去するために mod 2 を使用すると便利です。

安全性の証明:

pk が擬似ランダムで、r のエントロピーが十分に高い (つまり、ランダム性が強い?) 場合、pk と pk に r を掛けたものは両方とも擬似ランダムです。自然とベクトルを m で加算した後の暗号化結果も擬似ランダムになります。

以下は、Xiang Xie 先生の定型的な説明です。
暗号化の式: 暗号文 c = 公開鍵 pk ✖️ ランダム r + 平文 m
復号式: 平文 m = <暗号文 sk, 秘密鍵 sk> mod q mod 2

これに基づいて、mod 2 を使用して平文 m の値を復号化できます。ノイズが十分小さい限り、精度は保証されます。
ここで区別する必要があるものがあります: 上記$ポけ=(あ,b=あs^{\prime }+2e)$は BGV ソリューションであり、BFV は$ポけ=(あ,b=あs^{\prime }+e)$の違いは、BGV は情報を下位ビットでエンコードするのに対し、BFV はメッセージを上位ビットでエンコードすることです (BFV を学習するときに説明します)。

Eval (加法準同型性と乗法準同型性):

準同型加算または乗算はかなりのノイズの蓄積をもたらし、乗算は二次的な増加傾向があることに注意してください。
次に、準同型乗算の結果を復号する方法について説明します。次の式がわかります。2 つの暗号文の乗算は、暗号文と秘密鍵のテンソル積をそれぞれ計算し、内積を計算することと同じです。したがって、明らかに暗号文と秘密鍵のサイズは両方とも 2 倍になっています。 例は同等性の証明です。

そこで問題は、準同型乗算後に暗号文のサイズと秘密鍵のサイズをどのように復元するかということです。これはキースイッチングが解決する問題です。

Xiang Xie先生の説明は次のとおりです。

キースイッチング

目標は、暗号文と秘密キーのサイズを線形サイズに戻すことです。

次に、暗号文 c1 と c2 の乗算を求めます。

上記のプロセスは、ビット分解の概念に基づいています。

Xiang Xie先生の説明は次のとおりです。

キースイッチングの目的: 秘密鍵を変換する$\tilde{s}$下$\tilde{c}$ 秘密鍵に変換する$s$下$c$、そして$\tilde{c}$そして$c$これらはすべて同じ平文で暗号化されます。
ここでの中心的な概念はキー スイッチング キー (KSK) です。これは秘密キーを使用することを意味します。$s$暗号化する$\tilde{s}$。

キー スイッチング プロセスを通じて、秘密キーは次から派生できます。$s\otimes s$直線的になった$s$、同時に、暗号文は から変わります。$\tilde{c}$直線的になった$c$ 。そして、式の最後の行から、キー切り替え後のことがわかります。$⟨c,s⟩$そしてオリジナル$⟨\tilde{c},s\otimes s⟩$の間にノイズの差があります$2{\tilde{c}}^T\tilde{e}$ 、この部分は非常に大きくなる可能性があります。したがって、ここではキースイッチングを実装する方法はまだありません。

ガジェット行列 G がここで導入されます。

したがって、キースイッチングのプロセスは次のようになります。

この時点で、追加される誤差は非常に小さいです。
キースイッチングを通じて、元の秘密キーを要約すると、$\tilde{s}=s\otimes s$下$\tilde{c}=c\otimes c$、秘密鍵に変換されます$s$下$c$、キースイッチ後のキーに注意してください。$s,c$元の値ではありません（再確認）。

BGV の場合、加算のノイズは直線的に増加し、乗算のノイズは二乗的に増加しますが、キー スイッチングは乗算をサポートできますが (sk が極端に大きくなるのを制限します)、実際には、ノイズは元の乗算ノイズに加算される非常に小さなノイズです。も非常に大きいです。したがって、このノイズをさらに低減する必要がある。

係数の削減

この時点では深さの浅い準同型乗算演算や加算演算はLWEにより各層ごとに新たなキーを使用して実装されていますが、計算深度が深くなると爆発的にノイズが拡大するため、まだ平準化されていません。 .FHE (指定された深さで FHE を計算できます)。
ここで、モジュロ変換を必要とするブートストラップを使用せずに特定の深さを計算できる FHE を実装したいと考えています。

途中の処理がよくわかりません。要するに、暗号文 c を q を法とする領域から p (p< を法とする領域) に変換するということです。
具体的な例を次に示します。
Modulus Reduction が実行されていない場合、ノイズは深さが深くなるにつれて二重指数関数的に増加し、レベル >= 3 以降で復号エラーが発生します。

モジュラス低減が各レベルで実行される場合、モジュラスの継続的な低減を犠牲にして、ノイズも絶対値の範囲内に維持されます。

したがって、レベル化された FHE を実装したい場合は、係数を設定できます。$B^d$、その後、次の深さを計算できます。$d$回路（ここで$B$は、リフレッシュされた暗号文のノイズの上限です)。計算された$d$深さを超えた後、係数は次のように減少する必要があります。$B$ 、現時点で復号化にエラーがないことを確認するためです。 BGV はレベル化された FHE です。