編集者注: この記事は以下から引用しましたアンビラボ (ID:secbitlabs)、許可を得てOdailyによって転載されました。

編集者注: この記事は以下から引用しました

アンビラボ (ID:secbitlabs)

、許可を得てOdailyによって転載されました。

少し前に、スタンフォード大学で CS355 (上級暗号化) コースを受講しました。私たちは、ダンの博士課程の学生のうち、ディマ・コーガン、フロリアン・トラマー、サバ・エスカンダリアンの3人に教えを受けました。 3人の博士講師はそれぞれに特徴があり、研究の方向性も大きく異なります。 Dima はプライバシー保護技術 PIR (Private Information Retrieval) に重点を置き、Florian は ML とブロックチェーンの研究に重点を置き、Saba はゼロ知識証明に重点を置いています。

CS355 このコースは古代から現代までの暗号分野のほぼすべてをカバーします。最も初期の一方向性関数 (One-way Function) から、楕円方程式 (ECC) とペアリング、そして最後に、近年人気のある MPC、ゼロ知識、個人情報検索 (PIR)、完全準同型アルゴリズムなどに至るまで、 。 2日前に授業が終わったばかりだったので、知識内容がまだ浅い記憶の中に大量のメモを整理しました。コースの内容はとても興味深いので、残りの内容は時間があるときに共有します~

この号では、最近人気のある完全準同型暗号化 (FHE) とそれに付随する格子ベースの暗号化テクノロジについて説明します。

副題

完全準同型暗号とは

Fully Homomorphic Encryption (FHE) の名前を聞いたことがある友人も多いと思います。近年、個人のプライバシー保護に関する話題が多くなり、準同型暗号をはじめとする一連の暗号応用技術も広く普及しています。

このトピックをよりよく理解するために、完全準同型暗号の定義を簡単に紹介したいと思います。

• 暗号化システムのレビュー

• 始める前に、最も伝統的な暗号化システムを確認しましょう。

• 暗号化システムを構築したい場合、多くの場合キー (Key) が必要になることは誰もが知っています。このキーを使用して、一方の端で平文情報を暗号文に暗号化し、もう一方の端でキーを使用して暗号文を元の形式に戻すことができます。このキーがなければ、私たちが渡した情報を他の人が知ることは困難です。

上の図は基本的に、すべての一般的な暗号化システムの全体像を示しています。すべての暗号化システムは、より正式な方法で説明すると、間違いなく次の 3 つのことを実行します。

まず、暗号化と復号化のための鍵のペアが生成アルゴリズムによってランダムに生成されます。

暗号化当事者は、暗号化キーと暗号化アルゴリズムを通じて元のテキストを暗号化し、最終的に暗号文を取得します。

その後、復号化するときに、復号者は復号キーと復号アルゴリズムを通じて暗号文を復号し、最終的に元の元のテキストを復元できます。

暗号化アルゴリズムについて詳しい友人は、AES、RSA などの一般的な暗号化アルゴリズムを間違いなく知っているでしょう。また、暗号化システムは一般に、対称暗号化システムと非対称暗号化システムの 2 つのタイプに分類されることも誰もが知っています。ここで説明する 3 つの手順は、あらゆる暗号化システムに適用できます。対称型の場合、暗号化と復号化に使用されるキーは同じです。非対称システムの場合、暗号化には公開鍵 (Public Key) が使用され、復号化には別の秘密鍵 (Private Key) が使用されます。

暗号研究では、新しいシステムの定義を見るたびに、このシステムが持つべき特性 (プロパティ) を記述する必要があることがよくあります。

まず、最初に実装するプロパティは Correctness です。正確性とは、正しいキーを持っていれば、復号化アルゴリズムを通じて暗号文を元のテキストに復元できることを意味します。復号化の成功率を表すために、私たちは確率法をよく使用します。

上の方程式は、正しいキーを持っている場合、復号化アルゴリズムが暗号化アルゴリズムによって生成された暗号文を復元できる確率は 100% であることを表しています。

私たちが達成したい 2 番目のプロパティは、セマンティック セキュリティです。

セマンティック セキュリティの定義については、ここでは説明しません。しかし、異なる原文に対応する 2 つの暗号文がある場合、どの暗号文がどの原文に対応するかを区別できないことは理解できます。

