格子暗号とLWE／RLWE

格子とは何か：基底と難しい問題

ポスト量子暗号の主力である格子暗号は、名前のとおり格子（lattice）という幾何学的対象の上に立っています。格子とは、n 個の一次独立なベクトル（基底）b1,...,bn の整数結合で表せる点すべての集合です。

L = { z1·b1 + z2·b2 + ... + zn·bn : zi は整数 }

同じ格子は無数の基底で表せます。ここが暗号の肝で、**互いに直交に近く短い「良い基底」**を持てば格子上の計算は易しく、**歪んで長い「悪い基底」**しか知らないと同じ問題が途端に難しくなります。公開鍵として悪い基底を、秘密鍵として良い基底を配る――これが格子暗号の素朴な発想です。

難しさの中身は2つの問題に集約されます。

• 最短ベクトル問題（SVP）：格子の非ゼロで最も短いベクトルを求める。
• 最近ベクトル問題（CVP）：格子外の任意の点 t に対し、最も近い格子点を求める。

LWE：誤りを混ぜて方程式を壊す

SVP／CVPを暗号でそのまま使うのは扱いづらいため、実際の設計は LWE（Learning With Errors、誤り付き学習）という形に落とし込みます。秘密ベクトル s を隠したい主体が、公開の乱数行列 A と小さな誤差ベクトル e を使って

b = A · s + e   (mod q)

を大量に公開します。攻撃者に見えるのは (A, b) の対だけ。ここから s を復元するのがLWE問題です。

誤差 e が無ければ b = A·s は単なる連立一次方程式で、ガウスの消去法が一瞬で s を吐き出します。要はわざとノイズを混ぜることで消去法が破綻します。消去の過程で誤差が掛け算・足し算のたびに増幅され、最終的に真の解を覆い隠すからです。この「ノイズ付き方程式を解く」ことが、幾何学的には格子上の**有界距離復号（BDD、誤差が格子の最小距離より十分小さいという制約付きのCVP）**を解くことと等価になります。行列 A が張る格子に対し、b は格子点 A·s から誤差 e だけずれた点であり、最も近い格子点を当てれば s が分かる――つまりLWEはCVPの特殊ケースの言い換えです。

誤差の大きさとモジュラス q の比 q/‖e‖ の取り方が設計の要です。誤差が小さすぎると格子構造が透けて解読され、大きすぎると正規の復号が誤差に埋もれて失敗します。両者の隙間を突いて、復号は通るが解読は通らないパラメータを選びます。

Ring-LWE と Module-LWE：鍵を小さくする

素のLWEは安全ですが、行列 A が n × n 規模になり、鍵と暗号文が巨大になります（数百キロバイト級）。実用化を阻んだこのサイズ問題を解いたのが、代数構造の導入です。

Ring-LWE（RLWE）は、スカラーの代わりに多項式環 Zq[x]/(x^n + 1) の要素を成分に使います。この環では、乱数「行列」の役割をたった1本の多項式 a が担い、その巡回的な構造から実質 n × n 相当の情報が n 個の係数だけで表せます。結果として鍵サイズは1桁以上縮みます。さらに n を2冪に取り、モジュラス q を q ≡ 1 (mod 2n) を満たす素数に選ぶと、多項式の積を**数論変換（NTT、数論版の高速フーリエ変換）**で O(n log n) に高速化でき、性能でも決定的に有利になります。

ただしRLWEは「1本の多項式で全部を表す」強い構造ゆえ、その代数構造を突く未知の攻撃への不安が残ります。そこで折衷案が **Module-LWE（MLWE）**です。

MLWEは多項式を成分とする小さな行列（Kyberなら 2×2〜4×4 程度）を使います。行列のランクを増減させるだけで安全性を細かく調整でき、単一の環に全面依存しないため構造攻撃への余裕も確保できます。この設計判断が、NISTが最終的にModule系を選んだ理由の一つです。

Kyber と Dilithium の設計思想

NISTが標準化した2つの主力アルゴリズムは、いずれもこのModule-LWEを土台に、目的の異なる暗号プリミティブを構築しています。

**Kyber（ML-KEM、FIPS 203）**は共通鍵を届ける KEM（鍵カプセル化）です。中核は素朴なLWE型の公開鍵暗号（PKE）ですが、これは受動的な攻撃にしか安全でない（IND-CPA）ため、そのままでは不正な暗号文を送りつける選択暗号文攻撃に弱い。そこで Fujisaki-Okamoto（FO）変換を被せます。FO変換は、復号後に得た平文から暗号文を作り直し、元の暗号文と一致するか検証する仕組みで、少しでも細工された暗号文を確実に弾きます。これにより IND-CCA2（能動的攻撃に対する強い安全性）を達成します。

**Dilithium（ML-DSA、FIPS 204）**は署名方式で、Module-LWEに加え、短い解を探す困難さである Module-SISにも依拠します。方式は Fiat-Shamir with Aborts。署名は「秘密鍵 s を知っている」というゼロ知識証明をハッシュで非対話化したもので、z = y + c·s（c はメッセージ由来のチャレンジ、y はランダムなマスク）という形をとります。

Kyberと Dilithiumが同じ環 Zq[x]/(x^n + 1)（ともに n = 256）とNTTを共有するのは偶然ではなく、同一ハードウェア／ソフトウェア資産を使い回せるようにした意図的な設計です。KEMと署名の両方を1組の演算基盤で賄えるため、組込みからサーバーまで実装コストを抑えられます。

量子耐性の根拠

最後に、なぜこれが量子計算機でも破れないとされるのかを整理します。RSAやECC／DHを崩壊させるShorのアルゴリズムは、素因数分解と離散対数を周期発見に帰着させ、量子フーリエ変換で周期を一気に求めるものでした。ところが格子問題には利用できる周期構造が無い。SVP／CVPの困難さは代数的な周期ではなく高次元の幾何に根ざすため、Shorの手口がそもそも適用できません。

では量子計算機は格子に無力かというと、そうではありません。既知の最良の攻撃は格子基底簡約（BKZ など）を核とする手法で、量子版でもGroverによる探索の平方根加速が乗る程度です。つまり量子であっても計算量は依然として指数関数的にとどまり、鍵長を適切に取れば安全余裕が保たれます。実際のパラメータは、こうした最良攻撃のコストをビット安全性として見積もり（Kyber-768で古典・量子とも十分な余裕を確保）、そこに実装上の誤り率や将来の攻撃改良への保険を上乗せして決めています。

まとめ

格子暗号の安全性は、高次元格子のSVP／CVPが古典・量子いずれでも指数時間しか知られていないことに立脚します。LWEは連立方程式に小さな誤差を混ぜてCVPに帰着させる問題で、最悪ケース／平均ケース帰着という強い理論保証を持ちます。Ring-LWE／Module-LWEは多項式環で鍵を縮め、Module構造が効率と保守性の折衷を実現しました。

これを土台に、KyberはFO変換でIND-CCA2なKEMを、Dilithiumは棄却サンプリングを核とする署名を構成し、同じ環とNTTを共有します。量子耐性の根拠はShorの周期発見が幾何的な格子問題に効かないことにあり、既知の量子攻撃でも指数時間が残る点です。ただし絶対証明ではないため、暗号の基礎を押さえたうえで、実務ではハイブリッド化と暗号アジリティで備えるのが定石です。