暗号化について考えるとき、最初に思い浮かぶのは、静止状態での暗号化と転送中の暗号化です。静止状態での暗号化は、暗号化されたハードドライブ、取り外し可能なデバイス、またはクラウドデータベースにデータを保存することを可能にし、正当な所有者だけが平文の内容を見たり編集したりできる保証を提供します。転送中の暗号化は、インターネットを介して送信されるデータが指定された受信者のみがアクセスできることを保証します。これは公共のルーターやチャネルを経由して転送されても、悪意のある攻撃者によって改ざんされていないことも保証します。これは認証された暗号化として知られています。データが暗号化されると、チェーン内の誰もが一つのビットのデータを推測することはできず（機密性）、暗号文を検出せずに変更することもできません（整合性/真正性）。

一部のコラボレーションユースケースでは、暗号文に対しても重要な処理を許可する必要があります。これは、プライバシー保護技術、または使用されている暗号化の領域であり、完全準同型暗号化(FHE)はその1つです。例えば、有権者が投票用紙を暗号化し、中間のエンティティがすべての投票用紙を集約して投票数をカウントし、最終結果のみが公開されます。残念なことに、認証された暗号化では、中間のエンティティはそのような計算を実行するためにすべての投票用紙を復号化する必要があり、個々の投票がクリアに表示されるため、非常に面倒です。理論的には、投票用紙をシャッフルすることは可能ですが(一部の電子投票プロトコルは実際にこれに依存しています)、紙の投票用紙とは異なり、完全性を保証する従来の暗号化メカニズムにより、暗号化された投票用紙を送信者のIDから切り離すこともはるかに困難になります。電子投票スキームでは、投票をカウントするエンティティの周囲にハードウェアの壁を追加できます。これは、たとえば、信頼された実行エンクレーブの目的です。このようなエンクレーブは、攻撃者がエンティティと対話することをはるかに困難にします。しかし、ハードウェアに障害が発生すると復号化キーが漏洩する可能性があり、ソフトウェアエラーとは異なり、ハードウェア設計の脆弱性に簡単にパッチを適用することはできません。

このような類似のユースケースに対応するために、完全同型暗号化（FHE）を利用することができます。FHEは、復号化せずに暗号文上で関数を計算し、関数の出力の暗号化を直接取得することができる特殊な形式の暗号化です。

ほとんどの場合、評価する関数fは公開されているため、f(x)の暗号化を変換する処理手順の順序は公開されており、秘密を関与させずにクラウドで実行できます。

この図は、電子投票の3つのシナリオを示しています。最も左の画像では、信頼できるエンティティが個々の投票をシャッフルして復号化し、その合計を公開します。投票者のプライバシーが保護され、投票が正しく集計されるように、計算を行うエンティティを信頼する必要があります。中央の画像では、整合性とプライバシーの保証を提供するために信頼できるイントロープが使用され、同じ計算が行われます。右側の画像では、同型暗号化が使用されます。暗号化された投票を（公開で）追加でき、結果は復号化されます。E（ ）は暗号化操作を、D（ ）は復号化を示します。

FHEはコンパクトであり、つまり出力される暗号文のビットサイズとそれを復号化するための労力は、平文結果のビット数にのみ依存します。これは適用された計算のチェーンに依存しません。これには、単純な非コンパクトな暗号システムが含まれます。つまり、xの入力暗号文をfのソースコードと単に連結し、受信者にxを復号化させてからfを適用させるといったものは除外されます。

FHEアウトソーシングは、実用的な障害ではなく、数学的な問題の難しさに基づいて、セキュアエンクレーブの代替手段としてしばしば提示されます。そのため、FHEは受動的なサイドチャネル攻撃やクラウドホストの他の破損に完全に無敵です。誰かが計算をアウトソースする必要があるが、データが非常に機密性が高い場合を想像してみてください。他の誰かがマシンのルートになる可能性がある場合、その人はおそらくクラウドVMを使用することをためらうでしょう。また、SGXのようなエンクレーブで実行することも躊躇するかもしれません。クラウドホストのCPUとメモリは、常に負荷、電力、温度を監視されています。これらの測定からいくつかの情報が抽出されるかもしれません。その人は、FHEの約束によって、どのような種類の測定結果を集めても、情報の任意の1ビットを抽出するには、事後量子数学的な問題を解かなければならないという安心感を得るかもしれません。

もしスキームが秘密鍵なしでは情報の1ビットも読ませないようにするなら、逆にFHEの普遍的な可変性により、攻撃者は計算された任意のビットを反転させることができます。回路では、これはアクティブなサイドチャネル攻撃の相当部分であり、攻撃者は任意のビットを対象とすることができる魔法のレーザービームが与えられます。最初は非常に怖いかもしれませんが、FHEではこれらの攻撃は同型演算の不正実行に対応します。計算に複製または冗長性を追加することで回避できます。

FHEは公開鍵の形式でよく紹介されます。次のようなものがあります:

1. 復号化キー：これは暗号システムのマスターキーであり、すべての他のキーを派生させることができます。復号化キーは通常、ローカルで生成され、送信されることはなく、FHEの暗号文を復号化できるのは復号化キーの所有者だけです。
2. 暗号鍵：公開鍵モードでは、最初の暗号文を提供するパーティが復号鍵の所有者ではない場合、この中程度の鍵は通常、ゼロのランダム暗号化で構成されます。FHEはアフィン関数をサポートしているため、これは任意のメッセージを暗号化するのに十分です。
3. 評価キー：このキーは、暗号文上で関数を評価するパーティーに与えられるべきです。このキーは、公開鍵と同様に公開または伝送しても安全です。評価キーのサイズは、評価する関数が線形か任意かによって、空から非常に大きいまでさまざまです。

復号鍵の所有者は、暗号システムの最も機密性の高い秘密の所有者です。この人物は、実行された同型演算の連鎖が正当であり、最終暗号文が安全に復号できること、そしてその後平文結果を復号することを確認する責任があります。連鎖に悪意のある操作が導入されると、復号時に復号鍵が漏洩する可能性があります。幸いなことに、同型演算は公開され、検証することができます。

完全同型暗号化のシナリオ

このセクションでは、FHEが使用されるいくつかのシナリオと、それぞれのセットアップの利点と欠点について説明します。

アウトソーシングモード

この図では、オレンジの鍵のシンボルは復号化キー（およびその所有者）を示しています。FHEの暗号文は、復号化キーと同じ色のロックで表されます。個人データを提供する当事者はシリンダーで表されます：ここでは、アリスだけが個人データを提供しています。ボブ側では、評価関数と評価キーが公開され、緑の箱で描かれた計算は決定論的に行うことができます。誰もが計算を追跡し、主張された出力の暗号文が正しくないかどうかを検出できます。

これは、FHEのために公開された最初のユースケースです。それは、ハードウェアのセキュリティではなく、暗号化のセキュリティに基づくセキュアなエンクレーブにクラウドコンピューティングを変換することを目指しています。このような環境では、アリスはいくつかのプライベートデータを所有していますが、計算能力に制約があります。ボブは、より大きな計算能力を持つクラウドインスタンスを模倣します。ボブは追加のプライベートデータを提供しません。アリスは入力を暗号化して計算を外部に委託し、ボブは求められた（公開）関数を同型暗号化して暗号化された結果をアリスに送信します。

現在のハードウェアの能力では、アウトソーシングモードは実際には完全に一般的に使用するにはまだ少し遅いです - 非線形のユースケースでは通常、実行時間のオーバーヘッドファクターは100万倍、メモリのオーバーヘッドは1000倍です。しかし、FHEハードウェアは、このギャップを埋めるために現在開発中です。Darpa DPRIVEプロジェクトまたは暗号通貨ライト.

現在、アウトソーシング モードは、サーバー (Bob) に大規模なパブリック データベースがあり、クライアント (Alice) がクエリを発行し、クエリされるインデックスをプライベートのままにする必要がある PIR (Private Information Retrieval) のユース ケースで実際に使用されています。このようなPIRスキームは、準同型暗号化演算の線形性と互換性から多くの恩恵を受けますが、回路の乗法の深さが小さいため、計算コストは妥当な範囲内に維持されます。

この表は、アウトソーシングモードの利点と欠点を要約しています。

2者間計算モード

この図は以前と同じカラーコーディングを使用しています。今回は、ボブがプライベートデータをいくつか貢献して計算に参加しています。ボブ側での計算はもはや公に検証できなくなっており、赤い箱で示されています。このモードは正直だが好奇心旺盛なユースケースに制限されるべきです。

この新しいセットアップでは、唯一の違いは、ボブがいくつかのプライベートデータを使って計算に貢献することです。この場合、FHEは最小限の通信で強力な保証を提供する良い2者計算ソリューションであり、問い合わせ側に対して強力な保証を提供します。つまり、ボブはアリスのデータについて何も学ぶことはありませんし、アリスは計算の結果を学びます。

このシナリオの潜在的な応用例は、アリスとボブがお互いに富を知らせずに誰がより富裕かを知りたいというミリオネアの問題です。この問題の解決策は、電子商取引のアプリケーションで使用されています。

集約モード

これはアウトソーシングモードを改良したもので、多くの参加者からのデータをコンパクトに(参加者の数に比例して出力が増やされないという意味で)公開検証可能な方法で集約できます。一般的な使用法には、フェデレーテッドラーニングや電子投票などがあります。

クライアントサーバーモード

このセットアップは、コンピュートパーティが複数のクライアントに安全なコンピュートサービスを提供する、2者間コンピュートモードの改良版です。例えば、FHEはプライベートモデル予測サービス（プライベートモデルと入力を持つMLサービス）として使用できます。サーバーにはプライベートながら平文のモデルがあり、各クライアントは独自のデータを持ち、予測を実行したいと考えています。その結果、各クライアントは独自の秘密鍵で暗号化された予測を取得します。

ホモモーフィック暗号化は、計算される関数が正当であることをどのように保証していますか？

