ラティス暗号入門

全体概要

本セミナー「ラティス暗号入門」は、現代暗号の次世代を担うと目される「ラティス暗号」、特にLWE（Learning with Errors）暗号の数理的基礎から理論的安全性の証明まで、体系的に解説する高度な技術講義です。

その背景には、深刻な問題意識があります。1994年にShorが発見した量子アルゴリズムは、現在広く利用されているRSA暗号や楕円曲線暗号の理論的根拠である「素因数分解問題」「離散対数問題」を多項式時間で解いてしまいます。量子コンピュータが十分な規模に達した暁には、現行の公開鍵暗号インフラは根底から崩壊するという「ポスト量子暗号」問題です。この「Post Shor、Pre Quantum」という中間時代において、暗号研究者たちはその解決策を長らく模索してきました [p.237], [p.238]。

こうした状況を打破したのが、本講義の主役であるOded Regevです。彼はAjtaiの先行研究を継承・発展させ、2005年にLWE暗号を提案しました。LWE暗号の安全性は、格子上の難問（GapSVP、SIVPなど）の困難さに還元でき、かつその還元が厳密な理論として証明されている点に革命的な意義があります [p.240], [p.241]。

本講義はまず「ラティスとは何か」という直感的な理解から出発し、基底・ユニモジュラー変換・Dual ラティスといった数学的概念を丁寧に構築します [p.7]〜[p.105]。次に、Regevが「高校生にもわかる」と言うLWEの具体的なプロトコルを、実際の数値サンプルを用いて理解させます [p.109]〜[p.178]。最後に、LWE問題とラティス問題の複雑性理論的な関係、Ajtaiの一方向関数、Regevの量子的還元証明の概要という、研究者レベルの理論的核心に踏み込みます [p.183]〜[p.252]。

本セミナーは「なぜラティス暗号が量子耐性を持つと考えられるか」という根本的な問いに、数学的誠実さをもって答えようとする、入門から理論的深部までをカバーした稀有な講義です。

講義のロードマップ

■ Part I: ラティス入門

• この部の核心:

ラティス（格子）とは何かを直感的・数学的に理解することがゴールです。物理結晶やエッシャーの絵画などに見られる「繰り返し構造」という日常的概念から出発し、格子点の座標表現、基底によるラティスの定義、そして同一ラティスを生成する無数の基底の存在とその変換規則（ユニモジュラー行列）まで、段階的に数理構造を構築します [p.9]〜[p.105]。

• 論理展開:
• ℤ²はラティスであり、格子点は二つの整数の組として表現される [p.29], [p.30], [p.31]。
• ラティスの「基底」は一意ではなく、ユニモジュラー行列Uを用いた変換 `L(B) = L(BU)`（det(U)=±1）により無数の等価な基底が存在する [p.72], [p.73]。
• SVP（最短ベクトル問題）とCVP（最近ベクトル問題）は、次元が高くなると計算困難になるラティスの基本問題である [p.46], [p.47], [p.48]。
• Gram-Schmidt直交化はベクトル空間の任意の基底を直交化する手法だが、ラティスの基底に適用しても同じラティスを張るとは限らない点が重要である [p.94]〜[p.105]。

■ Part II: ラティス暗号 LWE

• この部の核心:

LWE暗号の動作原理を、Oded Regev自身が提示する「高校生向けの最も単純なサンプル」から始め、徐々に一般的なプロトコルへと拡張します。エラー項eがなぜ不可欠であるか、エンコード・デコードがなぜ正しく機能するか、という核心的な問いに数式で答えることがゴールです [p.110]〜[p.178]。

• 論理展開:
• 最も単純なLWEの例：秘密キーsに乱数を掛けて小さな偶数エラーを加えた公開キーリストを生成し、そのサブセットの和でビットをエンコード。デコードはsで割った余りの奇偶判定による [p.114]〜[p.126]。
• ℤq上の一般的プロトコル：`B = A^T s + e`で公開キーBを生成。エンコードは`u=Ax, v=B^T x + bit·(q/2)`、デコードは`Dec = v - s^T u`を計算し`q/2`との大小比較で判定する [p.155]〜[p.170]。
• デコードが成立する理由：`Dec = e^T x + bit·(q/2)`であり、エラー項eが十分小さいとき`e^T x ≈ 0`となるため、Decはbit·(q/2)に近似できる [p.177]。
• エラー項eは平均0、標準偏差αqのディスクリート正規分布からサンプリングされ、これがLWE（Learning *with Errors*）の名の由来である [p.173], [p.174]。

■ Part III: ラティスとラティス暗号

• この部の核心:

LWE暗号の安全性の数学的根拠を解明することがゴールです。LWE問題を定式化し、それが解けることは既知のラティス困難問題（GapSVP, SIVP）が解けることと同等であることを、Ajtaiの業績とRegevの証明の概要を通じて示します。特にDualラティスとフーリエ変換を用いた量子的還元という独創的な証明手法が核心です [p.183]〜[p.252]。

• 論理展開:
• LWE問題の定式化：` + e_k ≈ b_k`（e_kは小さなエラー）という近似式が多数与えられたとき秘密ベクトルsを求める問題。エラーがなければ連立方程式として容易に解けるが、エラーの存在が計算を困難にする [p.189]〜[p.192]。
• Ajtaiの貢献：SIS問題（Az=0を満たす短い整数ベクトルzを求める問題）に基づき一方向関数`f_A(x) = Ax`を定義。`f_A`の衝突耐性はSIS問題の困難性に等しく、これはラティス問題GapSVPのワーストケース困難性に還元される [p.219]〜[p.225]。
• Dual ラティスの定義：`L* = { y ∈ ℝⁿ | ∀x ∈ L, ∈ ℤ }`。det(L*)=1/det(L)となり、元のラティスを「細かくする」対称的な構造を持つ [p.228]〜[p.235]。
• Regevの証明の核心：ラティスLの正規分布DᵣからのサンプリングとDualラティスL*上の関数`f_{1/r}`をフーリエ変換で往復させることで、LWEオラクルを用いてGapSVPおよびSIVPへの量子的還元を構成する。この変換の繰り返しにより分布の標準偏差を1/2ずつ縮小させてShort Vectorを得る [p.244]〜[p.252]。