準同型暗号

準同型暗号化は、暗号化されたデータを復号化せずに計算を実行できる暗号化形式です。計算結果は暗号化された形式で残され、復号化されると、暗号化されていないデータで操作を実行した場合に生成された出力と同一の出力が生成されます。準同型暗号化は、プライバシーを保護しながら外部委託されたストレージや計算に使用できます。これにより、データを暗号化し、暗号化されたまま商用クラウド環境に処理を委託できます。

準同型暗号化では、平文でデータを処理する必要がなくなるため、攻撃者が特権昇格を利用して処理中のデータにアクセスする攻撃を防ぐことができます。^[1]

医療情報などの機密データの場合、準同型暗号化を使用すると、データ共有を妨げるプライバシー障壁を取り除いたり、既存のサービスのセキュリティを強化したりすることで、新しいサービスが可能になります。たとえば、医療における予測分析は、医療データのプライバシーに関する懸念から、サードパーティのサービスプロバイダーを介して適用することが難しい場合があります。しかし、予測分析サービスプロバイダーが復号化キーを持たずに暗号化されたデータで操作できれば、これらのプライバシーに関する懸念は軽減されます。さらに、サービスプロバイダーのシステムが侵害された場合でも、データは安全に保たれます。^[2]

準同型暗号化は、秘密鍵にアクセスせずに暗号化されたデータに対して計算を行うための追加の評価機能を備えた暗号化形式です。このような計算の結果は暗号化されたままです。準同型暗号化は、公開鍵暗号化の拡張として考えることができます^{[どのように? ]}。準同型とは代数における準同型性を指します。暗号化関数と復号化関数は、平文空間と暗号文空間の間の準同型性として考えることができます。

準同型暗号化には、暗号化されたデータに対して異なるクラスの計算を実行できる複数のタイプの暗号化方式が含まれます。^[3]計算はブール回路または算術回路として表されます。準同型暗号化の一般的なタイプには、部分準同型、やや準同型、レベル付き 完全準同型、完全準同型暗号化などがあります。

• 部分準同型暗号化には、加算や乗算など、1 種類のゲートのみで構成される回路の評価をサポートするスキームが含まれます。
• 準同型暗号化方式では、2 種類のゲートを評価できますが、回路のサブセットに対してのみ評価できます。
• レベル化された完全準同型暗号化は、制限された（事前に決定された）深さの複数の種類のゲートで構成された任意の回路の評価をサポートします。
• 完全準同型暗号化(FHE) は、無制限の深さの複数の種類のゲートで構成された任意の回路の評価を可能にし、準同型暗号化の最も強力な概念です。

準同型暗号化方式の大半では、暗号化されたデータに対して計算を実行する際の主な実際的な制限は、回路の乗法深度です。準同型暗号化方式は本質的に柔軟性があります。柔軟性の点では、準同型暗号化方式は非準同型暗号化方式よりもセキュリティ特性が弱くなります。

準同型暗号方式は、さまざまなアプローチを使用して開発されてきました。具体的には、完全準同型暗号方式は、基礎となるアプローチに対応する世代にグループ化されることがよくあります。^[4]

完全準同型暗号化方式を構築する問題は、RSA方式の発表から1年以内の1978年に初めて提案されました。^[5] 30年以上もの間、解決策が存在するかどうかは不明でした。その間、部分的な結果として次の方式が生まれました。

• RSA暗号システム (無限数のモジュラー乗算)
• エルガマル暗号システム（無限数のモジュラー乗算）
• Goldwasser–Micali 暗号システム(排他的論理和演算の回数に制限なし)
• ベナロー暗号システム（無限数のモジュラー加算）
• Paillier 暗号システム(無限数のモジュラー加算)
• サンダー・ヤング・ヤングシステム（20年以上を経て対数深度回路の問題を解決）^[6]
• ボネ・ゴー・ニッシム暗号（加算は無制限だが乗算は1回まで）^[7]
• イシャイ・パスキン暗号（多項式サイズ分岐プログラム）^[8]

