格子ベースの暗号

格子ベース暗号は、構築自体またはセキュリティ証明のいずれかで格子を含む暗号プリミティブの構築に対する一般的な用語です。格子ベース構築は、ポスト量子暗号の重要な標準をサポートしています。^[1] RSA、ディフィー・ヘルマン、楕円曲線暗号システム などのより広く使用され知られている公開鍵方式（理論的には量子コンピュータでショアのアルゴリズムを使用して破ることができます）とは異なり、一部の格子ベース構築は、古典的コンピュータと量子コンピュータの両方による攻撃に耐性があるようです。さらに、多くの格子ベース構築は、十分に研究された特定の計算格子問題が効率的に解決できない という仮定の下で安全であると見なされています。

2024年にNISTは量子耐性暗号のためのモジュール格子ベースデジタル署名標準を発表しました。^[2]

1996年、ミクローシュ・アジタイは、十分に研究された格子問題の困難性に基づいてセキュリティを確立できる最初の格子ベースの暗号構造を導入しました。 ^[3]また、シンシア・ドワークは、短整数解法（SIS）として知られる特定の平均ケースの格子問題が、最悪のケースの格子問題と同じくらい解決が難しいことを示しました。^[4]その後、彼女は、SISの計算困難性と同等のセキュリティを持つ 暗号ハッシュ関数を示しました。

1998年、ジェフリー・ホフスタイン、ジル・ピファー、ジョセフ・H・シルバーマンは、 NTRUとして知られる格子ベースの公開鍵暗号化方式を導入した。^[5]しかし、彼らの方式は最悪の格子問題を解くのと同じくらい難しいとは知られていない。

最悪ケース困難性仮定の下で安全性が証明された最初の格子ベースの公開鍵暗号化方式は、2005 年にOded Regevによって^[6]エラー付き学習問題 (LWE)とともに導入されました。それ以来、多くのフォローアップ作業が Regev の安全性証明の改善^{[7] [8]}と元の方式の効率性の改善に重点が置かれてきました。^{[9] [10] [11] [12]} LWE と関連問題に基づく追加の暗号プリミティブの構築にさらに多くの作業が費やされてきました。たとえば、2009 年にCraig Gentry は格子問題に基づく最初の完全準同型暗号化方式を導入しました。^[13]

線型代数において、格子は の基底からのベクトルのすべての整数線形結合の集合です。言い換えると、 です。たとえば 、は の標準基底によって生成される格子です。重要なのは、格子の基底が一意ではないことです。たとえば、ベクトル、、はの代替基底を形成します。 ${\displaystyle L\subset \mathbb {R} ^{n}}$ ${\displaystyle \{\mathbf {b} _{1},\ldots ,\mathbf {b} _{n}\}}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle L={\Big \{}\sum a_{i}\mathbf {b} _{i}:a_{i}\in \mathbb {Z} {\Big \}}).}$${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle (3,1,4)}$${\displaystyle (1,5,9)}$${\displaystyle (2,-1,0)}$${\displaystyle \mathbb {Z} ^{3}}$

最も重要な格子ベースの計算問題は、最短ベクトル問題(SVP または GapSVP と呼ばれることもあります) です。これは、非ゼロの格子ベクトルの最小ユークリッド長さを近似することを要求します。この問題は、近似係数が の多項式であっても、量子コンピュータを使用しても、効率的に解くことは難しいと考えられています。この領域で SVP が実際に困難である場合、多くの (すべてではありませんが) 格子ベースの暗号構造は安全であることが知られています。 ${\displaystyle n}$

このセクションでは、プリミティブ別にグループ化された、選択された格子ベースのスキームを示します。

暗号化の目的で選択されたスキーム:

• GGH暗号化方式は、最近接ベクトル問題（CVP）に基づいています。1999年に、グエンは、この方式の設計に重大な欠陥があることを発表しました。^[14]
• NTRUEncrypt。

準同型暗号化の目的で選択された方式:

• ジェントリーの当初の計画。^[13]
• ブラーカースキーとヴァイクンタナタン。^{[15] [16]}

ハッシュ化の目的で選択された格子ベースの暗号化方式:

• スイフト。
• 格子ベースハッシュ関数（LASH）。^{[17] [18]}

鍵交換の目的で選択されたスキーム。鍵確立、鍵カプセル化、鍵カプセル化メカニズム (KEM) とも呼ばれます。

• CRYSTALS-Kyber [ ^19]は、エラー付きモジュール学習（module-LWE）に基づいて構築されています。Kyberは、2023年にNISTによって標準化に選ばれました。^[1] 2023年8月、NISTはFIPS 203（初期公開ドラフト）を公開し、Kyberバージョンをモジュールラティスベースのキーカプセル化メカニズム（ML-KEM）と呼び始めました。^[20]
• FrodoKEM ^{[21] [22] は、}エラー学習（LWE）問題に基づく方式です。FrodoKEMは、米国国立標準技術研究所（NIST）^{[1]が実施した標準化の呼びかけに参加し、プロセスの第3ラウンドまで存続しました。その後、パフォーマンスが低いという理由で破棄されました。2022年10月、暗号学者}ダニエル・J・バーンスタインに関連するTwitterアカウントが、frodokem640のセキュリティ問題を投稿しました。^[23]
• NewHopeはエラー付きリング学習（RLWE）問題に基づいています。^[24]
• NTRUプライム^[25]
• Peikertの研究は、エラー付きリング学習（RLWE）問題に基づいています。^[10]
• Saber ^[26]は丸めを伴うモジュール学習（モジュールLWR）問題に基づいています。