セマンティック セキュリティの主な重要性は、傍観者が 2 つの暗号化されたメッセージを区別できないことです。したがって、侵入者がネットワーク上で盗聴し、私が送信した暗号化された情報を見たとしても、私が使用している暗号化システムが意味的に安全である限り、侵入者は暗号文から暗号化されたコンテンツに関する情報を取得することはできないと確信できます。

上記 2 つの特性を満たした後、暗号化システムは健全になります。

準同型暗号化: 偶然の特殊な性質

暗号化システムが何であるかを理解した後、ランダムに生成された文字化けと思われるこの暗号文に注目することができます。暗号文自体を見ただけでは何も情報が得られないことは誰もが知っています。しかし、これは、鍵がなく暗号文だけがある場合は何もできないことを意味するのでしょうか?

誰もが答えを知っています。実際にはそうではありません。

しかし、多くの暗号化アルゴリズムの中でも、あるクラスのアルゴリズムによって生成される暗号文には特別な準同型特性があります。つまり、暗号化アルゴリズムを使用して数値 1 の暗号文を取得すると、数値 2 の暗号文が取得されます。このとき、暗号文を合計すると、まさに暗号文になります！

この性質を加法準同型性と呼びます。つまり、暗号化された暗号文は、前の元のテキストとの微妙な代数的関係を維持します。暗号文を合計すると、元の文を合計して暗号化した後、新しい暗号文が得られます。同様に、加法準同型性の他に、乗法準同型性を利用した暗号アルゴリズムもあります。乗算準同型アルゴリズムによって生成された暗号文を乗算し、元のテキスト間の乗算の結果に対応する暗号文を取得できます。プロセス全体において、キーに関連する情報を知る必要はなく、ランダムに文字化けしたコードのように見える暗号文を組み合わせるだけです。

例: 匿名投票システム

次に、準同型暗号の実用性をわかりやすく説明する例を挙げてみましょう。

オンライン投票がどのようなものかは誰もが知っています。会社の上司が投票の波を始めたい場合は、その会社が 996 システムを採用するかどうかを選択します。次に、上司は IT 部門にサーバーをセットアップするよう依頼し、従業員に独自の選択肢を提出させることができます。つまり、「いいえ」には 0 票、「はい」には 1 票と投票します。最終投票期間の後、ボスはすべての投票を合計することができます。最終的に全投票の合計が従業員数の半数を超えれば、996人でスタートすることになる。

この投票メカニズムは非常に単純に見えますが、プライバシーに大きな問題があります。上司が心の中ではすべての従業員を 996 にすることを望んでいますが、どの従業員が残業をしたくないのかを確認するためにフィッシング法執行機関に意図的にこの投票を開始しただけだとします。上司は静かに弟にインターネットでの盗聴を任せ、各従業員が提出した選択肢を記録し、最後に誰が0票を投じたかを確認することができます。その結果、従業員は非常に恐れ、自分の心を打ち明けることができなくなります。

加法準同型暗号化アルゴリズムを使用できれば、この問題は簡単に解決できます。

まず、IT 部門は KeyGen アルゴリズムを使用して暗号化キーと復号化キーのペア pk、sk を生成し、公開キーを各従業員に配布します。

その後、各従業員は暗号化アルゴリズムを使用して自分の選択 (1 または 0) を暗号文に暗号化し、その暗号文を IT サーバーに送信します。

最後に、IT 部門は全員の選択を合計し、結合された暗号文を取得し、この暗号文を上司に送信できます。最後に、ボスは復号化されたキーを使用して暗号文を開き、最終的な投票結果を取得します。

このようにして、加法準同型性の特徴を備えた投票集計システムを実現することに成功しました。上司がネットワークを監視するために人を派遣したとしても、暗号化された暗号文のctiしか見ることができず、それぞれの投票数を知る方法はありません。投票した人です。

もちろん、このシステムはまだ不完全ですが、たとえば、IT 部門は上司が全員の投票を解読して文書に記録するのを直接支援できます。この問題の解決に役立つ暗号化ツールは他にもあります。紙面の都合上、ここでは詳しくは述べません。

