第7章ハッシュ関数・格子暗号・耐量子暗号

この章の目標

• ハッシュ関数の原像・第 2 原像・衝突に対する困難性の関係を説明し、誕生日攻撃の成功確率の評価を証明できる
• 長さ拡張攻撃を理解し、HMAC が $H(k \mathbin{\Vert} m)$ と違って安全に使える理由を説明できる
• 格子の行列式が基底によらないこと、2 次元のガウス簡約が最短ベクトルを与えることを証明し、LLL による格子攻撃の仕組みを説明できる
• レゲフの LWE 暗号方式で、誤差の総和が小さければ正しく復号できることを証明できる
• 量子計算機が公開鍵暗号・共通鍵暗号・ハッシュ関数に与える影響の違いと、耐量子暗号への移行の考え方を説明できる

前提：第2章、第3章、02-linear-algebra 第4章（行列式）、02-linear-algebra 第7章（内積・グラム–シュミットの直交化）。7.5 節ではミンコフスキーの凸体定理（15-algebraic-number-theory 第3章で証明されている）の主張だけを使う。7.8 節では第4章の ECDSA に触れる。

本章では、暗号のあらゆる場所で使われるハッシュ関数、暗号を破る道具であると同時に新しい暗号の土台でもある格子、第2〜4章の公開鍵暗号をすべて多項式時間で破る量子計算機を扱い、NIST が 2024 年に規格化した耐量子暗号と移行の考え方を整理する。

7.1 ハッシュ関数の安全性

ダウンロードしたファイルの SHA-256 のハッシュ値を配布元の掲載値と比べて改ざんを検出できるのは、同じハッシュ値をもつ別のファイルを作るのが難しいからである。

定義 7.1（ハッシュ関数とその安全性, 非形式的）任意の長さ（実際には $2^{64}$ ビット未満などの上限がある）のビット列を $n$ ビットのビット列に写す、効率よく計算できる関数 $H$ をハッシュ関数 (hash function) といい、$H(x)$ を $x$ のハッシュ値という。