このセクションでは、デジタル署名を目的とした格子ベースの方式の選択をリストします。

• CRYSTALS-Dilithium ^{[27] [28]}は、エラー付きモジュール学習 (module-LWE) とモジュール短整数解 (module-SIS) に基づいて構築されています。Dilithium は NIST によって標準化の対象に選ばれました。^[1] NIST PQC チームを代表して Ray Perlner からのメッセージによると、NIST module-LWE 署名標準は Dilithium 仕様のバージョン 3.1 に基づく予定です。

• FalconはNTRU上の短整数解法（SIS）に基づいて構築されています。FalconはNISTによって標準化の対象に選ばれました。^{[29] [1]}
• GGH 署名スキーム。
• Güneysu、Lyubashevsky、Pöppelmannの研究は、エラー付きリング学習（RLWE）に基づいています。^[30]

• ミタカ、ファルコンの異形。^[31]
• NTRUSign。
• qTESLAは、エラー付きリング学習（RLWE）に基づいています。qTESLAスキームは、米国国立標準技術研究所（NIST）が実施した標準化の呼びかけに参加しました。^{[32] [1]}

CRYSTALS-Dilithium または単に Dilithium ^{[27] [28] は、} module-LWE と module-SIS に基づいて構築されています。Dilithium は、NIST によってデジタル署名標準の基礎として選択されました。^[1] NIST PQC チームを代表して書いた Ray Perlner からのメッセージによると、NIST module-LWE 署名標準は、Dilithium 仕様のバージョン 3.1 に基づく予定です。NIST による Dilithium 3.1 の変更は、署名 (ヘッジ署名) の追加のランダム性やその他の改善をサポートすることを目的としています。^[33]

Dilithium は、NIST がポスト量子暗号プロセスで最初に選択した 2 つのデジタル署名方式のうちの 1 つであり、もう 1 つは格子ではなくハッシュに基づく SPHINCS⁺ です。

2023年8月、NISTはFIPS 204（初期公開草案）を公開し、Dilithiumを「モジュール格子ベースのデジタル署名アルゴリズム」（ML-DSA）と呼び始めました。^[34]

Falco Strenzkeによれば、2023年10月時点でML-DSAはLibgcryptの一部として実装されているとのことだ。 ^[35]

格子ベースの暗号構造は、公開鍵 ポスト量子暗号にとって大きな可能性を秘めています。^[36]実際、公開鍵暗号の主な代替形式は、因数分解の困難性と関連問題に基づく方式と、離散対数と関連問題の困難性に基づく方式です。しかし、因数分解と離散対数問題はどちらも量子コンピュータで多項式時間で解けることが知られています。^[37]さらに、因数分解のアルゴリズムは離散対数のアルゴリズムを生み出す傾向があり、その逆も同様です。これにより、格子問題の困難性などの代替仮定に基づく構造の研究がさらに促進されます。

多くの格子ベースの暗号方式は、特定の格子問題の最悪ケースの^{困難性を前提とすれば安全であることが知られています。 [3] [6] [7]}つまり、暗号方式を無視できない確率で効率的に破ることができるアルゴリズムが存在する場合、任意の入力に対して特定の格子問題を解く効率的なアルゴリズムが存在します。ただし、実用的な格子ベースの構成（NTRUに基づく方式や効率的なパラメータを持つLWEに基づく方式など）では、意味のある削減ベースのセキュリティ保証は知られていません。

困難な問題からの縮約論によって提供されるセキュリティ レベルの評価 (推奨されるパラメータ サイズ、困難な問題の計算複雑性の標準的な推定値、縮約の手順の詳細な調査に基づく) は、具体的なセキュリティ、または実践指向の証明可能セキュリティと呼ばれることがあります。^[38]格子ベースの暗号システムの具体的なセキュリティを調査した著者は、そのようなシステムの証明可能セキュリティの結果は、パラメータの実用的な値に対して意味のある具体的なセキュリティを提供しないことを発見しました。^{[39] [40]}

多くの暗号プリミティブでは、格子または密接に関連したオブジェクトに基づく構造のみが知られています。これらのプリミティブには、完全準同型暗号化、^[13] 識別不能難読化、^[41] 暗号多重線形写像、および関数型暗号化が含まれます。^[41]

• 格子問題
• 間違いから学ぶ
• 準同型暗号
• 耐量子暗号
• エラーのあるリング学習
• エラーキー交換によるリング学習

• Oded Goldreich、Shafi Goldwasser、Shai Halevi。「格子縮約問題からの公開鍵暗号システム」。Crypto '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology、112～131 ページ、ロンドン、イギリス、1997 年。Springer-Verlag。
• Oded Regev. 格子ベースの暗号化。Advances in cryptology (CRYPTO)、131～141 ページ、2006 年。