耐量子暗号入門：Learning With Errors（LWE）とRegev暗号をPythonで実装し、なぜ量子コンピュータに耐えるかを実験する

はじめに

https://yuhi-sa.github.io/posts/20260614_cryptography_roadmap/1/ では「Post-Quantum Cryptography（CRYSTALS-Kyber / Dilithium）」を将来追加予定の最後のプレースホルダとして挙げていました。本記事ではこれを実装します。https://yuhi-sa.github.io/posts/20260225_rsa/1/ の素因数分解、https://yuhi-sa.github.io/posts/20260614_diffie_hellman/1/ や https://yuhi-sa.github.io/posts/20260702_elliptic_curve_cryptography/1/ の離散対数問題は、いずれもShorのアルゴリズムによって量子コンピュータ上では多項式時間で解けてしまうことが知られています。本記事では、なぜLearning With Errors（LWE）問題が量子コンピュータにも耐えると考えられているのかを、Regev暗号（LWEベースの公開鍵暗号）のフルスクラッチ実装と数値実験で確認します。

なぜ量子コンピュータが脅威なのか：Shorのアルゴリズム

RSA・Diffie-Hellman・ECCはいずれも、特定の数論的問題（素因数分解・離散対数問題）が古典コンピュータでは効率的に解けないという仮定の上に安全性が成り立っています。1994年にPeter Shorが示したのは、量子コンピュータ上ではこれらの問題を多項式時間で解けるアルゴリズムが存在するということでした。つまり、十分な規模の量子コンピュータが実現すれば、現在使われているRSA・DH・ECCベースの暗号は原理的にすべて解読可能になります。これが、量子コンピュータにも耐性を持つ**耐量子暗号（Post-Quantum Cryptography, PQC）**への移行が進められている理由です。NISTは2024年に格子暗号ベースのCRYSTALS-Kyber（鍵交換、FIPS 203として標準化）とCRYSTALS-Dilithium（署名、FIPS 204）を標準として確定しました。

LWE問題（Learning With Errors）

Kyberを含む多くの耐量子暗号方式の基盤が、Oded Regevが2005年に提案したLWE問題です。直感的には「連立一次方程式に少しだけノイズを混ぜると、解くのが劇的に難しくなる」という性質を利用します。

LWE問題の定義：秘密ベクトル \(\mathbf{s} \in \mathbb{Z}_q^n\) 、ランダム行列 \(A \in \mathbb{Z}_q^{m \times n}\) 、小さな誤差ベクトル \(\mathbf{e} \in \mathbb{Z}_q^m\) （各成分は正規分布などから生成）に対して、

\[ \mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod{q} \tag{1} \]

が与えられたとき、\((A, \mathbf{b})\) から \(\mathbf{s}\) を求めよ、という問題です。もし誤差 \(\mathbf{e}\) がなければ、\(m \geq n\) のとき単純な連立一次方程式（modular線形代数）を解くだけで \(\mathbf{s}\) が一意に求まります。しかし誤差が加わると、この単純な解法は機能しなくなり、格子問題として知られる困難な問題（最短ベクトル問題など）に帰着することが示されています。この格子問題は、現時点で知られている量子アルゴリズム（Shorのアルゴリズムを含む）では効率的に解けないと考えられています。

Regev暗号：LWEベースの公開鍵暗号（1ビット版）

LWE問題の困難性を使って、以下のように公開鍵暗号を構成できます（Regev, 2005の簡略版）。

鍵生成：秘密鍵 \(\mathbf{s} \in \mathbb{Z}_q^n\) をランダムに選ぶ。公開鍵は LWE インスタンス \((A, \mathbf{b} = A\mathbf{s} + \mathbf{e})\) 。

暗号化（1ビット \(b \in \{0,1\}\) を暗号化）：ランダムな部分集合 \(\mathbf{r} \in \{0,1\}^m\) を選び、

