Learning With Errors：困難問題

Learning With Errors（LWE）問題は、ポスト量子暗号の基盤としてOded Regevによって2005年に提案されました。Z_q上のランダム行列Aと、b = As + eというベクトルbが与えられたとき、秘密ベクトルsを求めることが目標です。ベクトルeは離散ガウス分布から抽出された小さな誤差であり、この問題を計算上困難にしています。

LWE問題では、Aは素数を法とするqに対してZ_q上から一様にサンプリングされたm x nのランダム行列です。秘密鍵sはn次元ベクトルであり、eは各要素が狭いガウス分布から生成される小さな誤差ベクトルです。Aの構造を知っていたとしても、攻撃者がbを一様ランダムなベクトルと見分ける助けにはなりません。

LWEには、標準的な定式化が2つあります。探索LWEでは、多数のサンプル（A, b）が与えられたときに秘密鍵sを復元することを求めます。判定LWEでは、サンプル（A, As + e）と一様ランダムなペア（A, u）を見分けることを求めます。この2つの定式化は多項式時間同値です。つまり、一方を解くアルゴリズムを変換して、もう一方を解くことができます。

LWEの誤差項は、標準偏差sigmaでパラメータ化された整数上の離散ガウス分布から生成されます。sigmaの値が小さいと、eはqと比べて十分小さくなるため、bはAs mod qとほぼ同じに見えます。sigmaが0なら誤差は存在せず、ガウス消去法でシステムを解けてしまうため、誤差は困難性に不可欠です。

Regevは、注目すべき帰着を証明しました。それは、平均的なLWEサンプルを解くことが、格子上の最短ベクトル問題（SVP）の最悪時インスタンスを解くことと少なくとも同程度に難しいというものです。つまり、LWEを効率的に破れるなら、任意の格子問題を効率的に解けることになります。最悪時のSVPを多項式時間で解く古典アルゴリズムや量子アルゴリズムは、現在知られていません。

RSAや楕円曲線暗号とは異なり、LWEに対して指数的な高速化をもたらす既知の量子アルゴリズムはありません。Groverのアルゴリズムによる高速化は高々二次的であり、最良の量子格子アルゴリズム（BKZの変種）も、適切に選ばれたパラメータのLWEを破ることはできません。このため、LWEはポスト量子セキュリティの強固な基盤となります。

LWEの安全性は、3つのパラメータによって決まります。秘密鍵の長さである次元n、法q、そして誤差の標準偏差sigmaです。nを大きくし、q/sigmaの比を小さくすると、安全性が高まります。128ビットのポスト量子セキュリティでは、n = 1024、qは約12289、sigmaは約3.2とするのが一般的です。具体的な安全性の評価には、Albrechtらのlattice estimatorツールが使用されます。

短整数解（SIS）問題は、署名で使用される関連する格子困難性の仮定です。Z_q上のランダム行列Aが与えられたとき、Ax = 0 mod qを満たす短い非ゼロベクトルxを見つけます。SISは格子暗号におけるハッシュ関数や署名方式の基盤であり、暗号化や鍵カプセル化を支えるLWEを補完するものです。

単純なLWE暗号方式は、次のように動作します。公開鍵は（A, b = As + e）で、秘密鍵はsです。ビットmを暗号化するため、送信者はランダムな二値ベクトルrに対して、（u, v）=（A^T r, b^T r + m * floor(q/2)）を計算します。復号ではv - s^T uを計算し、丸めることでmを復元します。この方式は、LWE仮定の下でIND-CPA安全性を実現します。

LWEにより、基本的な暗号化以外にも幅広い暗号構成が可能になりました。これには、完全準同型暗号（FHE）、IDベース暗号（IBE）、属性ベース暗号（ABE）、鍵交換プロトコルなどがあります。CRYSTALS-Kyber（現在はML-KEM、FIPS 203として標準化済み）は、実際に最も広く導入されているLWEベースの方式です。

LWEベースの暗号技術は、すでに本番システムへの導入が始まっています。GoogleとCloudflareは、2018年から2020年にかけてKyberを使用したTLSの実験を実施しました。ChromeとFirefoxは、2024年にハイブリッドTLSハンドシェイクでML-KEM-768のサポートを追加しました。Signal Protocolは、前方秘匿性のためにML-KEM-1024を使用するポスト量子レイヤー（PQXDH）を追加し、将来の量子コンピューターに対して長期的なメッセージの機密性を保護しています。

LWE問題の困難性の保証を最も適切に説明しているのは、次のうちどの記述ですか。

LWEは、格子問題からの強力な最悪時帰着に裏付けられた、最もよく研究されているポスト量子困難性の仮定の1つです。その3つのパラメータ（n、q、sigma）が、安全性と性能のトレードオフを決定します。LWEは量子攻撃に耐性があり、NIST標準化方式の基盤となっています。LWEを理解することは、ML-KEMやML-DSAを含む、現代の格子ベース暗号を学ぶための入り口です。