クレイグ・ジェントリーは、格子ベースの暗号を使用して、2009年に完全な準同型暗号化方式の最初の妥当な構成を説明しました。 ^[9]ジェントリーの方式は、暗号文に対する加算と乗算の両方の演算をサポートしており、そこから任意の計算を実行する回路を構築することができます。構築は、暗号化されたデータに対する低次多項式の評価に限定された、ある程度準同型な暗号化方式から始まります。これは、各暗号文が何らかの意味でノイズが多く、このノイズは暗号文を加算および乗算するにつれて大きくなり、最終的にはノイズによって結果として得られる暗号文が解読不能になるために制限されます。

次に、ジェントリーは、この方式をわずかに変更してブートストラップ可能にする方法、つまり、独自の復号回路を評価し、さらに少なくとも 1 つの操作を実行できるようにする方法を示します。最後に、彼は、ブートストラップ可能なある程度準同型な暗号化方式は、再帰的な自己埋め込みによって完全に準同型な暗号化に変換できることを示します。ジェントリーの「ノイズの多い」方式では、ブートストラップ手順は、復号手順を準同型に適用することで暗号文を効果的に「更新」し、以前と同じ値を暗号化するがノイズの少ない新しい暗号文を取得します。ノイズが大きくなりすぎるたびに暗号文を定期的に「更新」することで、ノイズをあまり増やさずに任意の数の加算と乗算を計算できます。

ジェントリーは、理想格子上の特定の最悪ケース問題と、スパース（または低重み）部分集合和問題という2つの問題の困難性を前提として、この方式のセキュリティを確保した。ジェントリーの博士論文^[10]には、さらに詳しい情報が記載されている。ジェントリーのオリジナルの暗号システムのジェントリー・ハレヴィ実装では、基本ビット操作あたり約30分かかると報告されている^[11] 。その後の広範な設計と実装作業により、これらの初期の実装に比べて実行時パフォーマンスが桁違いに向上した。

2010年、Marten van Dijk、Craig Gentry、Shai Halevi、Vinod Vaikuntanathanは、2番目の完全準同型暗号化方式^[12]を発表しました。これは、Gentryの構築ツールの多くを使用しますが、理想格子を必要としません。代わりに、彼らは、Gentryの理想格子ベースの方式のやや準同型コンポーネントを、整数を使用する非常に単純なやや準同型スキームに置き換えることができることを示しています。したがって、このスキームは、概念的にはGentryの理想格子スキームよりも単純ですが、準同型演算と効率に関しては同様の特性を持っています。Van Dijkらの研究におけるやや準同型コンポーネントは、2008年にLevieilとNaccacheによって提案された暗号化スキーム^[13]や、 1998年にBram Cohenによって提案された暗号化スキームに似ています。 ^[14]

しかしながら、コーエンの方法は加法準同型でさえありません。ルヴィエイユ・ナカシェ方式は加算のみをサポートしていますが、少数の乗算もサポートするように変更できます。ヴァン・ダイクらの方式の多くの改良と最適化は、ジャン＝セバスチャン・コロン、タンクレード・ルポイント、アヴラディップ・マンダル、デビッド・ナカシェ、およびメディ・ティボウシによる一連の研究で提案されました。^{[15] [16] [17] [18]}これらの研究のいくつかには、結果として得られた方式の実装も含まれていました。

この世代の準同型暗号システムは、2011 年から 2012 年にかけてZvika Brakerski、Craig Gentry、Vinod Vaikuntanathanらによって開発された技術から派生したものです。これらの技術革新により、はるかに効率的な、ある程度準同型な暗号システムと完全に準同型な暗号システムが開発されました。これらには次のものが含まれます。

• Brakerski-Gentry-Vaikuntanathan (BGV、2011) スキーム、^[19] Brakerski-Gentry-Vaikuntanathan の技術に基づいています。^[20]
• ロペス・アルト、トロマー、ヴァイクンタナサンによるNTRUベースのスキーム（LTV、2012） ^[21]
• Brakerski/Fan-Vercauteren (BFV、2012) スキーム^[22] Brakerski のスケール不変暗号システムに基づいています。^[23]
• Bos、Lauter、Loftus、Naehrig (BLLN、2013)によるNTRUベースの方式^[24]は、 LTVとBrakeskiのスケール不変暗号システムに基づいて構築されています。^[23]

