耐量子暗号入門：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と同じ値を採用）

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

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

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

correct decryptions: 2000/2000 (100.00%)

2000回すべてで正しく復号できました。誤差が小さければ、正規の受信者（秘密鍵 \(\mathbf{s}\) を知っている）は確実に復号できることが確認できます。

数値実験2：ノイズσと復号精度のトレードオフ

耐量子暗号の設計における核心的なジレンマは、「誤差 \(\mathbf{e}\) は大きいほど安全（LWE問題が難しくなる）だが、大きすぎると正規の受信者すら復号に失敗する」という点です。\(\sigma\) を変化させ、5回の鍵生成×各300回の暗号化・復号試行で平均復号精度を測定しました。

\(\sigma\) （誤差の標準偏差）	平均復号精度
2	100.00%
32	100.00%
64	89.67%
96	79.67%
128	64.60%
200	52.00%（ほぼ当て推量）

\(\sigma\) が大きくなるにつれて復号精度が単調に低下し、\(\sigma=200\) ではほぼ50%（ランダムに1ビット当てるのと同程度）まで劣化しました。これは「誤差を大きくして安全性を上げると、正当性（correctness）が崩れる」というLWEベース暗号設計の本質的なトレードオフを定量的に示しています。実際のKyberでは、このトレードオフを慎重にチューニングし、十分な安全性を保ちながら復号失敗確率を \(2^{-140}\) 程度まで抑える設計になっています（本記事のトイ実装よりはるかに洗練された誤差分布・パラメータ選択を使用）。

数値実験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問題が困難であるためには誤差が本質的に必要であり、この誤差が「格子上の最短ベクトル問題」という、量子コンピュータでも効率的な解法が知られていない問題への還元を可能にしています。

CRYSTALS-Kyberとの関係

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

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

参考文献

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).
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).