1. 原像困難性 (preimage resistance)：ランダムに選んだ $x$（たとえば $2n$ ビットの列から一様に）のハッシュ値 $y = H(x)$ だけから、$H(x') = y$ となる $x'$ を求めるのが難しい（$x' = x$ でなくてよい）。
2. 第 2 原像困難性 (second-preimage resistance)：ランダムに選んだ $x$ が与えられたとき、$x' \neq x$ かつ $H(x') = H(x)$ となる $x'$ を求めるのが難しい。
3. 衝突困難性 (collision resistance)：$x \neq x'$ かつ $H(x) = H(x')$ となる組 $(x, x')$（衝突, collision）を求めるのが難しい。

入力は出力よりずっと多いので衝突は無数にあり、問題はそれを見つけられるかである（固定した関数には衝突を出力するだけのアルゴリズムが誰も知らなくても存在するので、厳密な定義には鍵つきの関数族を使う。実際のハッシュ関数の安全性は最良の攻撃の計算量で測る）。

命題 7.2（衝突困難なら第 2 原像困難）第 2 原像を確率 $\varepsilon$ で求めるアルゴリズム $\mathcal{A}$ があれば、それを 1 回使って衝突を確率 $\varepsilon$ で求められる。

証明. 定義 7.1 の 2 のとおりに $x$ を選んで $\mathcal{A}$ に与え、出力 $x'$ と組にする。$\mathcal{A}$ が成功すれば $x' \neq x$ かつ $H(x') = H(x)$ である。$\square$

衝突困難性から原像困難性を導くには、関数が十分に圧縮することが要る。

命題 7.3（圧縮する関数では、原像が求まれば衝突が求まる）$X, Y$ を有限集合、$H\colon X \to Y$ とし、一様に選んだ $x \in X$ の像 $y = H(x)$ から確率 $\varepsilon$ で $y$ の原像を出力するアルゴリズム $\mathcal{A}$（内部の乱数は $x$ と独立）があるとする。$x$ を一様に選んで $x' = \mathcal{A}(H(x))$ とし、$x' \neq x$ かつ $H(x') = H(x)$ なら $(x, x')$ を出力すれば、確率 $\varepsilon - \lvert Y \rvert/\lvert X \rvert$ 以上で衝突が得られる。

証明. $y \in H(X)$ について $c_y = \lvert H^{-1}(y) \rvert$、$\varepsilon_y = P(\mathcal{A}(y) \in H^{-1}(y))$ とする。$H(x) = y$ という条件のもとで $x$ は $H^{-1}(y)$ 上に一様に分布して $\mathcal{A}(y)$ と独立なので、$\mathcal{A}(y) \in H^{-1}(y)$ のとき $\mathcal{A}(y) \neq x$ となる条件付き確率は $1 - 1/c_y$ である。$P(H(x) = y) = c_y/\lvert X \rvert$ だから、成功確率は

である（第 1 項は $\mathcal{A}$ の成功確率 $\varepsilon$ そのもので、$\varepsilon_y \leq 1$, $\lvert H(X) \rvert \leq \lvert Y \rvert$ を使った）。$\square$

512 ビットを 256 ビットに縮める関数なら $\lvert Y \rvert/\lvert X \rvert = 2^{-256}$ で、衝突困難で十分に圧縮する関数は原像困難である。

例 7.4 圧縮しなければこの議論は成り立たない。$\lbrace 0, 1 \rbrace^n$ 上の恒等写像は衝突をもたないので衝突困難だが、$y$ の原像は $y$ 自身で、原像困難ではない。

出力が $n$ ビットなら、値がランダムにふるまうとして、総当たりの手間は原像と第 2 原像が約 $2^n$ 回、衝突は次節の誕生日攻撃で約 $2^{n/2}$ 回である。

7.2 誕生日攻撃

衝突を探す最も単純な方法は、多くの入力のハッシュ値を計算して一致を探すことである。その成功確率は次の定理で評価できる。

定理 7.5（誕生日の限界, birthday bound）$N, k$ を正の整数とし、$Y_1, \dots, Y_k$ を、$N$ 個の元からなる集合の上の一様分布に独立に従う確率変数とする。$Y_i = Y_j$ となる $i < j$ が存在する確率を $p(k, N)$ とすると

$$1 - e^{-k(k-1)/(2N)} \leq p(k, N) \leq \frac{k(k-1)}{2N}$$

が成り立つ。

証明. 上界：各組 $i < j$ について $P(Y_i = Y_j) = \sum_y P(Y_i = y)P(Y_j = y) = 1/N$ で、組は $k(k-1)/2$ 個あり、和事象の確率は個々の確率の和以下である。下界：$k > N$ なら鳩の巣原理により $p(k, N) = 1$ なので、$k \leq N$ とする。値の並び $(Y_1, \dots, Y_k)$ は $N^k$ 通りでどれも同じ確率で現れ、値がすべて異なる並びは $N(N - 1)\cdots(N - k + 1)$ 通りなので

である。ここで各因子が $0$ 以上であることと、すべての実数 $t$ について $1 - t \leq e^{-t}$ であること（$e^{-t}$ は下に凸で、$t = 0$ での接線が $1 - t$）を使った。$\square$

下界は攻撃の成功確率を保証し、上界からは $k$ が $\sqrt{N}$ よりずっと小さければ衝突はまず起きないことがわかる。

系 7.6 $k(k - 1) \geq 2N\log 2$ ならば $p(k, N) \geq 1/2$ である。特に $k \geq 1 + 1.18\sqrt{N}$ ならば $p(k, N) \geq 1/2$。

証明. 定理 7.5 の下界が $1 - e^{-\log 2} = 1/2$ 以上になる。$k \geq 1 + 1.18\sqrt{N}$ なら $k(k - 1) \geq (k - 1)^2 \geq 1.18^2N \geq 2N\log 2$（$2\log 2 = 1.386\cdots$）である。$\square$

例 7.7（誕生日のパラドックス）$N = 365$, $k = 23$ では $k(k - 1) = 506 \geq 730\log 2 = 505.99\cdots$ なので、誕生日が一様で独立なら、23 人の中に誕生日が同じ 2 人がいる確率は $1/2$ 以上である。実際の値は $p(23, 365) = 0.5073$ である。

値が一様でない同じ分布に独立に従う場合も、衝突の確率は $p(k, N)$ 以上である（概略：値がすべて異なる確率は、各値の確率の $k$ 次基本対称式 $e_k$ の $k!$ 倍で、二つの確率をその平均で置き換えても $e_k$ は減らないので、一様分布で最大になる）。よって $H\colon D \to Y$（$\lvert Y \rvert = N$）が任意の関数でも、$x_1, \dots, x_k \in D$ を一様に独立に選べば、$x_i \neq x_j$ かつ $H(x_i) = H(x_j)$ となる組がある確率は $1 - e^{-k(k-1)/(2N)} - k(k-1)/(2\lvert D \rvert)$ 以上である（最後の項は入力どうしが一致する確率の上界）。この誕生日攻撃 (birthday attack) により、出力が $n$ ビットなら（$D$ を十分大きくとって）約 $1.18 \cdot 2^{n/2}$ 回の計算で確率ほぼ $1/2$ 以上で衝突が見つかるので、衝突困難性は高々 $n/2$ ビットの安全性しかもたず、128 ビットの安全性には 256 ビットの出力が要る（第3章の $\rho$ 法のように記憶をほとんど使わない方法もある）。

7.3 メルクル–ダムガード構成と実際のハッシュ関数

任意の長さの入力を扱うハッシュ関数は、固定長の入力を縮める圧縮関数を繰り返して作ることが多い。

定義 7.8（メルクル–ダムガード構成, Merkle–Damgård construction）$f\colon \lbrace 0, 1 \rbrace^n \times \lbrace 0, 1 \rbrace^b \to \lbrace 0, 1 \rbrace^n$ を圧縮関数、$\mathrm{IV} \in \lbrace 0, 1 \rbrace^n$ を固定の初期値とする。長さ $\ell < 2^{64}$ ビットのメッセージ $M$ の後ろに、ビット $1$、いくつかの $0$、$\ell$ の 64 ビットの 2 進表示を付け加えて長さを $b$ の倍数にした最短の列を $\overline{M} = M \mathbin{\Vert} \operatorname{pad}(\ell)$ とする（$\operatorname{pad}(\ell)$ は $\ell$ だけで決まる）。$\overline{M}$ を $b$ ビットずつのブロック $m_1, \dots, m_L$ に分け、$h_0 = \mathrm{IV}$, $h_i = f(h_{i-1}, m_i)$ として $H(M) = h_L$ とする（$h_i$ を連鎖値という）。

定理 7.9（メルクル, ダムガード, 1989 年）$H$ の衝突から $f$ の衝突が効率よく求まる。したがって $f$ が衝突困難なら $H$ も衝突困難である。

証明. $H(M) = H(M')$, $M \neq M'$ とし、$M'$ の側の値に $'$ をつける。長さが異なれば最後のブロックの末尾 64 ビットが異なるので、$f(h_{L-1}, m_L) = f(h'_{L'-1}, m'_{L'})$ が衝突である。長さが等しければ $L = L'$ で、$(h_{i-1}, m_i) \neq (h'_{i-1}, m'_i)$ となる最大の $i$ を $i_0$ とする（$m_i \neq m_i'$ となる $i$ があるので存在する）。$i_0 = L$ なら $H(M) = H(M')$ から、$i_0 < L$ なら $i_0$ の最大性から $h_{i_0} = h'_{i_0}$ なので、$f(h_{i_0-1}, m_{i_0}) = f(h'_{i_0-1}, m'_{i_0})$ が衝突である。$\square$

命題 7.10（長さ拡張, length extension）メルクル–ダムガード構成の $H$ について、$H(M)$ と $M$ の長さ $\ell$ だけを知っていれば（$M$ を知らなくても）、任意のビット列 $X$ に対して $H(M \mathbin{\Vert} \operatorname{pad}(\ell) \mathbin{\Vert} X)$ を計算できる。

証明. $M' = M \mathbin{\Vert} \operatorname{pad}(\ell) \mathbin{\Vert} X$ の長さ $\ell'$ は $\ell$ と $X$ から求まり、$\overline{M'} = \overline{M} \mathbin{\Vert} X \mathbin{\Vert} \operatorname{pad}(\ell')$ である。$\overline{M}$ の長さは $b$ の倍数なので、最初の $L$ ブロックまでの連鎖値は $h_L = H(M)$ で、残りのブロックを $h_L$ から順に $f$ で処理すれば $H(M')$ が得られる。$\square$

実際のハッシュ関数　米国の規格 FIPS 180-4 の SHA-2（SHA-256・SHA-512 など。数字は出力のビット数）はメルクル–ダムガード構成で（SHA-256 では $n = 256$, $b = 512$）、SHA-256 と SHA-512 は最後の連鎖値をそのまま出力するので長さ拡張ができる。FIPS 202（2015 年）の SHA-3 は Keccak に基づくスポンジ構成で、内部状態の一部を出力しないので長さ拡張は当てはまらない。

MD5（出力 128 ビット）と SHA-1（160 ビット）もメルクル–ダムガード構成だが、圧縮関数の構造を突く攻撃が誕生日攻撃よりずっと速い。2004 年 8 月に王小雲（ワン・シャオユン）らが MD5 の衝突の実例を発表し、2017 年 2 月には CWI（オランダ）と Google の研究者が、SHA-1 の値が等しい 2 つの異なる PDF ファイルを公表した（SHAttered。SHA-1 の計算約 900 京回（ほぼ $2^{63}$ 回）で、誕生日攻撃の約 $2^{80}$ 回よりはるかに少ない）。衝突が見つかった関数を、署名や証明書のように衝突困難性に依存する用途に使い続けてはいけない。

7.4 メッセージ認証符号と HMAC

ハッシュ値で改ざんを検出できるのは、正しいハッシュ値が別の安全な経路で届く場合だけである。秘密鍵 $k$ を共有する 2 者は、メッセージ認証符号 (message authentication code, MAC) のタグ $t = \operatorname{MAC}_k(m)$ を添えて送り、受信者は同じ計算をして一致を確かめる。安全性の定義は署名の EUF-CMA（第2章 2.10 節）と同じで、鍵を知らない攻撃者は、好きなメッセージのタグを教えてもらえても、新しいメッセージの正しいタグを作れないことである。

素朴な $\operatorname{MAC}_k(m) = H(k \mathbin{\Vert} m)$ は、$H$ がメルクル–ダムガード構成なら安全でない。タグ $t = H(k \mathbin{\Vert} m)$ を一つ見た攻撃者は、$k$ の長ささえわかれば、命題 7.10 により任意の $X$ について $m \mathbin{\Vert} \operatorname{pad}(\ell) \mathbin{\Vert} X$（$\ell$ は $k \mathbin{\Vert} m$ の長さ）の正しいタグを計算できる。

定義 7.11（HMAC）$H$ をブロック長 $b$ ビットのハッシュ関数とし、鍵 $k$ の後ろに $0$ を付けて $b$ ビットにしたものを $k'$ とする（$k$ が $b$ ビットより長ければ先に $H(k)$ に置き換える）。

$$\operatorname{HMAC}_k(m) = H\bigl((k' \oplus \mathrm{opad}) \mathbin{\Vert} H((k' \oplus \mathrm{ipad}) \mathbin{\Vert} m)\bigr)$$

とおく。$\mathrm{ipad}$, $\mathrm{opad}$ はそれぞれバイト 0x36, 0x5c を $b/8$ 個並べた定数である（RFC 2104、FIPS 198-1）。

HMAC では内側のハッシュ値は表に出ず、外側を長さ拡張しても、正しいタグの外側の入力はいつも「$b$ ビットの鍵と $n$ ビットのハッシュ値」という決まった長さなので、どのメッセージのタグにもならない。HMAC の安全性は圧縮関数についての仮定のもとで証明されている（ベラーレ・カネッティ・クラフチック 1996 年。ベラーレ 2006 年は、圧縮関数が擬似ランダム関数（鍵を知らない者にはランダムな関数と見分けがつかない関数）であるという種類の、衝突困難性を含まない仮定から証明した。主張のみ）。そのため SHA-1 の衝突が HMAC-SHA1 を直ちに破るわけではないが、新しい設計では HMAC-SHA256 以上を実績のあるライブラリで使う（$H(k \mathbin{\Vert} m)$ のような自作の構成は、Web API のリクエスト署名などで実際に長さ拡張攻撃を受けてきた。問題 7.2）。

7.5 格子と格子問題

格子は、実ベクトルの整数係数の一次結合だけを考える「整数版の線形代数」である。

定義 7.12（格子・基底・行列式）$b_1, \dots, b_n \in \mathbb{R}^n$ を一次独立とする。$L = \mathbb{Z}b_1 + \cdots + \mathbb{Z}b_n$（$b_i$ の整数係数の一次結合の全体）を $b_1, \dots, b_n$ で生成される格子 (lattice)、$(b_1, \dots, b_n)$ をその基底という。基底を列に並べた行列を $B = (b_1 \ \cdots \ b_n)$ とし、$\det L = \lvert \det B \rvert$ を $L$ の行列式 (determinant) という。

これは15-algebraic-number-theory 第3章の定義 3.1 の格子と同じで（行列式はそこでの余体積）、$\det L$ は平行体 $\lbrace \sum_i t_ib_i \mid 0 \leq t_i < 1 \rbrace$ の体積である。

定理 7.13（行列式は基底によらない）$(b_1, \dots, b_n)$ と $(b_1', \dots, b_n')$ が同じ格子 $L$ の基底ならば、$B' = BU$ をみたす整数行列 $U$ で $\det U = \pm 1$ となるものがある。特に $\lvert \det B' \rvert = \lvert \det B \rvert$ で、$\det L$ は基底の取り方によらない。

証明. 各 $b_j'$ は $L$ の元なので $b_j' = \sum_i u_{ij}b_i$（$u_{ij} \in \mathbb{Z}$）と書け、$U = (u_{ij})$ とおけば $B' = BU$。同様に $B = B'V$ となる整数行列 $V$ がある。$B = BUV$ で $B$ は正則なので $UV = I$。積公式（02-linear-algebra 第4章 定理 4.19）より $\det U \det V = 1$ で、どちらも整数なので $\det U = \pm 1$ である。$\square$

格子の計算では、グラム–シュミットの直交化（02-linear-algebra 第7章 定理 7.9 の $w_j$）を正規化せずに使う。

$b_1^{\ast}, \dots, b_n^{\ast}$ は互いに直交し、$b_1^{\ast}, \dots, b_i^{\ast}$ は $b_1, \dots, b_i$ と同じ部分空間を張る（$b_i^{\ast}$ は一般に格子の元ではない）。

命題 7.14 格子 $L$ の基底 $(b_1, \dots, b_n)$ について、

1. $\det L = \prod_{i=1}^{n} \lVert b_i^{\ast} \rVert$。
2. $0$ でない $v \in L$ はすべて $\lVert v \rVert \geq \min_i \lVert b_i^{\ast} \rVert$ をみたす。

証明. (1) $B = B^{\ast}T$（$B^{\ast} = (b_1^{\ast} \ \cdots \ b_n^{\ast})$、$T$ は対角成分が $1$ の上三角行列）なので $\det B = \det B^{\ast}$。$B^{\ast}$ の列を正規化した直交行列 $Q$ について $B^{\ast} = Q\operatorname{diag}(\lVert b_1^{\ast} \rVert, \dots, \lVert b_n^{\ast} \rVert)$ で、$\det Q = \pm 1$ である。(2) $v = \sum_i a_ib_i$（$a_i \in \mathbb{Z}$）で $a_j \neq 0$ となる最大の $j$ をとる。$i < j$ の $b_i$ は $b_j^{\ast}$ と直交し、$\langle b_j, b_j^{\ast} \rangle = \lVert b_j^{\ast} \rVert^2$ なので $\langle v, b_j^{\ast} \rangle = a_j\lVert b_j^{\ast} \rVert^2$。コーシー–シュワルツの不等式より $\lvert a_j \rvert \lVert b_j^{\ast} \rVert^2 \leq \lVert v \rVert \lVert b_j^{\ast} \rVert$ で、$\lvert a_j \rvert \geq 1$ だから $\lVert v \rVert \geq \lVert b_j^{\ast} \rVert$。$\square$

格子点 $v = Ba$ の係数 $a = B^{-1}v \in \mathbb{Z}^n$ は $v$ の一次式なので、長さが一定以下の格子点は有限個しかない。よって $0$ でない格子点の長さの最小値 $\lambda_1(L)$ が存在する。

定義 7.15（格子問題）基底が与えられたとき、$\lVert v \rVert = \lambda_1(L)$ となる $v \in L$ を求める問題を最短ベクトル問題 (SVP)、$0 < \lVert v \rVert \leq \gamma\lambda_1(L)$ となる $v \in L$ を求める問題を $\gamma$-近似 SVP という。基底と点 $t \in \mathbb{R}^n$ から $\lVert t - v \rVert$ が最小の $v \in L$ を求める問題を最近ベクトル問題 (CVP) という。

定理 7.16（ミンコフスキー）$L \subset \mathbb{R}^n$ を格子とすると、$\lambda_1(L) \leq \sqrt{n}(\det L)^{1/n}$ である。

証明. ミンコフスキーの凸体定理（15-algebraic-number-theory 第3章 定理 3.4。主張だけを使う）によれば、原点対称なコンパクト凸集合 $X$ が $\operatorname{vol}(X) \geq 2^n\det L$ をみたせば、$X$ は $L$ の $0$ でない点を含む。$r = (\det L)^{1/n}$ として $X = [-r, r]^n$ に適用すると、各座標の絶対値が $r$ 以下の $0 \neq v \in L$ があり、$\lVert v \rVert \leq \sqrt{n}r$ である。$\square$

SVP と CVP を厳密に解く問題は NP 困難である（CVP はファン・エムデ・ボアス, 1981 年。SVP は乱択帰着のもとでアイタイ, 1998 年。主張のみ）。暗号の根拠になる、近似倍率 $\gamma$ が $n$ の多項式程度の近似 SVP は、NP 困難かどうかは知られていないが、古典・量子のどちらでも知られている最良のアルゴリズムは $n$ について指数時間かかる。

7.6 2 次元のガウス簡約

2 次元では、ユークリッドの互除法と同じ考え方で最短ベクトルが求まる（ラグランジュとガウスによる二元二次形式の簡約理論にさかのぼる）。基底 $(b_1, b_2)$ が

をみたすとき、簡約されているという。

ガウス簡約（Gauss reduction）　入力は $\mathbb{R}^2$ の一次独立なベクトル $b_1, b_2$ とする。

1. $\lVert b_1 \rVert > \lVert b_2 \rVert$ なら $b_1$ と $b_2$ を入れ替える。
2. $\mu = \langle b_1, b_2 \rangle/\lVert b_1 \rVert^2$ とする。$\lvert \mu \rvert \leq 1/2$ なら $(b_1, b_2)$ を出力して終わる。
3. $\mu$ に最も近い整数を $m$ とし、$b_2 \leftarrow b_2 - mb_1$ とする（割り算の余りにあたる）。
4. $\lVert b_2 \rVert \geq \lVert b_1 \rVert$ なら $(b_1, b_2)$ を出力して終わる。そうでなければ $b_1$ と $b_2$ を入れ替えて 2 に戻る。

定理 7.17（ガウス簡約）

1. ガウス簡約は有限回の操作で終わり、出力は入力と同じ格子 $L$ の簡約された基底である。
2. 格子 $L$ の基底 $(b_1, b_2)$ が簡約されていれば $\lVert b_1 \rVert = \lambda_1(L)$ であり、$b_1$ と一次独立な $v \in L$ はすべて $\lVert v \rVert \geq \lVert b_2 \rVert$ をみたす。

証明. (1) 入れ替えと $b_2 \leftarrow b_2 - mb_1$ は、逆の操作（入れ替えと $b_2 \leftarrow b_2 + mb_1$）も整数係数なので、生成する格子を変えない。2 に来るたびに $\lVert b_1 \rVert \leq \lVert b_2 \rVert$ が成り立つ（最初は 1 により、2 回目以降は 4 の入れ替えによる）ので、2 で終われば簡約されている。3 のあとでは $\lvert \langle b_1, b_2 - mb_1 \rangle \rvert = \lvert \mu - m \rvert \lVert b_1 \rVert^2 \leq \frac{1}{2}\lVert b_1 \rVert^2$ なので、4 で終わっても簡約されている。4 で入れ替えて 2 に戻るとき、新しい $b_1$ は古い $b_1$ より真に短い $0$ でない格子点である。長さが最初の $\lVert b_1 \rVert$ 以下の格子点は有限個なので、入れ替えは有限回しか起こらない。

(2) $v = a_1b_1 + a_2b_2 \neq 0$（$a_1, a_2 \in \mathbb{Z}$）とすると、簡約されていることから

である。$a_2 = 0$ なら $\lVert v \rVert = \lvert a_1 \rvert \lVert b_1 \rVert \geq \lVert b_1 \rVert$。$a_2 \neq 0$（$v$ が $b_1$ と一次独立）のとき、$\lvert a_1 \rvert \geq \lvert a_2 \rvert$ なら第 1 項は $0$ 以上なので $\lVert v \rVert^2 \geq a_2^2\lVert b_2 \rVert^2 \geq \lVert b_2 \rVert^2$。$\lvert a_1 \rvert < \lvert a_2 \rvert$ なら第 1 項の係数は $0$ 以下なので、$\lVert b_1 \rVert \leq \lVert b_2 \rVert$ を使って

となる。よって $\lVert v \rVert \geq \lVert b_1 \rVert$ がつねに成り立ち、$a_2 \neq 0$ なら $\lVert v \rVert \geq \lVert b_2 \rVert$ である。$\square$

例 7.18 $b_1 = (42, 29)$, $b_2 = (55, 37)$ で生成される格子 $L$（$\det L = 41$）を簡約すると、$m = 1, 3, 2$ の引き算で $(13, 8)$, $(3, 5)$, $(7, -2)$ が順に現れ、簡約された基底 $(3, 5), (7, -2)$（内積は $11 \leq 34/2$）が得られる。定理 7.17 より $\lambda_1(L) = \sqrt{34}$ で、行列式は $\lvert 3 \cdot (-2) - 5 \cdot 7 \rvert = 41$ のまま、ほとんど平行だった入力（なす角は約 $0.7$ 度）が直交に近い基底（約 $75$ 度）に変わる。

7.7 LLL アルゴリズム

次元 $n$ が大きいとき、$n$ の多項式時間で最短ベクトルを求める方法は知られていない。1982 年にレンストラ・レンストラ・ロヴァースは、有理数係数の多項式の因数分解のために、最短ベクトルを指数的な近似倍率で求める多項式時間のアルゴリズムを与えた。

定義 7.19（LLL 簡約, LLL-reduced）$1/4 < \delta < 1$ とする。格子の基底 $(b_1, \dots, b_n)$ が次の 2 条件をみたすとき、$\delta$ について LLL 簡約されているという（原論文では $\delta = 3/4$）。

1. （サイズ簡約）すべての $j < i$ について $\lvert \mu_{ij} \rvert \leq 1/2$。
2. （ロヴァースの条件）すべての $2 \leq i \leq n$ について $\lVert b_i^{\ast} \rVert^2 \geq (\delta - \mu_{i,i-1}^2)\lVert b_{i-1}^{\ast} \rVert^2$。

ロヴァースの条件は $\lVert b_i^{\ast} + \mu_{i,i-1}b_{i-1}^{\ast} \rVert^2 \geq \delta\lVert b_{i-1}^{\ast} \rVert^2$ と同値で（$b_i^{\ast} \perp b_{i-1}^{\ast}$）、左辺は $b_{i-1}$ と $b_i$ を入れ替えたときの新しい $b_{i-1}^{\ast}$ の長さの 2 乗である（$n = 2$, $\delta = 1$ なら 7.6 節の「簡約されている」になる）。

定理 7.20（LLL 簡約基底の性質）$(b_1, \dots, b_n)$ を格子 $L$ の、$\delta = 3/4$ について LLL 簡約された基底とすると、

$$\lVert b_1 \rVert \leq 2^{(n-1)/2}\lambda_1(L), \qquad \lVert b_1 \rVert \leq 2^{(n-1)/4}(\det L)^{1/n}$$

が成り立つ。一般の $\delta$ については、$\alpha = 1/(\delta - 1/4)$ とおき、二つの不等式の $2$ を $\alpha$ に置き換えたものが成り立つ（$\delta = 3/4$ なら $\alpha = 2$）。

証明. サイズ簡約より $\mu_{i,i-1}^2 \leq 1/4$ なので、ロヴァースの条件から $\lVert b_i^{\ast} \rVert^2 \geq (\delta - 1/4)\lVert b_{i-1}^{\ast} \rVert^2 = \lVert b_{i-1}^{\ast} \rVert^2/\alpha$ で、繰り返すと $\lVert b_1 \rVert^2 = \lVert b_1^{\ast} \rVert^2 \leq \alpha^{i-1}\lVert b_i^{\ast} \rVert^2$（$1 \leq i \leq n$）。$\alpha > 1$ なので $\lVert b_i^{\ast} \rVert \geq \alpha^{-(n-1)/2}\lVert b_1 \rVert$ がすべての $i$ で成り立ち、命題 7.14 (2) より $\lambda_1(L) \geq \alpha^{-(n-1)/2}\lVert b_1 \rVert$。また $i = 1, \dots, n$ について掛け合わせると、命題 7.14 (1) より $\lVert b_1 \rVert^{2n} \leq \alpha^{n(n-1)/2}(\det L)^2$。$\square$

LLL アルゴリズム　入力は基底 $b_1, \dots, b_n$ と $\delta$。$k = 2$ とし、$k \leq n$ の間、次を繰り返して、$k = n + 1$ になったら $(b_1, \dots, b_n)$ を出力する。

1. （サイズ簡約）$j = k - 1, \dots, 1$ の順に、$\mu_{kj}$ に最も近い整数 $m$ をとって $b_k \leftarrow b_k - mb_j$ とする（$b_k^{\ast}$ と $\mu_{kl}$（$l > j$）は変わらず、$\mu_{kj}$ は $m$ だけ減るので、終わると $\lvert \mu_{kj} \rvert \leq 1/2$ となる）。
2. ロヴァースの条件 $\lVert b_k^{\ast} \rVert^2 \geq (\delta - \mu_{k,k-1}^2)\lVert b_{k-1}^{\ast} \rVert^2$ が成り立てば $k \leftarrow k + 1$、成り立たなければ $b_{k-1}$ と $b_k$ を入れ替えて $k \leftarrow \max(k - 1, 2)$ とする。

各段階の始めに $b_1, \dots, b_{k-1}$ が LLL 簡約されていること（帰納的に確かめられる）から、出力は LLL 簡約された基底である。

定理 7.21（LLL アルゴリズムの計算量。主張）成分が整数の基底を入力すると、$\delta = 3/4$ の LLL アルゴリズムは $n$ と $\log \max_i \lVert b_i \rVert$ の多項式時間で終わる。

証明の要点は、$b_1, \dots, b_i$ の内積を並べた行列の行列式 $d_i = \prod_{j \leq i}\lVert b_j^{\ast} \rVert^2$（正の整数）の積が、サイズ簡約では変わらず、入れ替えのたびに $\delta$ 倍未満になることである（詳細は Hoffstein–Pipher–Silverman）。実際の LLL は定理 7.20 の評価よりずっと短いベクトルを出力することが多い。小さなブロックごとに最短ベクトルを求める BKZ はより良い近似を与えるが、ブロックを大きくすると計算時間が指数的に増える。格子暗号の安全性の見積もりはこの計算量に基づく。

7.8 格子簡約による攻撃

部分和問題（ナップサック問題）は、正の整数 $a_1, \dots, a_n$ と $S$ から $\sum_i x_ia_i = S$ となる $x \in \lbrace 0, 1 \rbrace^n$ を求める問題で、一般には NP 困難である。これを使う暗号が公開鍵暗号の最初期に提案された。

例 7.22（メルクル–ヘルマン暗号, 1978 年）秘密の列 $r = (3, 5, 11, 20, 41, 83, 167, 331)$ は、各項がそれより前の項の和より大きい（超増加列）。$M = 673 > \sum_i r_i = 661$ と、$\gcd(W, M) = 1$ となる $W = 113$ も秘密にし、$a_i = Wr_i \bmod M$ を公開鍵とする：$a = (339, 565, 570, 241, 595, 630, 27, 388)$。平文 $x = (1, 0, 1, 1, 0, 1, 1, 0)$ の暗号文は $S = \sum_i x_ia_i = 1807$ である。正規の受信者は $113^{-1} \equiv 405 \pmod{673}$ を使って $405 \cdot 1807 \equiv 284 \equiv \sum_i x_ir_i$ を得る。$0 \leq \sum_i x_ir_i \leq 661$ なので $284 = \sum_i x_ir_i$ で、大きい項から貪欲に引けば $x$ が決まる（$284 = 167 + 83 + 20 + 11 + 3$）。

攻撃者は $W, M$ を知らないが、格子で $x$ を求められる。$\mathbb{R}^{n+1}$ のベクトル