これらの方式のほとんどの安全性は、(リング)エラー付き学習(RLWE)問題の困難性に基づいていますが、LTV方式とBLLN方式はNTRU計算問題の過剰拡張^[25]変種に依存しています。このNTRU変種はその後、サブフィールド格子攻撃に対して脆弱であることが示され、^{[26] [25]、}この2つの方式が実際には使用されなくなったのはそのためです。

第 2 世代の暗号システムはすべて、依然として Gentry の元の構築の基本的な青写真に従っています。つまり、最初にある程度準同型な暗号システムを構築し、次にブートストラップを使用してそれを完全に準同型な暗号システムに変換します。

第二世代暗号システムの特徴は、準同型計算中のノイズの増加がずっと緩やかであることです。Craig Gentry、Shai Halevi、Nigel Smartによる追加の最適化により、ほぼ最適な漸近複雑度を持つ暗号システムが実現しました。セキュリティパラメータで暗号化されたデータに対する操作の実行は、複雑度が のみです。^{[27] [28] [29]}これらの最適化は、多数の平文値を単一の暗号文にまとめ、これらすべての平文値をSIMD形式で操作できるようにする Smart-Vercauteren 手法に基づいています。^[30]これらの第二世代暗号システムの進歩の多くは、整数暗号システムにも移植されました。^{[17] [18]}${\displaystyle T}$${\displaystyle k}$${\displaystyle T\cdot \mathrm {polylog} (k)}$

第 2 世代の方式のもう 1 つの際立った特徴は、ブートストラップを呼び出さずにレベル FHE モードで動作しても、多くのアプリケーションで十分に効率的であることです。

2013年、クレイグ・ジェントリー、アミット・サハイ、ブレント・ウォーターズ（GSW）は、準同型乗算における高価な「再線形化」ステップを回避するFHEスキームを構築するための新しい手法を提案した。^[31]ズビカ・ブラケルスキとヴィノド・ヴァイクンタナサンは、特定の種類の回路では、GSW暗号システムはノイズの増加率がさらに遅く、したがって効率が良く、セキュリティが強化されることを観察した。 [ ^32]ジェイコブ・アルペリン・シェリフとクリス・ペイカートは、この観察に基づいて非常に効率的なブートストラッピング手法を説明した。^[33]

これらの技術はさらに改良され、GSW暗号システムの効率的なリング型であるFHEW（2014）^[34]とTFHE（2016）^[35]が開発されました。FHEW方式は、すべての操作の後に暗号文を更新することで、ブートストラップ時間を1秒未満に短縮できることを初めて示しました。FHEWは、暗号化されたデータに対してブールゲートを計算する新しい方法を導入し、ブートストラップを大幅に簡素化し、ブートストラップ手順のバリアントを実装しました。^[33] FHEWの効率は、FHEWと同様の方法を使用して ブートストラップ手順のリング型^[36]を実装するTFHE方式によってさらに改善されました。

2016 年に Cheon、Kim、Kim、Song (CKKS) ^{[37] は、}ブロック浮動小数点演算と呼ばれる特殊な固定小数点演算をサポートする近似準同型暗号化方式を提案しました。CKKS 方式には、乗算後に暗号化されたメッセージを縮小する効率的な再スケーリング操作が含まれています。比較すると、このような再スケーリングには BGV 方式と BFV 方式でのブートストラップが必要です。再スケーリング操作により、CKKS 方式は多項式近似を評価するための最も効率的な方法となり、プライバシー保護機械学習アプリケーションの実装に適したアプローチとなっています。この方式では、非決定論的および決定論的な近似誤差がいくつか発生するため、実際には特別な処理が必要です。^[38]

2020年に発表されたBaiyu LiとDaniele Micciancioによる論文では、CKKSに対する受動的な攻撃について論じられており、復号結果が共有されるシナリオでは標準的なIND-CPA定義では不十分な可能性があることが示唆されている。^[39]著者らは、この攻撃を4つの最新の準同型暗号化ライブラリ（HEAAN、SEAL、HElib、PALISADE）に適用し、いくつかのパラメータ設定で復号結果から秘密鍵を復元できることを報告している。著者らはまた、これらの攻撃に対する緩和戦略を提案しており、論文には責任ある開示が含まれており、論文が公開される前に準同型暗号化ライブラリがすでに攻撃に対する緩和策を実装していたことを示唆している。準同型暗号化ライブラリに実装された緩和戦略に関する詳細情報も公開されている。^{[40] [41]}

