暗号技術の現在

全体概要

本セミナー「暗号技術の現在」は、現代暗号技術の成立から量子コンピュータによる脅威、そしてポスト量子暗号（Post-Quantum Cryptography）の幕開けまでを、歴史的・数理的に俯瞰する野心的な技術講義です。

中心的な問いは「なぜ今、暗号技術は転換点を迎えているのか」です。現代暗号の基盤は、コンピュータが特定の数学的問題（素因数分解・離散対数）を効率的に解けないという「計算複雑性」に依存しています [p.7], [p.60]。この前提を根底から覆す可能性を示したのが、1994年にPeter Shorが発見した量子アルゴリズムです [p.88]。Shorのアルゴリズムは、量子コンピュータを用いれば素因数分解を多項式時間で解けることを理論的に証明し、RSA暗号・楕円曲線暗号を無効化しうると示しました。

この発見から約20年後の2015年、NSAは「来るべき量子耐性アルゴリズムへの移行計画を開始する」と公表し [p.15], [p.92]、NISTは2016年からPost-Quantum Cryptography標準化プロセスを開始しました。そして2022年7月、NISTはCRYSTALS-KYBERおよびCRYSTALS-Dilithiumなどの標準候補を発表するに至ります [p.99]。

これらのポスト量子暗号の技術的中核は「ラティス暗号」です。ラティス暗号は、高次元格子問題（SVP・CVP）の計算困難性を安全性の根拠とし、量子コンピュータをもってしても効率的に解けないとされています [p.204]。本セミナーは、Miklós Ajtai、Oded Regev、Craig Gentryら主要プレーヤーの業績を丁寧に追いながら、ラティス入門（基底・ラティス問題・等価な基底の構造）まで踏み込んで解説します [p.162]〜[p.222]。暗号技術はその時代の計算基盤とともに歴史的に変化するという視座が、講義全体を貫く哲学的軸となっています [p.11]。

講義のロードマップ

■ Part 1: 概説 ── エピソードで振り返る暗号史

• この部の核心:

暗号技術が「国家機密」から「標準技術」へと変容した歴史的経緯を、チューリングの名誉回復 [p.5], [p.6]、ナッシュのNSA宛書簡 [p.7], [p.8]、1976/77年の公開キー暗号・RSA暗号の成立 [p.10] というエピソードを軸に描きます。暗号は計算能力と通信基盤に依存して歴史的に変化するという認識が提示されます [p.11]。

• 論理展開:
• TuringによるEnigma解読は国家機密とされ、彼の功績は生前一切公式に認められなかった [p.5]
• NashはすでにP≠NP的洞察に到達し「指数関数的時間のかかる暗号は誰にも破れない」とNSAに書簡を送っていた（1955年）[p.8], [p.46]
• セキュリティがNational Securityを超えて万人に必要な標準技術となったことが、現代暗号の本質的変化 [p.11]
• NISTは2022年7月にNIST IR 8413を公開し、ポスト量子暗号標準の第三ラウンド報告を発表 [p.17]

■ Part 2: 第一部 ── 現代暗号技術の成立

• この部の核心:

1970年代後半に成立した現代暗号技術（公開キー暗号・RSA暗号・電子署名）の数理的基礎を解説します。一方向関数の困難性、素因数分解・離散対数問題との関係、そして計算複雑性理論（P・NP・NP完全）が暗号の安全性根拠であることを明確にします [p.26], [p.27], [p.60]。

• 論理展開:
• 公開キー暗号（Diffie-Hellman、1976年）とRSA暗号（Rivest-Shamir-Adleman、1977年）の仕組み：公開鍵で暗号化・秘密鍵で復号 [p.53], [p.55]
• RSA暗号の安全性根拠：N=p×qの素因数分解はNP問題であり、検証は多項式時間で可能だが発見は指数関数的時間を要する [p.51], [p.52], [p.68]
• 一方向関数の「難しさ」の確率的定義：逆算アルゴリズムが一定確率以下でしか成功しないこと [p.75]
• GCHQのEllis・Cocks・Williamsonは1970〜1974年にすでに公開キー暗号を発明していたが、機密扱いで1997年まで非公開 [p.57], [p.58]

■ Part 3: 第二部 ── Shorのアルゴリズムの発見

• この部の核心:

1994年のShorのアルゴリズム発見が暗号史に与えたインパクトと、量子複雑性クラスBQPの登場を解説します。量子並列性（Quantum Parallelism）の本質的な制約と、それを克服するSimonの問題・量子フーリエ変換・Phase Estimatorの連鎖的構造を詳述します [p.109], [p.126], [p.133], [p.139]。

• 論理展開:
• Shorのアルゴリズムは素因数分解を多項式時間で実行できることを証明し、RSA・楕円曲線暗号の両方を脅かす [p.88]
• 量子並列性だけでは2ⁿ個の計算結果から1つしか取り出せない根本的問題があり、追加の量子回路技術（Simon問題・QFT・Phase Estimator）が必須 [p.84], [p.125]
• BQPクラス（Bounded-Error Quantum Polynomial-Time）はP⊆BQPを満たし、素因数分解はBQPに属する。ただしBQPがNP完全問題を解けるかは否定的 [p.149], [p.151]
• GoogleのSycamoreによる「量子優越性」（2019年）はShorのアルゴリズムには遠く及ばないレベル [p.96], [p.82]

■ Part 4: 第三部 ── ラティス暗号の時代の始まり

• この部の核心:

ポスト量子暗号の技術的中核であるラティス暗号の基礎概念を丁寧に構築します。Ajtaiによる格子問題のone-way function応用（1996年）[p.164]、RegevのLearning with Errors（LWE）（2005年）[p.174]、GentryのFully Homomorphic Encryption（2009年）[p.179] という三段階の発展を追い、基底・SVP・CVP・等価な基底の代数的構造まで解説します。

• 論理展開:
• ラティスは空間上に規則的に配置された点の集合であり、n個の基底ベクトルの整数線型結合で定義される [p.183], [p.199]
• SVP（最短ベクトル問題）とCVP（最近ベクトル問題）は高次元で計算困難であり、これがラティス暗号の安全性根拠 [p.204], [p.205], [p.206]
• 同一ラティスを生成する「良い基底」（直交性が高い）と「悪い基底」（cosθ≈1）の違いが暗号設計の本質で、Babaiのアルゴリズムは良い基底があれば機能する [p.207], [p.210]
• NIST IR 8413はCRYSTALS-KYBER（KEM）とCRYSTALS-Dilithium（署名）を標準化対象に選定し、これらはいずれもLWEベースのラティス暗号 [p.177], [p.99]