しかし、ここで準同型暗号アルゴリズムの威力を実感できるはずです。これは次のように理解できます。準同型暗号化アルゴリズムを通じて、ユーザーは信頼できないリモート サーバー (クラウド) を使用して、ある種の安全な委任計算 (安全な委任計算) を実行できます。ユーザーは、準同型暗号化技術を通じて機密のプライバシー入力をクラウドに預けることができ、クラウドは暗号化されたデータに対してある程度の計算を実行し、最終的にユーザーが望む暗号化結果を取得してユーザーに返すことができます。最後に、ユーザーは復号キーを使用して、取得した結果を開くことができます。プロトコル全体を通じて、プリンシパル (クラウド) はプライベート入力に関連する有用な情報を確認できません。

準同型暗号方式の分類

2 つの最も基本的な準同型特性を一般的に理解すると、他の概念も非常に簡単に理解できるようになります。体系的な観点から、準同型暗号方式は、部分準同型、近似準同型、有限級数完全準同型、完全準同型の 4 つのカテゴリに大別されます。

次に、各カテゴリの具体的な定義を順番に見ていきましょう。

部分準同型暗号化

準同型暗号の初期段階は部分準同型暗号と呼ばれ、暗号文の準同型特性が 1 つだけであると定義されます。この段階には、上で説明した加法準同型性と乗法準同型性の 2 つのモードが含まれます。

これを前述の安全なプロキシ コンピューティングのシナリオに当てはめると、プライベートな入力があり、クラウドが (x1、x2、...) の計算に役立つことを期待している場合、クラウドを使用してこれらを計算できます。入力。表現する関数。

加法準同型暗号化アルゴリズムを通じて計算できる場合、この関数にはプライベート入力の線形結合 (加算演算) のみが含まれている必要があることを意味します。実際の例は、プライベート入力に定数を乗算し、それらを加算することです。

しかし、2 つの入力を乗算したい場合、上記の加法準同型アルゴリズムは無力です。すべてのプライベート入力の線形結合のみにすることができます。

一般的な加法準同型暗号化アルゴリズムは、巡回群に基づく ElGamal 暗号化アルゴリズムです。

ElGamal は、循環グループの特性を使用する、Diffie-Hellman 鍵交換プロトコルに基づく非常に便利な公開鍵暗号化アルゴリズムです。スペースの都合上、ここでは循環グループの定義については詳しく説明しません。各グループがジェネレーターを見つけることができることだけを知っておく必要があります。

この生成器はべき乗されることができます。 ElGamal暗号化の実装方法は大まかに以下のとおりです。

まず、私たちは、

私たちは ElGamal の正確さと安全性を証明しません。しかし、この暗号化システムの暗号化方法を見た後、これらはすべてべき乗演算であるため、ElGamal の潜在的な加法準同型特性を見つけることができます。

同じ原理が乗法準同型暗号化のアルゴリズムにも適用できます。すべてのプライベート入力を乗算することしかできませんが、線形結合 (加算) を行う方法はありません。乗法準同型の例は実際には非常に一般的であり、私たち全員がよく知っている RSA 暗号化は乗法準同型システムです。

RSA暗号化の実装方法は大まかに以下のとおりです。

これら 2 つのメッセージの乗算に対応する暗号文が得られます。これは乗算の準同型の性質であり、この暗号文の上に新しい暗号文を重ね続けることができるため、暗号文間の乗算を求めることができます。

ある程度準同型の暗号化

前の段落で述べたように、プライベート入力を乗算してそれらの間の線形結合を取得したい場合、単純な部分準同型暗号化アルゴリズム (RSA、ElGamal) を完成させることはできません。したがって、次の段階に進む必要があります。

部分準同型暗号化の次の段階は近似準同型暗号化で、これは私たちが達成したい完全準同型暗号に一歩近づきます。近似準同型暗号化アルゴリズムがあれば、暗号文の加算と乗算を同時に計算できます。ただし、この段階はほぼ準同型（ある程度準同型）であるため、実行できる加算と乗算の数は非常に限られており、計算できる関数も限られた範囲内にあることに注意する必要があります。