\[ \mathbf{u} = \mathbf{r}^\top A \pmod q, \qquad v = \mathbf{r}^\top \mathbf{b} + b \cdot \lfloor q/2 \rfloor \pmod q \tag{2} \]

を暗号文とする。

復号：

\[ v - \mathbf{u}^\top \mathbf{s} = \mathbf{r}^\top\mathbf{e} + b\cdot\lfloor q/2\rfloor \pmod q \tag{3} \]

を計算する。\(\mathbf{r}^\top\mathbf{e}\) は小さい値（誤差の和）なので、結果が \(0\) に近ければ \(b=0\) 、\(q/2\) に近ければ \(b=1\) と判定できます。

Python実装

import numpy as np

n, q, m, sigma = 32, 3329, 128, 2.0  # トイパラメータ（qはKyberと同じ値を採用）
rng = np.random.default_rng(20260715)  # 本記事の全実験で固定するシード

def sample_error(size, sigma, q):
    e = np.round(rng.normal(0, sigma, size)).astype(np.int64) % q
    return e

def keygen():
    s = rng.integers(0, q, size=n)
    A = rng.integers(0, q, size=(m, n))
    e = sample_error(m, sigma, q)
    b = (A @ s + e) % q
    return (A, b), s

def encrypt(pub, bit, q):
    A, b = pub
    r = rng.integers(0, 2, size=A.shape[0])
    u = (r @ A) % q
    v = (int(r @ b) + bit * (q // 2)) % q
    return u, v

def decrypt(sk, ct, q):
    u, v = ct
    raw = (v - int(u @ sk)) % q
    return 1 if abs(raw - q // 2) < q // 4 else 0

正当性の導出：ノイズ蓄積と復号条件

decrypt 関数は abs(raw - q // 2) < q // 4 という閾値判定で1ビットを復元します。式(3)より \(\mathtt{raw} = \mathbf{r}^\top\mathbf{e} + b\cdot\lfloor q/2\rfloor \pmod q\) なので、この判定が正しいbitを返すための必要十分条件は、mod \(q\) に還元する前の符号付き整数として

\[ |\mathbf{r}^\top\mathbf{e}| < q/4 \tag{4} \]

が成り立つことです（\(b=0\) なら \(\mathtt{raw}\approx 0\) が \(q/4\) 未満、\(b=1\) なら \(\mathtt{raw}\approx\lfloor q/2\rfloor\) が \(q/2\) から \(q/4\) 以内に収まっている必要がある、という対称な条件になります）。したがって復号が成功する確率は、蓄積誤差 \(\mathbf{r}^\top\mathbf{e}\) が \(q/4\) を超えない確率そのものです。これを具体的に評価します。

ステップ1：蓄積誤差の分布。 \(\mathbf{r}\in\{0,1\}^m\) 、各誤差成分 \(e_i\) は（丸め処理を無視して連続近似すれば）独立に \(\mathcal{N}(0,\sigma^2)\) に従うとします。\(r\) の重み（1の個数）を \(k=\sum_i r_i\) とおくと、\(r\) を固定したときの条件付き分布は独立なガウス分布の線形結合なので厳密に

\[ \mathbf{r}^\top\mathbf{e} \mid \mathbf{r} \sim \mathcal{N}(0,\, k\sigma^2) \tag{5} \]

となります（CLTによる近似ではなく、ガウス分布の再生性から厳密に成り立ちます）。

ステップ2：厳密な最悪ケース評価（証明可能な上界）。 \(0 \le k \le m\) は常に成り立つので、標準的なガウス裾確率の評価 \(P(|Z|>t) \le 2\exp(-t^2/2v)\) （\(Z\sim\mathcal{N}(0,v)\) ）を \(t=q/4\) , \(v=k\sigma^2 \le m\sigma^2\) に適用すると、\(\mathbf{r}\) の値によらず

\[ P(\text{復号失敗}\mid \mathbf{r}) \le 2\exp\!\left(-\frac{q^2}{32\,k\,\sigma^2}\right) \le 2\exp\!\left(-\frac{q^2}{32\,m\,\sigma^2}\right) \tag{6} \]

が成り立ちます。復号失敗確率を \(2^{-\lambda}\) 以下に抑えたいなら、この式から

\[ q \;\gtrsim\; 4\sigma\sqrt{2m\lambda\ln 2} \;=\; \Theta\!\left(\sigma\sqrt{m\lambda}\right) \tag{7} \]

という設計制約が得られます。これが「法 \(q\) は誤差の標準偏差 \(\sigma\) と、合算するサンプル数 \(m\) の平方根の積程度で大きくしなければならない」という、LWEベース暗号設計で繰り返し現れるノイズ増大（noise growth）の基本則です。次数 \(n\) は直接この式には現れませんが、\(m\) は通常 \(n\) に比例して選ばれる（本記事のトイ実装では \(m=4n\) ）ため、間接的に \(n\) が大きいほど同じ安全マージンを保つのに必要な \(q\) も大きくなります。

ステップ3：実用上シャープな近似。 式(6)は \(k\le m\) という最悪ケースを使った証明可能な上界ですが、実際には \(\mathbf{r}\) は \(\{0,1\}^m\) から一様ランダムに選ばれるため、\(k\) は二項分布 \(\mathrm{Binomial}(m, 1/2)\) に従い期待値 \(m/2\) の周りに強く集中します（Chernoff限界）。そこで \(k\approx m/2\) を代入した、より実測に近い近似

\[ P(\text{復号失敗}) \approx 2\left(1-\Phi\!\left(\frac{q/4}{\sigma\sqrt{m/2}}\right)\right) \tag{8} \]

を使うと、下の数値実験2でこの予測と実測がどこまで一致するかを直接検証できます。

数値実験1：復号正当性の検証

\(n=32\) （格子次元）、\(q=3329\) （Kyberと同じ法）、\(m=128\) （公開鍵のLWEサンプル数）、\(\sigma=2.0\) （誤差の標準偏差）というトイパラメータで、シード 20260715 を固定してランダムなビットの暗号化・復号を2000回試行しました。

correct decryptions: 2000/2000 (100.00%)

2000回すべてで正しく復号できました。\(\sigma=2.0\) のとき式(8)が予測する失敗確率は \(10^{-100}\) を大きく下回るほど小さく（\(q/4 \approx 832\) に対し \(\sigma\sqrt{m/2}=2\times 8=16\) と、閾値までの距離が標準偏差の50倍以上ある）、2000回中0回の失敗は理論値と完全に整合します。

数値実験2：ノイズσと復号成功率のトレードオフ（理論と実測の比較）

耐量子暗号の設計における核心的なジレンマは、「誤差 \(\mathbf{e}\) は大きいほど安全（LWE問題が難しくなる）だが、大きすぎると正規の受信者すら復号に失敗する」という点です。式(8)の予測を検証するため、\(\sigma\) を2から300まで27点掃引し、各点で20回の鍵生成 × 400回の暗号化・復号試行（合計8000試行/点）を行い、実測の復号成功率を式(8)・式(6)の理論曲線と重ねました。

import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import norm

n, q, m = 32, 3329, 128
SEED = 20260715

def sample_error(size, sigma, q, rng):
    return np.round(rng.normal(0, sigma, size)).astype(np.int64) % q

def keygen(rng, sigma):
    s = rng.integers(0, q, size=n)
    A = rng.integers(0, q, size=(m, n))
    e = sample_error(m, sigma, q, rng)
    b = (A @ s + e) % q
    return (A, b), s

def encrypt(pub, bit, rng):
    A, b = pub
    r = rng.integers(0, 2, size=A.shape[0])
    u = (r @ A) % q
    v = (int(r @ b) + bit * (q // 2)) % q
    return u, v

def decrypt(sk, ct):
    u, v = ct
    raw = (v - int(u @ sk)) % q
    return 1 if abs(raw - q // 2) < q // 4 else 0

def theory_typical_success(sigma):  # 式(8)
    z = (q / 4) / (sigma * np.sqrt(m / 2))
    return 100 * (1 - 2 * norm.sf(z))

sigmas = [2, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112,
          120, 128, 140, 150, 165, 175, 190, 200, 225, 250, 275, 300]
n_keygens, trials_per_keygen = 20, 400
rng_master = np.random.default_rng(SEED)
for sigma in sigmas:
    correct, total = 0, 0
    for _ in range(n_keygens):
        rng = np.random.default_rng(rng_master.integers(0, 2**31 - 1))
        pub, sk = keygen(rng, sigma)
        for _ in range(trials_per_keygen):
            bit = int(rng.integers(0, 2))
            ct = encrypt(pub, bit, rng)
            correct += decrypt(sk, ct) == bit
            total += 1
    print(sigma, 100 * correct / total, theory_typical_success(sigma))

\(\sigma\)	実測成功率	式(8)の予測
32	99.99%	99.88%
64	91.50%	89.59%
96	69.65%	72.15%
128	61.83%	58.36%
150	53.50%	51.20%
200	50.89%	39.70%
300	50.02%	27.12%

Regevの復号成功率とノイズ標準偏差σの関係。実測点（黒丸）は式(8)の実用近似（青線）とσ≲100の範囲でよく一致し、式(6)の証明可能な最悪ケース上界（赤破線）はさらに保守的な値を与える

\(\sigma \lesssim 100\) の範囲では実測と式(8)の理論予測がよく一致しています。一方 \(\sigma \gtrsim 150\) では理論予測（式(8)、式(6)）が実測を下回り続ける（0%に向かって減少し続ける）のに対し、実測は50%（コイントスと同じ）で頭打ちになり、それ以上は下がりません。これは式(5)の「\(e_i\) は連続ガウス分布」という近似が破綻するためです：実装の sample_error は誤差を % q で \(\mathbb{Z}_q\) に還元しており、\(\sigma\) が \(q\) と同程度まで大きくなると誤差はもはや「小さなガウスノイズ」ではなく**\(\mathbb{Z}_q\) 上でほぼ一様**になります。このとき raw も \(\mathbb{Z}_q\) 上でほぼ一様分布し、判定区間 \((q/4, 3q/4)\) の幅がちょうど \(q\) の半分であることから、真のbitに関係なく1が返る確率はちょうど1/2に収束します。理論式(8)はこの「モジュラー折り返し」を考慮していないため、大きな \(\sigma\) では実測より悲観的な（低い）成功率を予測してしまう——これは単純化されたガウス近似がどこで破綻するかを実測で確認できた、という意味で有益な失敗例です。実際のKyberでは、このトレードオフを慎重にチューニングし、十分な安全性を保ちながら復号失敗確率を \(2^{-140}\) 程度まで抑える設計になっています（本記事のトイ実装よりはるかに洗練された誤差分布・パラメータ選択を使用）。

エッジケース(a)：しきい値を超えると実際に復号が失敗する

理論と図から、\(\sigma\) を安全域を超えて大きくすると復号が実際に間違ったビットを返すことを、1つの固定した鍵で確認します。同一シード 20260715 から、まず鍵を生成し、その後1000回暗号化・復号を試行します（真のビット列は鍵生成後の乱数状態から生成されるため、以下の「危険域」「安全域」の2つの実行で全く同じビット列が暗号化されます）。

def demo(sigma, n_show, n_total, seed):
    rng = np.random.default_rng(seed)
    pub, sk = keygen(rng, sigma)
    mismatches = 0
    for t in range(n_total):
        bit = int(rng.integers(0, 2))
        ct = encrypt(pub, bit, rng)
        u, v = ct
        raw = (v - int(u @ sk)) % q
        dec = 1 if abs(raw - q // 2) < q // 4 else 0
        if t < n_show:
            print(t, bit, dec, raw, "OK" if dec == bit else "FAIL")
        mismatches += dec != bit
    print(f"correct: {n_total - mismatches}/{n_total} ({100*(n_total-mismatches)/n_total:.2f}%)")

demo(sigma=150, n_show=20, n_total=1000, seed=20260715)  # 危険域
demo(sigma=2,   n_show=20, n_total=1000, seed=20260715)  # 安全域（同じシード）

危険域（\(\sigma=150\) 、式(8)の予測成功率 51.20%）の実行結果の先頭20件：

trial true_bit decrypted_bit    raw  match
    0        1             1   1213     OK
    1        0             1   1071   FAIL
    2        0             1   1819   FAIL
    3        1             0    686   FAIL
    4        1             0    505   FAIL
    5        0             0    312     OK
    6        1             0   3128   FAIL
    7        1             0    649   FAIL
    8        1             0   2807   FAIL
    9        1             0   3068   FAIL
   10        0             0    667     OK
   11        1             0   3119   FAIL
   12        1             0   3107   FAIL
   13        0             1   1302   FAIL
   14        1             0   2626   FAIL
   15        0             0    614     OK
   16        0             0    635     OK
   17        1             0   3301   FAIL
   18        1             1   1752     OK
   19        0             0   3316     OK
... (1000 trials total)
correct decryptions: 308/1000 (30.80%)

σ=150では1000回中308回（30.80%）しか正しく復号できず、コイントス（50%）よりも悪い結果になりました。これは、この特定の鍵で生成された誤差ベクトル \(\mathbf{e}\) がたまたま偏り（バイアス）を持ち、\(\mathbb{E}_{\mathbf{r}}[\mathbf{r}^\top\mathbf{e}\mid\mathbf{e}] = \frac{1}{2}\sum_i e_i\) という鍵固有の系統的シフトが閾値判定を間違った方向に押しやったためです（式(8)は多数の鍵で平均した振る舞いを予測するものであり、特定の1つの鍵の挙動を保証するものではないことを示す実例です）。

同じシードで \(\sigma=2\) （安全域）に戻すと：

correct decryptions: 1000/1000 (100.00%)

同じ乱数シード・同じ平文ビット列に対して、σだけを150から2に下げると1000回中1000回すべて正しく復号できました。 ノイズを安全域に保つことの重要性が、具体的な数値で確認できます。

なお、数値実験2の表で「100.00%に近い」とされていた \(\sigma=32\) についても、1000回試行すると4回（99.60%）失敗が観測されました。300回程度の試行では見えなかった稀な失敗事象が、試行回数を増やすと顕在化する——復号の正当性は「保証」ではなく「高確率」の主張であることが、この境界事例からも分かります。

数値実験3：誤差なしなら秘密鍵は一瞬で復元できる

LWEの困難性が「誤差」そのものに由来することを直接確認するため、誤差なしの場合（\(\mathbf{b} = A\mathbf{s}\) 、通常の線形連立方程式）に秘密鍵を復元できるかを試しました。

import sympy

A0 = np.array(rng.integers(1, q, size=(n, n)))
s_true = rng.integers(0, q, size=n)
b0 = (A0 @ s_true) % q  # 誤差項なし

A0_inv_mod = sympy.Matrix(A0.tolist()).inv_mod(q)  # 法qでの逆行列
s_recovered = np.array([int(x) for x in (A0_inv_mod * sympy.Matrix(b0.tolist())) % q]).flatten()

max |recovered - true| (should be 0): 0
s fully recovered: True

法 \(q\) での行列の逆行列を計算するだけで、秘密鍵が完全に、一瞬で復元されました。 これは、誤差のない連立方程式は単純な線形代数（\(O(n^3)\) ）で解けてしまうことを示しています。LWE問題が困難であるためには誤差が本質的に必要であり、この誤差が「格子上の最短ベクトル問題」という、量子コンピュータでも効率的な解法が知られていない問題への還元を可能にしています。

エッジケース(b)：パラメータサイズと安全性・効率のトレードオフ

本記事のRegev暗号では、暗号文は \((\mathbf{u}, v) \in \mathbb{Z}_q^n \times \mathbb{Z}_q\) 、公開鍵は \((A, \mathbf{b}) \in \mathbb{Z}_q^{m\times n} \times \mathbb{Z}_q^m\) です。\(\lceil\log_2 q\rceil = 12\) ビット（\(q=3329\) ）としてビット数を数えると、

\[ \begin{aligned} \text{暗号文サイズ} &= (n+1)\lceil\log_2 q\rceil \text{ bits} \\ \text{公開鍵サイズ} &= m(n+1)\lceil\log_2 q\rceil \text{ bits} \end{aligned} \tag{9} \]

となります（\(m=4n\) という本記事のトイ実装の比率を保ったまま \(n\) を変化させたときの値）。

ns = np.array([32, 64, 128, 256, 512, 768, 1024])
ms = 4 * ns
bits_q = 12  # ceil(log2(3329))
ciphertext_bytes = (ns + 1) * bits_q / 8
pubkey_bytes = ms * (ns + 1) * bits_q / 8

\(n\)	\(m\)	暗号文サイズ	公開鍵サイズ
32	128	49.5 B	6.2 KB
128	512	193.5 B	96.8 KB
512	2048	769.5 B	1.50 MB
1024	4096	1537.5 B	6.01 MB

暗号文サイズと公開鍵サイズのn依存性。本記事のトイ実装（青・緑線）は公開鍵がO(n^2)で爆発する一方、実際のML-KEM（赤マーカー）は同じnで暗号文サイズは近い値ながら公開鍵サイズは数KB台に収まっている

暗号文サイズは \(n\) に対してほぼ線形に増えるだけですが（\(n=1024\) でも1.5KB程度）、公開鍵サイズは \(m\propto n\) を仮定すると \(n\) について2次（\(O(n^2)\) ）で増大し、\(n=1024\) では約6MBに達します。これが「CRYSTALS-Kyberとの関係」の節で述べた「公開鍵サイズが \(O(nm)\) と大きくなる」という主張の具体的な数値です。図には実際のML-KEM（Kyber）の公開値も重ねています。ML-KEM-512/768/1024（\(n=k\times 256\) 、\(k=2,3,4\) ）の暗号文サイズはそれぞれ768/1088/1568バイトで、興味深いことに同じ \(n\) における本記事のトイ暗号文サイズ（769.5/1153.5/1537.5バイト）とほぼ一致します（\(q\) を同じ値に揃えたため）。しかし公開鍵サイズはML-KEMがそれぞれ800/1184/1568バイトと、本記事のトイ実装（1.50MB〜6.01MB）よりも3〜4桁小さく抑えられています。この差こそが、行列 \(A\) 全体を送る代わりに多項式環の構造を使って \(A\) を短いシードから再生成する（Module-LWEの中核アイデアの1つ）ことの効果です。

安全性コストについても、informalには次のことが知られています。 LWE/Module-LWEに対する最も実践的な攻撃（格子基底簡約：BKZアルゴリズムなど）のコストを見積もる標準的な手法（core-SVPモデル）では、攻撃コストは次数に対しておおよそ指数関数的に増加すると評価されます。実際にNISTへ提出されたKyberの仕様書は、ML-KEM-512（\(n=512\) ）は古典計算で約118ビット・量子computingで約107ビットの困難性、ML-KEM-768（\(n=768\) ）は約182/165ビット、ML-KEM-1024（\(n=1024\) ）は約256/232ビットの困難性を持つと公表しています。これはあくまで公表されている数値の引用であり、本記事のトイ実装（\(n=32\) ）に対して同様の攻撃コストを実際に見積もったものではないことに注意してください。トイパラメータの \(n=32\) 、\(q=3329\) は教育目的の単純化であり、暗号学的な安全性を主張するものではありません。それでも「\(n\) を大きくすると公開鍵/暗号文サイズという効率コストと、格子問題の困難性という安全性の利得がトレードオフの関係にある」という定性的な構造は、この図とKyberの公表値の両方から確認できます。

エッジケース(c)：なぜLWEはShorのアルゴリズムに耐えると考えられているのか

RSAの素因数分解もDiffie-Hellman/ECCの離散対数問題も、実は同じ数学的構造に帰着します。**アーベル群上の隠れ部分群問題（Hidden Subgroup Problem, HSP）**です。Shorのアルゴリズムの核心は、量子フーリエ変換（QFT）を使ってアーベル群上のHSPを多項式時間で解くことにあります。素因数分解は \((\mathbb{Z}/N\mathbb{Z})^*\) 上の位数発見問題に、離散対数問題は \(\mathbb{Z}\times\mathbb{Z}\) 上のHSPに、それぞれ帰着することが知られており、どちらも「アーベル群+QFT」という同じ枠組みで攻略されます。

一方、LWE問題（あるいはその背後にある格子上の最短ベクトル問題・有界距離復号問題）は、アーベル群上のHSPへの効率的な帰着が知られていません。格子問題に対応する隠れ部分群問題は非可換な二面体群（dihedral group）上のHSP（あるいは「隠れ格子問題」）に近い構造を持つとされていますが、二面体群は非可換であり、QFTによる標準的な攻略法が機能しません。実際、二面体群上のHSPに対して知られている最良の量子アルゴリズム（Kuperberg, 2005）は劣指数時間 \(2^{O(\sqrt{n})}\) であり、Shorのアルゴリズムが達成する多項式時間には遠く及びません。Regev (2004) も、格子問題と二面体coset問題の間に関係があることを示しつつ、それが効率的な量子解法には直結しないことを論じています。

ここで誠実に述べておくべき点は、「LWEが量子計算機に耐性を持つことの証明」は存在しないということです。 分かっているのは、（1）過去20年以上にわたり格子問題に対する多項式時間の量子アルゴリズムが発見されていないこと、（2）格子問題がRSA/離散対数のように「アーベル群+QFT」という既知の攻略パターンに自然には当てはまらないこと、の2点です。これは「破る方法が知られていない」という状況証拠であり、「原理的に破れない」という数学的証明ではありません。実際、格子問題に対する（古典・量子を問わない）攻撃アルゴリズムの改善は現在も活発な研究分野であり（後述の「最近の研究動向」を参照）、この状況証拠は将来変化しうるものです。

CRYSTALS-Kyberとの関係

本記事のRegev暗号は教育目的の単純化版で、1ビットずつしか暗号化できず、公開鍵サイズも前節で確認した通り \(O(nm)\) と大きくなります。実際のCRYSTALS-Kyberは、**多項式環上のLWE（Module-LWE）**を使うことで、この問題を解決しています。整数ベクトルの代わりに多項式環 \(\mathbb{Z}_q[x]/(x^n+1)\) の要素を使い、行列演算の代わりに多項式乗算（NTT: Number Theoretic Transformによる高速化と相性が良い）を使うことで、鍵サイズと計算量を大幅に削減しつつ、複数ビットを一度に暗号化できるようにしています。本記事のトイ実装で確認した「誤差が困難性の源泉」「誤差サイズと正当性のトレードオフ」「公開鍵サイズと安全性のトレードオフ」という核心的な性質は、Module-LWEでも変わらず成り立ちます。

最近の研究動向（2024〜2025）

NISTはFIPS 203（ML-KEM）・FIPS 204（ML-DSA）に加え、2024年8月にFIPS 205（SLH-DSA、SPHINCS+ベースのハッシュ関数のみに依存する署名方式）も確定しました。 格子問題ではなくハッシュ関数の困難性だけに依拠する保守的な代替署名方式として位置づけられています。
NISTは2025年3月、符号ベース暗号のHQC（Hamming Quasi-Cyclic）をML-KEMのバックアップとなる5番目のPQCアルゴリズムに選定しました。 格子問題とは全く異なる数学的構造（誤り訂正符号）に基づいており、「ML-KEMの安全性の前提が万一崩れた場合に備えて、異なる数学的仮定に基づく代替を用意しておく」という多様化戦略の一環です（Draft標準は2026年頃、最終確定は2027年を予定）。
Wenger, Saxena, Malhou, Thieu, Lauter (2025), “Benchmarking Attacks on Learning with Errors”, IEEE Symposium on Security and Privacy (S&P) 2025 は、uSVP・SALSA・Cool & Cruel・Dual Hybrid Meet-in-the-Middleという主要な攻撃手法をKyber型の疎な秘密鍵に対して統一的にベンチマークした研究です。伝統的なuSVP攻撃がこの設定では有効に機能しない一方、機械学習を使った攻撃が特定の設定で28〜36時間程度でbinomial secretを回収できることを示しており、LWEへの現実的な攻撃コストの評価が今も発展途上であることを裏付けています。
Stevens, Wenger, Li, Nolte, Saxena, Charton, Lauter (2024), “Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors”, arXiv:2402.01082 は、Transformerベースの機械学習でLWEの疎な秘密鍵を回収する攻撃を改良し、次元 \(n=1024\) という実用的な暗号パラメータ規模で疎な二値秘密鍵の回収に初めて成功したと報告しています。前節の「攻撃コストは公表値でしか分からない」という記述とあわせて、機械学習ベースの攻撃がLWEの実践的な安全性マージンにどう影響するかは、現在進行形で調査されている問題です。

暗号系ロードマップ：古典暗号・対称鍵・RSA・Diffie-Hellman・楕円曲線・ハッシュ・署名・TLSのPython実装ハブ - 本記事はこのハブの「将来追加予定」プレースホルダの最後の1つを実装したものです。
RSA暗号の理論・鍵生成・暗号化・復号をPython実装 - Shorのアルゴリズムで破られる素因数分解ベースの暗号方式です。
Diffie-Hellman鍵交換の理論と実装 - Shorのアルゴリズムで破られる離散対数問題ベースの鍵交換です。
楕円曲線暗号（ECC）の数学と Python 実装 - 同じくShorのアルゴリズムの標的である楕円曲線離散対数問題（ECDLP）を解説しています。
TLS 1.3ハンドシェイク解剖 - 現行のECDHEベースのハンドシェイクが、将来的にKyberベースの鍵交換へ移行しうる文脈を提供します。
AES対称鍵暗号の理論とPython実装 - 対称鍵暗号はGroverのアルゴリズムによる平方根加速しか受けず、耐量子暗号移行後もAES-256がそのまま使われ続ける理由を解説しています。

参考文献

Regev, O. (2005). On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC).
Regev, O. (2004). Quantum computation and lattice problems. SIAM Journal on Computing, 33(3), 738-760.
Kuperberg, G. (2005). A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM Journal on Computing, 35(1), 170-188.
Peikert, C. (2016). A decade of lattice cryptography. Foundations and Trends in Theoretical Computer Science, 10(4), 283-424.
Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484-1509.
National Institute of Standards and Technology (2024). Module-Lattice-Based Key-Encapsulation Mechanism Standard. FIPS 203 (CRYSTALS-Kyber).
National Institute of Standards and Technology (2024). Module-Lattice-Based Digital Signature Standard. FIPS 204 (CRYSTALS-Dilithium).
National Institute of Standards and Technology (2024). Stateless Hash-Based Digital Signature Standard. FIPS 205 (SLH-DSA).
National Institute of Standards and Technology (2025). NIST Selects HQC as Fifth Algorithm for Post-Quantum Encryption. NIST News, March 11, 2025.
Wenger, E., Saxena, E., Malhou, M., Thieu, E., & Lauter, K. (2025). Benchmarking attacks on learning with errors. IEEE Symposium on Security and Privacy (S&P) 2025.
Stevens, S., Wenger, E., Li, C., Nolte, N., Saxena, E., Charton, F., & Lauter, K. (2024). Salsa Fresca: Angular embeddings and pre-training for ML attacks on Learning With Errors. arXiv:2402.01082.