部分準同型暗号化の次の段階は近似準同型暗号化であり、私たちが達成したい完全準同型暗号化に一歩近づきます。ほぼ準同型の暗号化アルゴリズムがある場合、暗号文の加算と乗算を同時に計算できます。ただし、この段階はほぼ準同型（Somewhat Homomorphic）であるため、実行できる加算と乗算の数は非常に限られており、計算できる関数 F も限られた範囲内にあることに注意してください。
Gentry 氏の論文では、ブートストラッピングと呼ばれる重要な概念についても言及しています。ブートストラップは、暗号文の特別な処理技術であり、処理後に、臨界値に近いノイズを含む暗号文を、ノイズが非常に低い新しい暗号文に「リフレッシュ」できます。ブートストラップにより、有限級数システムのノイズは臨界値を超えることができないため、完全に準同型のシステムになります。このようにして、任意のサイズの F を準同型的に計算できます。
完全準同型暗号化の予備調査: FHE の定義と歴史的レビュー
作者：Steven Yue
私は少し前にスタンフォード大学で CS355 (Advanced Cryptography) コースを受講しました。私たちは、ダンの博士課程の学生のうち、ディマ・コーガン、フロリアン・トラマー、サバ・エスカンダリアンの3人に教えを受けました。 3名の博士講師はそれぞれに特徴があり、研究の方向性も大きく異なります。 Dima はプライバシー保護技術 PIR (Private Information Retri) に重点を置き、Florian は ML とブロックチェーンの研究に重点を置き、Saba はゼロ知識証明に重点を置いています。
CS355 コースは、古代から現代までの暗号分野のほぼすべての内容をカバーします。最も初期の一方向性関数 (One-way Function) から、楕円方程式 (ECC) とペアリング、そして最後に、近年人気のある MPC、ゼロ知識、個人情報検索 (PIR)、完全準同型アルゴリズムなどに至るまで、 。 2日前に授業が終わったばかりだったので、知識内容がまだ浅い記憶の中にメモを整理しました。コースの内容はとても興味深いので、残りの内容は後で時間があるときに共有したいと思います~
この号では、最近人気のある完全準同型暗号化 (FHE) とそれに付随する格子ベースの暗号化テクノロジについて説明します。
完全準同型暗号化とは何ですか?
完全準同型暗号化 (FHE) という名前を聞いたことがある友人も多いと思います。近年、個人のプライバシー保護に関する話題が多くなり、準同型暗号をはじめとする一連の暗号応用技術も広く普及しています。
このトピックをよりよく理解するために、完全準同型暗号の定義を簡単に紹介したいと思います。
暗号化システムのレビュー
始める前に、最も伝統的な暗号化システムを確認しましょう。
暗号化システムを構築したい場合、多くの場合キーが必要になることは誰もが知っています。このキーを使用すると、一方の端で平文情報を暗号文に暗号化し、もう一方の端でそのキーを使用して暗号文を元の形式に戻すことができます。このキーがなければ、私たちがどのような情報を伝えたかを他の人が知ることは困難です。
暗号研究では、新しいシステムの定義を見るたびに、そのシステムが持つべき特性を述べなければならないことがよくあります。
セマンティック セキュリティの主な重要性は、傍観者が 2 つの暗号化されたメッセージを区別できないことです。したがって、侵入者がネットワーク上で盗聴し、私が送信した暗号化された情報を見たとしても、私が使用している暗号化システムが意味的に安全である限り、侵入者は暗号文から暗号化されたコンテンツに関する情報を取得することはできないと確信できます。
上記 2 つの特性を満たした後、暗号化システムは健全になります。
暗号化システムが何であるかを理解した後は、ランダムに生成された文字化けしたコードのように見えるこの暗号文に注目することができます。暗号文自体を見ただけでは何も情報が得られないことは誰もが知っています。しかし、これは、鍵がなく暗号文だけがある場合は何もできないことを意味するのでしょうか?
誰もが答えを知っています。実際にはそうではありません。
この性質を加法準同型性と呼びます。これは、暗号化された暗号文が前の元のテキストとの微妙な代数的関係を維持していることを意味します。暗号文を加算すると、元の文を加算することで暗号化された新しい暗号文が得られます。同様に、加法準同型暗号化アルゴリズムも存在すると結論付けることができます。乗法準同型アルゴリズムによって生成された暗号文を乗算し、元のテキストを乗算した結果に対応する暗号文を取得できます。プロセス全体において、キーに関連する情報を知る必要はなく、ランダムに文字化けしたコードのように見える暗号文を組み合わせるだけです。
例: 匿名投票システム
次に、準同型暗号の実用性をわかりやすく説明する例を示します。
オンライン投票がどのようなものかは誰もが知っています。会社の上司が投票の波を始めたい場合は、その会社が 996 システムを採用するかどうかを選択します。次に、上司は IT 部門にサーバーをセットアップするよう依頼し、従業員に選択肢を提出させることができます。希望しない場合は 0 票、希望する場合は 1 票を投票します。最終投票期間の後、ボスはすべての投票を合計することができます。最終的に全投票の合計が従業員数の半数を超えた場合、会社は996人でスタートする。
この投票メカニズムは非常に単純に見えますが、大きなプライバシー問題があります。上司が全従業員を 996 人にすることを望んでいるにもかかわらず、法執行機関がどの従業員が残業をしたくないのかを調べるために意図的にこの投票を開始した場合、上司は彼は静かに弟にインターネットでの盗聴を任せ、従業員全員が提出した選択肢を記録し、最後に誰が０票を投じたかを確認することができる。その結果、従業員は非常に恐れ、自分の感情を表現することができなくなります。
加法準同型暗号化アルゴリズムを使用できれば、この問題は簡単に解決できます。
もちろん、このシステムはまだ不完全ですが、たとえば、IT 部門は上司が全員の投票を解読して文書に記録するのを直接支援できます。この問題の解決に役立つ暗号化ツールは他にもあります。紙面の都合上、ここではこれ以上の説明は省略します。
しかしこの時点で、準同型暗号アルゴリズムの威力を実感できるはずです。これは次のように理解できます。準同型暗号化アルゴリズムを通じて、ユーザーは信頼できないリモート サーバー (クラウド) を使用して、ある種の安全なプロキシ計算 (安全な委任計算) を実行できます。ユーザーは準同型暗号技術を利用して個人の機密入力を暗号化してクラウドに預け、クラウドは暗号化されたデータに対してある程度の計算を行い、最終的にユーザーが望む暗号化結果を取得してサーバーに返すことができます。クラウド、ユーザー。最後に、ユーザーは復号キーを使用して結果を開くことができます。契約全体を通して、委任された当事者 (クラウド) は個人的な入力に関連する有用な情報を決して見ることができません。
2 つの最も基本的な準同型特性を大まかに理解すると、他の概念が非常に簡単に理解できるようになります。体系的な観点から見ると、準同型暗号方式は部分準同型、近似準同型、有限級数完全準同型、完全準同型の 4 つのカテゴリに大別されます。
次に、各カテゴリの具体的な定義を順番に見ていきましょう。
部分準同型暗号化
準同型暗号の最も基本的な段階は部分準同型暗号と呼ばれ、準同型特性を 1 つだけ持つ暗号文として定義されます。この段階には、上で説明した加法準同型性と乗法準同型性の 2 つのモードが含まれます。
これら 2 つのメッセージの乗算に対応する暗号文が得られます。これは乗法準同型性の性質であり、この暗号文の上に新しい暗号文を重ね続けることで、暗号文間の乗算を求めることができます。
ある程度準同型暗号化
前の段落で述べたように、プライベート入力を乗算してそれらの間の線形結合を取得したい場合、単純な部分準同型暗号化アルゴリズム (RSA、ElGamal) を完成させることはできません。したがって、次の段階に進む必要があります。
部分準同型暗号化の次の段階は近似準同型暗号化であり、私たちが達成したい完全準同型暗号化に一歩近づきます。ほぼ準同型の暗号化アルゴリズムがある場合、暗号文の加算と乗算を同時に計算できます。ただし、この段階はほぼ準同型（Somewhat Homomorphic）であるため、実行できる加算と乗算の数は非常に限られており、計算できる関数 F も限られた範囲内にあることに注意してください。
近似準同型暗号の一般的な例は現段階ではあまり多くありませんが、最もよく理解されている例と言えば、ペアリングに基づく巡回群暗号アルゴリズムでしょう。
上記では、通常の巡回グループに基づく ElGamal 暗号化アルゴリズムについて簡単に説明しました。このアルゴリズムが加法準同型であることは誰もが知っています。これは、任意の暗号文間の線形結合を取得できることを意味します。実際、いくつかの特殊な巡回群では、弱い乗法準同型特性も見つかります。
この制限は、任意の論理と深さの関数 F を計算できないため、システムがほぼ準同型であることを証明します。
完全レベル準同型暗号化
次の段階に到達すると、完全準同型性の目標に一歩近づきます。
この段階は、有限級数完全準同型暗号化と呼ばれます。この段階では、暗号文に対する加算と乗算の任意の組み合わせを回数の制限なく実行できます。
完全準同型暗号化 (FHE)
多くの呼び出しを経て、最終的に私たちが待ち望んでいる完全準同型暗号化 (FHE) が登場します。
完全準同型暗号とはその名のとおり、計算方法に制限がなく、鍵を持たずに暗号文を任意に組み合わせて新たな暗号文を生成することができ、計算量に関係なく完全に元の暗号文に戻すことができます。
この段階に到達すると、前述した安全なエージェントの計算が実行可能になります。より効率的な完全準同型暗号化システムを見つけることができれば、データを漏らすことなく、すべてのローカル計算を安全にクラウドにプロキシすることができます。
完全準同型暗号方式の定義
以下の完全準同型システムの歴史の議論を始める前に、完全準同型システムの正式な定義を系統的に定義することができます。完全準同型暗号化システムには、合計 4 つのアルゴリズムがあります。
完全準同型暗号化アルゴリズムがどのように実装されるかを学び始める前に、完全準同型暗号化の概念がどのようにして生まれたのかを見てみるのもよいでしょう。
FHE (完全準同型) の概念は、実際には 1970 年代後半に提案されました。 1978 年、暗号学の著名人である Rivest、Adleman、Dertouzos は、論文「データ バンクとプライバシー準同型性について」の中で、暗号文に対して特定の計算を実行し、元のテキストに対して間接的に操作できるシステムのアイデアに初めて言及しました。その後、この考え方は再要約され、完全準同型暗号化と名付けられました。
完全準同型暗号化の概念は長い間提案されてきたことがわかります。驚くべきことに、論文が発表される 2 年前の 1976 年に、ディッフル・ヘルマン鍵交換プロトコルが提案されたばかりでした。これは、暗号化専門家の想像力が依然として非常に豊かであることを示しています。
FHE の概念が提案されたとき、学術コミュニティ全体がそれに感動し、完全に準同型の特性を持つ完璧なアルゴリズムを見つけようとして数十年にわたる研究を開始しました。しかし過去数十年にわたり、人々は考えられるすべてのオプションを試してきましたが、完全に準同型であるという条件をすべて満たし、安全性が簡単に証明できるオプションを見つけることができませんでした。
2009 年までスタンフォード大学で学んでいた Craig Gentry 博士は、突然アイデアを思いつき、FHE アルゴリズムの困難を突破しました。彼は博士論文の中で、合理的で安全な完全準同型暗号システムを初めて示しました。このシステムは理想格子の仮定に基づいています。 Gentry09 によって提案された完全準同型暗号化システムは、第 1 世代完全準同型暗号化システムと呼ばれることがあります。
Gentry 氏の論文では、ブートストラッピングと呼ばれる重要な概念についても言及しています。ブートストラップは、暗号文の特別な処理技術であり、処理後に、臨界値に近いノイズを含む暗号文を、ノイズが非常に低い新しい暗号文に「リフレッシュ」できます。ブートストラップにより、有限級数システムのノイズは臨界値を超えることができないため、完全に準同型のシステムになります。このようにして、任意のサイズの F を準同型的に計算できます。
Gentry の大躍進の後、暗号界全体が再び狂気の渦に陥り、Gentry が提案したアイデアに基づいて、より効率的で汎用性の高い完全準同型システムを見つけるために誰もが競い合い始めました。
2011 年、Brakerski と Vaikuntanathan という 2 人の大物が、格子暗号化のもう 1 つの前提である Learning With Errors (LWE) に基づいた、新しい完全準同型暗号化システムを提案しました。同年、Brakerski、Gentry、Vaikuntanathan がシステムを完成させ、正式に公開しました。彼らが発明した完全準同型システムは、略して BGV システムと呼ばれます。 BGV システムは制限レベルの準同型暗号化システムですが、ブートストラップを通じて完全な準同型暗号化システムに変えることができます。 Gentry09 によって提案されたシステムと比較して、BGV システムはより現実的な LWE 仮定を使用します。一般に、BGV方式を第2世代完全準同型暗号方式と呼びます。
2013年、ジェントリーはカムバックを果たした。 Gentry、Sahai、Waters は、新しい GSW 完全準同型暗号化システムを開始しました。 GSW システムは、有限級数の完全準同型特性を持つという点で BGV に似ており、より単純な LWE 仮定に基づいており、ブートストラップを通じて完全準同型にすることができます。一般に GSW システムを第 3 世代の完全準同型暗号化システムと呼びます。
2013 年以降、暗号圏は基本的に繁栄しました。オリジナルの 3 世代完全準同型システムに基づいて、BGV および GSW システムの動作効率の最適化と加速を目的としたさまざまな新しい設計が登場しました。 IBM は、BGV システムに基づいたオープンソースの完全準同型コンピューティング ライブラリ HElib を開発し、主要なモバイル プラットフォームへの移植に成功しました。同時に、注目に値する別のオープンソース プロジェクト TFHE もあります。 TFHE は GSW システムをベースに、さまざまな最適化と高速化が追加されており、現在では非常に有名です。
従来の完全準同型ライブラリの開発に加えて、多くのチームは、GPU、FPGA、ASIC などの異種ハードウェアを使用して完全準同型暗号化アルゴリズムの計算をより高速化する方法も研究しています。たとえば、cuFHE は、よく知られた CUDA ベースの GPU アクセラレーションによる完全準同型暗号化システムです。
今日の観点から見ると、ジェントリーが完全準同型システムのドアをノックしてから 11 年が経過しました。現在、業界では FHE の研究がブームになっており、多くの人がさまざまな観点やアプリケーション要件から完全準同型システムを研究しています。現在までに、実現可能なさまざまな FHE 実装手法がすでに存在していますが、依然として誰もが追求しているのは、FHE システム運用の効率化です。現在の最先端の FHE ライブラリを例に挙げると、モバイル プラットフォーム上で比較的単純なロジックを準同型的に計算するには、最短で数十ミリ秒、最長で数十秒かかる場合があります。これらの時間単位は、コンピュータ システムにとって非常に遅いです。
異種プラットフォーム上で FHE システムをより効率的に実行する方法は、依然として未解決の謎です。この問題が一度解決されれば、すべてのコンピューター計算を完全準同型に変換し、エージェントがサードパーティのクラウド上で計算を実行できるようになるのは簡単な未来になります。
FHE と MPC の関係
記事を終える前に、FHE と MPC の関係について少し付け加えておきたいと思います。 MPC は Secure Multi-Party Computation の略で、信頼できるマルチパーティ計算です。これは通常、複数の関係者が独自のプライベート入力を持っており、他の者には公開したくないが、自分の入力を使用して関数 F を一緒に計算し、計算結果を共有したいことを意味します。
MPC は実際には非常によく知られており、長い間研究されてきた分野です。前世紀に暗号学者 Yao Qizhi が「Garbled Circuits」を発表して以来、MPC の分野は広く認識されるようになり、多くの画期的な進歩がありました。現在、使用できる MPC ライブラリはすでに多数あり、一定の操作効率も備えています。
MPC を知っている友人は、完全準同型暗号化システムの困難な歴史を見て、多くの疑問を持つかもしれません。なぜ完全準同型暗号化を MPC プロトコルで直接置き換えることはできないのですか?
実際、MPC プロトコルは FHE プロトコルを完全に置き換えることができます。ユーザー入力とプライベート入力をプロトコルの当事者として使用し、その後、MPC プロトコルの実行条件を満たすリモート プロキシ コンピューティング サーバーを別の当事者として使用するだけで済みます。特定の対話を通じてのみ、プロキシ コンピューティングを実行できます。そしてサーバーはプライベート入力を見ることができません。
しかし、私たちが見落としている非常に重要な点があります。MPC は対話型であるため、プロトコルを完成させるには、ユーザーとサーバーが一緒に計算して通信する必要があります。これは、FHE エージェント コンピューティングの最も基本的な要件と矛盾します。ユーザーが契約を完了するために常にオンラインに留まり、コンピューティング能力の一部を支払う必要がある場合、実際には計算はまったく「プロキシ」されず、両当事者は情報セキュリティのために追加の計算を行うだけです。 。これは、MPC の分野が大きな進歩を遂げているのに、FHE の分野がまだ知られていない理由も説明します。2 つのシステムはまったく異なる問題を解決するためです。
これを見ると、誰もが完全準同型暗号システムについて十分に理解しているはずです。
次に、前述の GSW 完全準同型暗号化システムについて学びます。完全準同型システムとしては第 3 世代になりますが、Gentry09、BGV、GSW の 3 つのシステムの中で、GSW が最も仮定が少なく、構造が単純で理解しやすいと思います。そして現在、GSW システムに基づいて構築されたオープン ソース ライブラリ (TFHE など) が数多く存在します。
スペースの都合上、この記事はここで終了とさせていただきます。次の記事では、まず GSW システムの基本、つまり格子ベースの暗号化システムと LWE 問題について学びます。 LWE の問題を理解すると、GSW が解決する問題が非常に明確になります。