近似準同型暗号の現段階では一般的な例はあまりありませんが、最もよく理解されている例と言えば、ペアリング (Pairing) 巡回グループ暗号化アルゴリズムに基づいたものとなるでしょう。

上記では、通常の巡回グループに基づく ElGamal 暗号化アルゴリズムについて簡単に説明しました。このアルゴリズムが加法準同型であることは誰もが知っています。これは、暗号文間のあらゆる線形結合を取得できることを意味します。実際、いくつかの特殊な巡回群では、弱い乗法準同型特性を見つけることができます。

このようにして、最初の 2 つの値の累乗間の積の組み合わせが隠れて得られます。 ElGamal 暗号化では 2 つの値の累乗を線形結合できるという特性と組み合わせると、完全準同型システムが得られます。

実際、ペアリングの特別な性質はすべての循環群に現れるわけではないため、現実はそれほど美しくありません。したがって、ペアリングによってペアにできる 2 つのグループの値を乗算して新しいグループにマップすると、新しいグループは対応するペアリング属性を見つけることができない可能性があります。

つまり、Pairing プロパティを持つ巡回グループでは、非常に限られた乗算しか実行できません。現在のグループがペアリングをサポートしているが、新しいマッピング グループ GT がペアリングをサポートしていない場合、これは、現在のシステムに基づいて準同型暗号化操作を実行したい場合、操作できる関数には任意の線形結合を含めることができることを意味します。乗算のレイヤーは 1 つまでしか含めることができません。

この制限は、任意の論理と深さの関数 F を計算できないため、システムがほぼ準同型であることを証明します。

完全レベル準同型暗号化

次の段階に到達すると、完全準同型性の目標に一歩近づきます。

この段階は、有限級数完全準同型暗号化と呼ばれます。この段階では、回数の制限なく、暗号文に対して加算と乗算の任意の組み合わせを実行できます。

しかし、これが有限級数準同型性と呼ばれる理由は、この段階のアルゴリズムでは、関数 F の複雑さを制限する複雑さの上限 L という新しい概念が導入されるためです。これをバイナリ回路 C で表現できる場合、深さとサイズは L の範囲内に収まる必要があります。つまり、次のようになります。

言い換えれば、L が比較的大きい場合、さまざまなより単純な (複雑さの低い) 準同型演算を実行できます。有限級数準同型暗号のアルゴリズムは、完全準同型暗号の次の段階の基礎でもあり、複雑さの中で完全準同型を実現できれば、完全準同型の実現もそう遠くありません。

この複雑さの上限 L がどのようにして得られるかがわかります。まず第一に、完全準同型暗号化アルゴリズムが存在する場合、暗号文に対してあらゆる加算および乗算演算を実行できると想像できます。ただし、このアルゴリズムでは、暗号化時に暗号文に一定量のランダム ノイズが追加されます。

ノイズが制御可能な範囲内にある場合、復号アルゴリズムは暗号文から元のテキストを簡単に復元できます。しかし、準同型計算のために暗号文を積み重ねると、各暗号文のノイズが重なり合って拡大します。暗号文に対して比較的単純なロジックを実行するだけであれば、重畳ノイズは依然として許容範囲内にあります。しかし、あまりにも複雑に暗号文を積み重ねると、ノイズの範囲が臨界値を超えると、元の文が完全に上書きされてしまい、復号に失敗してしまいます。

完全準同型暗号化 (FHE)

多くの呼び出しを経て、最終的に私たちが待っている完全準同型暗号化 (FHE) にたどり着きました。

この段階に到達すると、前述の安全なプロキシ計算が可能になります。非常に効率的な完全準同型暗号化システムを見つけることができれば、データを漏らすことなく、すべてのローカル コンピューティングを安全にクラウドにプロキシすることができます。

副題

完全準同型暗号化方式の定義

以下の完全準同型システムの歴史の議論を始める前に、完全準同型システムの正式な定義を系統的に定義することができます。完全準同型暗号化システムには、合計 4 つのアルゴリズムがあります。

副題

完全準同型暗号化システムの特性

次に、このシステムのプロパティ (プロパティ) を見てみましょう。まず、システムが正しくなければなりません。

