講演資料
講義資料スライドの表紙です。上のスライド画像をクリックすると、同じ画面のまま全編のPDF資料を快適に閲覧・印刷することができます。
セミナーの概要
本セミナー「ラティス暗号入門」は、現代暗号の次世代を担うと目される「ラティス暗号」、特に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]。
■ Part II: ラティス暗号 LWE
LWE暗号の動作原理を、Oded Regev自身が提示する「高校生向けの最も単純なサンプル」から始め、徐々に一般的なプロトコルへと拡張します。エラー項eがなぜ不可欠であるか、エンコード・デコードがなぜ正しく機能するか、という核心的な問いに数式で答えることがゴールです [p.110〜p.178]。
■ Part III: ラティスとラティス暗号
LWE暗号の安全性の数学的根拠を解明することがゴールです。LWE問題を定式化し、それが解けることは既知のラティス困難問題（GapSVP, SIVP）が解けることと同等であることを、Ajtaiの業績とRegevの証明の概要を通じて示します。特にDualラティスとフーリエ変換を用いた量子的還元という独創的な証明手法が核心です [p.183〜p.252]。
ページのナビゲート