FHEは、各参加者がプロトコルに誠実に従うインセンティブがあるコラボレーションシナリオで使用する方が常に簡単です。FHEは、例えば、2つの異なる国にある同じグループの2つの取引主体間の統計を計算するために使用できます:GDPRなどの規制では、一部の統計の公開は許可されていますが、一般的には、すべての個別のデータを同じ場所に収集することはできません。この場合、FHEの使用が可能であり、すべての参加者にはプロトコルに誠実に従うインセンティブがあります。非コラボレーションのシナリオでは、関連する関数が計算されたことを確認する最も簡単な方法は、冗長性を導入することです。たとえば、アウトソーシングと集計のシナリオでは、準同型計算は完全に公開されており、決定論的にすることができます。2つ以上の独立したエンティティがまったく同じ出力暗号文を持つ限り、計算は正しく、結果は安全に復号化できます。冗長性が高ければ高いほど、結果に対する信頼性が高まりますが、これはもちろん効率とのトレードオフです。

また、計算パーティが入力と出力の暗号文にデジタル署名してFHEの結果を裏付けるとき、誰もが同じFHE計算を追跡し、証明が有効かどうかを確認できます。 FHE計算パーティによる不正行為の試みは公に捉えられ、不正と不正者を暴露する公に検証可能な証明書に関連付けることができます-これを強力な潜在的なセキュリティモデルと呼びます。

完全同型署名別の方法は、独立した検証者の必要性をなくし、一般的にはより多くのリソースを必要としますが、計算の正確性を検証する別の方法です。

完全同型暗号化は、最終的な受信者が中間変数ではなく最終結果のみを復号化することをどのように保証しますか？

これを行う最も簡単な方法は、復号キーの所有者が中間の暗号文にアクセスできないようにすることです。

二者間またはクライアント・サーバー間のシナリオで、アリスは入力を暗号化し、ボブは暗号文上で計算を行い、暗号化された出力をアリスに送信します。アリスは結果を解読することができますが、他の変数にアクセスすることはできません。

クラウド集約シナリオ、例えば多くの参加者が共通のクラウド上に暗号化された投票用紙を送信する電子投票の場合、別の手法が使われます: 復号キーは通常、単一の受信者に与えられるのではなく、復号権限の異なるメンバー間で秘密分散されます。この場合、復号は権限のメンバー間でのオンライン通信を含む多者間計算を実行することによって、特定の暗号文にのみトリガーすることができます。1人のメンバーが暗号文を復号することを拒否すると、復号は不可能です。これにより、権限のメンバー全員が合意した暗号文のみが復号できることが保証されます。

同型暗号化の構成要素

同型暗号化には3種類あります: 部分的な同型暗号化(PHE)、レベル付き同型暗号化(LHE)、完全な同型暗号化(FHE)です。部分的な同型暗号化は制限されたセットの関数の計算のみを許可します(例:合計のみ、線形関数のみ、双線形関数のみ)。一方、レベル付きおよび完全な同型暗号化は任意の回路、つまり、制御フローがデータに依存しない関数を評価できます。LHEでは、暗号パラメータは関数に依存し、回路の複雑さとともに増大し、それにより暗号文と鍵が大きくなります。FHEスキームでは、特定のパラメータセットに対して、つまり特定の鍵と暗号文のサイズに対して、算術ゲートやバイナリゲートで表される回路として表現できる任意の関数を評価できます。つまり、LHEとは異なり、評価する回路がますます大きくなっても、スキームのパラメータ(および鍵と暗号文)は大きくなりません。

言い換えれば、与えられた平文回路を準同型で実行できるかどうか、およびどの程度のコスト(時間とメモリのオーバーヘッド)で実行できるかという質問に対して、PHEは「いいえ」と答える可能性があります。LHEは「はい」と答えますが、複雑な回路に対して任意の高いコストを設定する場合があります。FHEも「はい」と答え、さらに、鍵、暗号化および復号化アルゴリズム、および平文回路が指定される前にゲートの普遍的なセットを準同型で評価する方法を提供します。したがって、FHEは、準同型評価のメモリと実行時間が元の平文回路に比例することを保証する唯一のモードです。これを行うために、今日知られているすべてのFHEスキームは、計算が行われるにつれてノイズが増すノイズの多い暗号文を処理します。実行された計算にノイズがオーバーフローして復号化エラーにつながるのを防ぐために、これらのスキームはブートストラップと呼ばれる非常にコストのかかる操作を定期的に実行し、ノイズを管理可能なレベルに戻します。各種類のスキームの詳細、ブートストラップ、および FHE コンパイラでノイズやその他のコストを最小限に抑える方法については、このシリーズの 2 番目のブログ投稿で詳しく説明します。

免責事項：

1. この記事は[から転載されましたcryptographycaffe], すべての著作権は元の作者に帰属します [Nicolas Gama と Sandra Guasch]. If there are objections to this reprint, please contact the ゲートラーンチームにお任せください。迅速に対応いたします。
2. 責任の免責事項：この記事で表現される意見および見解は著者個人のものであり、投資アドバイスを構成するものではありません。
3. 他の言語への記事の翻訳はGate Learnチームによって行われます。特に言及されていない限り、翻訳された記事のコピー、配布、または盗用は禁止されています。