つまり、回路 F を任意に選択し、元のテキスト メッセージのセット m1、m2、... を任意に選択するとします。最初に KeyGen アルゴリズムによって生成されたキーがある場合は、次のようになります。

次に、システムは意味的に安全である必要があります。この定義についてはすでに上で説明しました。

最後に、完全準同型暗号化システムを実用化するには、コンパクト性という要件を追加する必要があります。

なぜこの簡単な機能を追加する必要があるのでしょうか?この要件がなければ、意味のない (不正な) 完全準同型システムを簡単に作成できるからです。

Eval の出力サイズに制限がない場合、Eval を何度も重ね合わせると、得られる暗号文のサイズはどんどん大きくなっていきます。最終的に復号するときは、元の暗号文をすべて復号して計算するだけです。これは、ユーザーが自分の健康情報を暗号化し、病院に自分が病気かどうかの判断を依頼するようなものです。病院は暗号文をそのまま送り返し、その後、データ モデルのセット全体と医学の教科書を送り返します。それは、次のことを伝えるのと同じことを意味します。自分で計算する必要があるとユーザーに伝えます。

このタイプの完全準同型システムには、最終的な暗号文が演算回路 F の特定の詳細を完全に隠すことができないという、より大きな欠点もあります。この病院の使用シナリオでは、病院の最も価値のある資産はこのデータ分析システムである可能性があります。無駄に F をユーザーに送り返してしまうと、あなたの苦労の成果は簡単に他人に盗まれてしまいます。

要約すると、正確性、意味論的セキュリティ、簡潔さの 3 つの要素が満たされている限り、自明ではない完全準同型暗号化システムが完成します。

副題

完全準同型暗号の歴史的レビュー

完全準同型暗号化アルゴリズムがどのように実装されるかを学び始める前に、完全準同型暗号化の概念がどのようにして生まれたのかを見てみるのもよいでしょう。

FHE (完全準同型性) の概念は、実際には 1970 年代後半に提案されました。 1978 年、暗号分野の著名人である Rivest、Adleman、Dertouzos は、「データ バンクとプライバシー準同型性に関する論文」の中で、暗号文に対して特定の計算を実行し、暗号文に対して間接的に操作できるシステムの概念について初めて言及しました。オリジナルのテキスト。その後、このアイデアは再要約され、完全準同型暗号化と呼ばれるようになりました。

完全準同型暗号化の概念は長い間提案されてきたことがわかります。驚くべきことに、この論文が発表される 2 年前の 1976 年には、ディッフル・ヘルマン鍵交換プロトコルが提案されたばかりでした。暗号分野の想像力は依然として非常に豊かであることがわかります。

FHE の概念が提案されたとき、学術コミュニティ全体がそれに感動し、完全に準同型の特性を持つ完璧なアルゴリズムを見つけようとして数十年にわたる研究を開始しました。しかし、過去数十年にわたり、人々は考えられるすべてのオプションを試してきましたが、完全準同型性のすべての条件を満たし、安全性を簡単に検証できるオプションを見つけることができませんでした。

2009 年までスタンフォード大学に留学していたクレイグ ジェントリー博士は、突然のひらめきにより FHE アルゴリズムの困難を突破しました。彼は博士論文の中で、合理的で安全な完全準同型暗号システムを初めて示しました。このシステムは、理想的な格子の仮定に基づいています。 Gentry09 によって提案された完全準同型暗号化システムは、第 1 世代完全準同型暗号化システムと呼ばれることがあります。

Gentry 氏の論文では、ブートストラッピングと呼ばれる重要な概念についても言及しています。ブートストラップは暗号文の特別な処理技術で、処理後に臨界値に近いノイズを含む暗号文を実際に「リフレッシュ」して、ノイズが非常に低い新しい暗号文を生成します。ブートストラップにより、有限級数システムのノイズは臨界値を超えることができないため、完全に準同型のシステムになります。このようにして、任意のサイズを準同型的に計算できます。

ジェントリーの大躍進の後、暗号圏全体が再び狂気に陥り、ジェントリーのアイデアに基づいた、より効率的で汎用性の高い完全準同型システムを見つけるために誰もが争うことになりました。