以下の例では、表記法はメッセージの暗号化を表すために使用されます。 ${\displaystyle {\mathcal {E}}(x)}$${\displaystyle x}$

パディングなしの RSA

RSA公開鍵が係数と暗号化指数を持つ場合、メッセージの暗号化は で与えられます。準同型性は次のように表されます。 ${\displaystyle n}$${\displaystyle e}$${\displaystyle m}$${\displaystyle {\mathcal {E}}(m)=m^{e}\;{\bmod {\;}}n}$

${\displaystyle {\begin{aligned}{\mathcal {E}}(m_{1})\cdot {\mathcal {E}}(m_{2})&=m_{1}^{e}m_{2 }^{e}\;{\bmod {\;}}n\\[6pt]&=(m_{1}m_{2})^{e}\;{\bmod {\;}}n\\[6pt]&={\mathcal {E}}(m_{1}\cdot m_{2})\end{aligned}}}$

エルガマル

エルガマル暗号システムでは、生成元 を持つの巡回群において、公開鍵が（ここで、 が秘密鍵）である場合、メッセージの暗号化は、あるランダム に対して となる。準同型性は、 ${\displaystyle G}$${\displaystyle q}$${\displaystyle g}$${\displaystyle (G,q,g,h)}$${\displaystyle h=g^{x}}$${\displaystyle x}$${\displaystyle m}$${\displaystyle {\mathcal {E}}(m)=(g^{r},m\cdot h^{r})}$${\displaystyle r\in \{0,\ldots ,q-1\}}$

${\displaystyle {\begin{aligned}{\mathcal {E}}(m_{1})\cdot {\mathcal {E}}(m_{2})&=(g^{r_{1}},m_{1}\cdot h^{r_{1}})(g^{r_{2}},m_{2}\cdot h^{r_{2}})\\[6pt]&=(g^{r_{1}+r_{2}},(m_{1}\cdot m_{2})h^{r_{1}+r_{2}})\\[6pt]&={\mathcal {E}}(m_{1}\cdot m_{2}).\end{aligned}}}$

ゴールドヴァッサー・ミカリ

ゴールドワッサー・ミカリ暗号システムでは、公開鍵が法で2次非剰余の場合、あるランダム に対してビットの暗号化は となる。準同型性は次のように表される。 ${\displaystyle n}$${\displaystyle x}$${\displaystyle b}$${\displaystyle {\mathcal {E}}(b)=x^{b}r^{2}\;{\bmod {\;}}n}$${\displaystyle r\in \{0,\ldots ,n-1\}}$

${\displaystyle {\begin{aligned}{\mathcal {E}}(b_{1})\cdot {\mathcal {E}}(b_{2})&=x^{b_{1}}r_{1 }^{2}x^{b_{2}}r_{2}^{2}\;{\bmod {\;}}n\\[6pt]&=x^{b_{1}+b_{2}}(r_{1}r_{2})^{2}\;{\bmod {\;}} n\\[6pt]&={\mathcal {E}}(b_{1}\oplus b_{2}).\end{aligned}}}$

ここで、 は2 を法とする加算 (つまり、排他的論理和) を表します。 ${\displaystyle \oplus}$

ベナロ

ベナロー暗号システムでは、公開鍵が の法で のブロックサイズを持つ基数である場合、メッセージの暗号化は、あるランダム に対して となる。準同型性は、 ${\displaystyle n}$${\displaystyle g}$${\displaystyle c}$${\displaystyle m}$${\displaystyle {\mathcal {E}}(m)=g^{m}r^{c}\;{\bmod {\;}}n}$${\displaystyle r\in \{0,\ldots ,n-1\}}$

