Learning With Errors（LWE）の基礎

Regev（2005）によるLearning With Errors（LWE）では、Z_q上の多数のノイズを含む線形方程式が与えられたとき、秘密ベクトルsを求めます。ノイズeは小さいものの、ガウス消去法を妨げます。ノイズがなければ連立方程式は簡単に解けますが、ごく小さなノイズでも計算上は困難になります。

秘密s ∈ Z_q^n。攻撃者は、a_i ∈ Z_q^nがランダムで、b_i = + e_i mod qを満たすサンプル(a_i, b_i)を受け取ります。e_iは分布χから得られる小さなノイズです（例: σ = √nのガウス分布）。課題は、多項式個のサンプルからsを求めることです。

ノイズがない場合: b_i = mod qです。ガウス消去法によってO(n^3)でsを復元できます。ノイズがある場合は、方程式が1つでも誤ると消去計算全体が破綻します。ノイズは、鍵を使えば復号できる程度に小さい一方で、暗号解析を防げるほど十分に大きく設定されています。

Regevは、量子還元によってLWEが最悪時の格子問題（SIVP、GapSVP）に帰着できることを証明しました。つまり、LWEが破られると、多くの困難な格子問題も解かれることになります。しかし、格子問題に対する量子アルゴリズムはまだ知られていません。LWEは耐量子安全です。

RLWEでは、Z_q^nを円分多項式fに対する環Z_q[x]/(f(x))で置き換えます。1つのRLWEサンプルにn個の方程式を組み込めるため、はるかに効率的です。RLWEは、Kyber（KEM）、Dilithium（署名）、BFV/BGV/CKKS HE方式の基盤です。

セキュリティは、n（次元、通常は512-2048）、q（法、1024-2^60）、σ（ノイズの標準偏差）に依存します。nが大きいほど、またσ/q比が小さいほど、問題は困難になります。NISTの耐量子標準では、k個のモジュール（k=2,3,4）を持つn=256（モジュール次元）が使用されています。

公開鍵: (A, b=As+e)。ビットmを暗号化するには、ランダムなrを選び、暗号文(u=A^T r, v = b^T r + m*q/2)を計算します。復号では、v - s^T u = e^T r + m*q/2 ≈ m*q/2となります。最も近いmに丸めます。ノイズeによって、暗号化中は暗号文に含まれるmが隠されます。

Decision-LWEでは、(a, As+e)と、uが一様ランダムな(a, u)を識別します。LWEの困難性を仮定すると、これらは計算量的に識別不能です。これは意味論的安全性の基盤であり、秘密鍵を持たない攻撃者から見ると、暗号文はランダムなノイズのように見えます。

既知の最良の攻撃は、BKZ（Block Korkine-Zolotarev）格子簡約です。計算量は準指数時間ですが、多項式時間ではありません。BKZ-βには2^{0.292β}回の操作が必要です。LWE-512のBKZに対するセキュリティは約128ビットです。BKZに対する量子高速化は知られていません。

Module-LWE（Kyberで使用）は、ランクkのモジュール上のRLWEです。k=2では512ビット、k=3では768ビット、k=4では1024ビットのセキュリティに対応できる柔軟性があります。セキュリティと性能はkに応じて変化します。NISTはKyber（ML-KEMに改称）をPQC標準として選定しました。

RSA/ECCのセキュリティは、整数因数分解や離散対数に基づいており、Shorによって量子計算に対して脆弱です。LWEのセキュリティは、最悪時の格子問題に基づいており、既知の量子高速化はありません。鍵サイズは、LWEが約1 KBであるのに対し、RSA-2048は256バイトです。LWEはより大きいものの、耐量子性があります。

多数のサンプルがあってもLWEを解くことが難しいのはなぜですか？

LWEは、ノイズを含む線形方程式から秘密sを求める問題であり、量子計算でも困難です。RLWEは効率化のために多項式環を使用します。Kyber、Dilithium、HE方式の基盤となっています。次は、整数演算用のBGVおよびBFV HE方式について学びます。