2011 年、2 人の大物 Brakerski と Vaikuntanathan は、格子暗号化のもう 1 つの前提である Learning With Errors (LWE) に基づいた、新しい完全準同型暗号化システムを提案しました。同年、Brakerski、Gentry、Vaikuntanathan は共同でシステムを完成させ、正式に公開しました。彼らが発明した完全準同型システムは、略して BGV システムと呼ばれます。 BGV システムは、系列が限定された準同型暗号化システムですが、ブートストラップによって完全な準同型暗号化システムに変えることができます。 BGV システムは、Gentry09 によって提案されたシステムよりも現実的な LWE 仮定を使用します。一般に、BGV方式を第2世代完全準同型暗号方式と呼んでいます。

2013 年以降、暗号圏は基本的に開花しました。オリジナルの 3 世代の完全準同型システムに基づいて、BGV および GSW システムの動作効率を最適化し、加速するためのさまざまな新しい設計が登場しました。 IBM は、BGV システムに基づいたオープンソースの完全準同型コンピューティング ライブラリ HElib を開発し、主要なモバイル プラットフォームへの移植に成功しました。同時に、別のオープンソース プロジェクト TFHE も非常に注目に値します。 TFHE は GSW システムをベースにしており、さまざまな最適化と高速化が追加されており、現在では非常に有名です。

従来の完全準同型ライブラリの開発に加えて、多くのチームは、GPU、FPGA、ASIC などの異種ハードウェアを介して完全準同型暗号化アルゴリズムの計算をより高速化する方法も研究しています。たとえば、cuFHE は、よく知られた CUDA ベースの GPU アクセラレーションによる完全準同型暗号化システムです。

今日の視点から見ると、ジェントリーが完全準同型システムの扉を叩いてから 11 年が経過したように見えます。現在、業界は FHE に関する研究で溢れており、多くの人がさまざまな角度やアプリケーション要件から完全準同型システムを研究しています。現在までに、実現可能なさまざまな FHE 実装手法がすでに存在していますが、依然として誰もが追求しているのは、FHE システム運用の効率化です。現在の最先端の FHE ライブラリを例に挙げると、モバイル プラットフォーム上で比較的単純なロジックを準同型的に計算するには数十ミリ秒または数十秒かかる場合があります。これらの時間単位は、コンピュータ システムにとっては非常に遅いです。

異種プラットフォーム上で FHE システムをより効率的に実行する方法は、依然として未解決の謎です。この問題が解決されれば、すべてのコンピューター計算を完全準同型変換に変換し、エージェントがサードパーティのクラウド上で計算を実行することが手の届く未来になります。

副題

FHEとMPCの関係

MPC は実際には非常によく知られた分野であり、長い間研究されてきました。暗号学者の姚志志氏が前世紀に「文字化け回路」を発表して以来、MPC の分野は広く認識され、多くの画期的な進歩が見られました。今では使えるMPCライブラリも豊富になり、一定の動作効率も得られます。

MPC を知っている場合は、完全準同型暗号化システムの困難な歴史を見た後、多くの疑問が生じるかもしれません。なぜ完全準同型暗号化を MPC プロトコルで直接置き換えることができないのですか?

実際、MPC プロトコルは FHE プロトコルを完全に置き換えることができます。ユーザー入力とプライベート入力をプロトコルの当事者として使用し、次にリモート プロキシ コンピューティング サーバーを別の当事者として使用するだけで、MPC プロトコルの実行条件が満たされます。特定の対話を通じてのみ、プロキシ コンピューティングを実行できます。そしてサーバーもプライベート入力を認識しません。

しかし、私たちが無視している非常に重要な点があります。MPC は対話型であるため、契約を完了するには、ユーザーとサーバーが一緒に計算して通信する必要があります。これは、FHE プロキシ コンピューティングの最も基本的な要件とも矛盾します。ユーザーが契約を完了するために常にオンラインに留まり、コンピューティング能力の一部を支払う必要がある場合、計算はまったく「代理」されず、両当事者は情報のセキュリティーのために追加の計算を行うだけになります。 。これは、MPC の分野が大きな進歩を遂げているのに、FHE の分野がまだ知られていない理由も説明します。2 つのシステムはまったく異なる問題を解決するためです。

副題