${\displaystyle {\begin{aligned}{\mathcal {E}}(m_{1})\cdot {\mathcal {E}}(m_{2})&=(g^{m_{1}}r_{ 1}^{c})(g^{m_{2}}r_{2}^{c})\;{\bmod {\;}}n\\[6pt]&=g^{m_{1}+m_{2}}(r_{1}r_{2})^{c}\;{\bmod {\;}} n\\[6pt]&={\mathcal {E}}(m_{1}+m_{2}\;{\bmod {\;}}c).\end{aligned}}}$

パイエ

Paillier暗号システムでは、公開鍵が係数で基数がの場合、メッセージの暗号化は、ランダムな に対して となる。準同型性は、 ${\displaystyle n}$${\displaystyle g}$${\displaystyle m}$${\displaystyle {\mathcal {E}}(m)=g^{m}r^{n}\;{\bmod {\;}}n^{2}}$${\displaystyle r\in \{0,\ldots ,n-1\}}$

${\displaystyle {\begin{aligned}{\mathcal {E}}(m_{1})\cdot {\mathcal {E}}(m_{2})&=(g^{m_{1}}r_{ 1}^{n})(g^{m_{2}}r_{2}^{n})\;{\bmod {\;}}n^{2}\\[6pt]&=g^{m_{1}+m_{2}}(r_{1}r_{2})^{n}\;{\bmod { \;}}n^{2}\\[6pt]&={\mathcal {E}}(m_{1}+m_{2}).\end{aligned}}}$

その他の部分準同型暗号システム

• 岡本・内山暗号方式
• ナカチェ・シュテルン暗号
• ダムゴード・ユリック暗号
• Sander-Young-Yung 暗号化方式
• Boneh-Goh-Nissim 暗号システム
• イシャイ・パスキン暗号
• ジョイ・リベール暗号システム^[42]
• カスタニョス・ラギヨーミ暗号^[43]

暗号文に対する任意の計算をサポートする暗号システムは、完全準同型暗号 (FHE) として知られています。このような方式では、任意の機能を実現するプログラムを構築することができ、暗号化された入力に対して実行することで、結果の暗号化を生成できます。このようなプログラムは入力を復号化する必要がないため、信頼できない当事者が入力や内部状態を明らかにすることなく実行できます。完全準同型暗号システムは、たとえばクラウドコンピューティングのコンテキストで、プライベートな計算をアウトソーシングする際に大きな実用的な意味を持ちます。^[44]

第 2 世代 (BGV/BFV)、第 3 世代 (FHEW/TFHE)、および第 4 世代 (CKKS) FHE スキームを実装するオープンソース FHE ライブラリのリストを以下に示します。

完全準同型暗号化方式のオープンソース実装はいくつかあります。第 2 世代および第 4 世代の FHE 方式の実装は、通常、レベル FHE モードで動作し (一部のライブラリではブートストラップがまだ使用可能)、効率的なSIMDのようなデータのパッキングをサポートします。これらは通常、暗号化された整数または実数/複素数の計算に使用されます。第 3 世代の FHE 方式の実装は、各操作の後にブートストラップされることが多いですが、パッキングのサポートは限られています。これらは当初、暗号化されたビット上のブール回路を計算するために使用されていましたが、整数演算と単変数関数評価をサポートするように拡張されました。第 2 世代、第 3 世代、第 4 世代の方式のどれを使用するかは、入力データの種類と目的の計算によって異なります。

2017年にはIBM、マイクロソフト、インテル、NISTなどの研究者らがオープンな準同型暗号標準化コンソーシアムを設立し、コミュニティセキュリティ準同型暗号標準を維持している。^{[67] [68] [69]}

• 準同型秘密分散
• ネットワークコーディングのための準同型署名
• プライベート生体認証
• 完全準同型スキームを使用した検証可能なコンピューティング
• クライアント側の暗号化
• 機密コンピューティング
• 検索可能な対称暗号化
• 安全なマルチパーティ計算
• フォーマット保存暗号化
• 多態的コード
• プライベートセットの交差点

• FHE.org コミュニティ (カンファレンス、ミートアップ、ディスカッション グループ)
• Daniele Micciantio の FHE リファレンス
• Vinod Vaikuntanathan の FHE リファレンス
• 「暗号空間のアリスとボブ」。アメリカン・サイエンティスト。2012年9月。 2018年5月8日閲覧。
• GitHubで管理されている準同型暗号化実装のリスト