暗号技術の現在 ? ポスト量子暗号への移行と量子暗号

全体概要

本セミナー「暗号技術の現在 ― ポスト量子暗号への移行と量子暗号」は、現代暗号技術の歴史的成立から、量子コンピュータが突きつける根本的脅威、そしてその先に広がる「ポスト量子暗号」標準化の動向と「量子暗号」の原理にいたるまでを、一貫した論理の流れで概観する、きわめて密度の高い知的旅程です。

中心的な問いは極めてシンプルです。「現在のインターネットを支える公開キー暗号は、量子コンピュータが実用化された後も安全であり続けられるのか」――この問いに対して、NSA・NISTを含む世界の安全保障機関がすでに「ノー」と答え、移行計画を公表し始めているという現実から、セミナーは出発します [p.4], [p.10]。

現代暗号の礎は1976/1977年に築かれました [p.7]。素因数分解の困難さを利用したRSA暗号、離散対数問題に基づく楕円曲線暗号、これらはすべて「計算複雑性理論」における「多項式時間」と「指数関数的時間」の非対称性という経験的事実の上に立っています [p.8], [p.60]。ところが1994年、Peter Shorは量子コンピュータを用いれば素因数分解が多項式時間で解けることを理論的に証明し、この前提を根底から揺るがしました [p.85], [p.86]。

Shorのアルゴリズムが実現可能な大規模量子コンピュータの構築には、長らく「事実上不可能」という評価が広く共有されていました [p.9]。しかし21世紀に入り、Google・IBM・Microsoft・Intelといったベンダーの参入とともに状況は一変し、2015年にNSAが「量子耐性アルゴリズムへの早期移行計画」を公表 [p.10]、翌2016年にはNISTが「Post-Quantum Cryptography」標準化プロセスを正式に開始しました [p.10], [p.117]。その目標期限は2022〜2024年とされています [p.119]。

セミナーは三部構成を取り、第一部で暗号技術の歴史的成立と計算複雑性理論の基礎を丁寧に積み上げ、第二部でShorのアルゴリズムの本質とNISTの標準化動向を詳述し、第三部では「計算の難しさ」に依らない量子の物理的性質そのものを安全保障の根拠とする「量子暗号（量子鍵配送）」の原理を解説します。最後に、現在の古典コンピュータと量子コンピュータが共存する「ハイブリッドの時代」を展望し、量子貨幣というフロンティアへと議論が広がっていきます。暗号技術は約20年ごとに大きな変化を遂げてきたという歴史的洞察 [p.11] が、全体を貫く時間軸として機能しています。

講義のロードマップ

■ Part 1: 現代暗号技術成立以前・現代暗号の成立・計算複雑性理論

• この部の核心:

現代暗号が「秘密に依拠する時代」から「計算の難しさに依拠する時代」へと転換した歴史的経緯と、その理論的基盤である計算複雑性理論の本質を提示します。第二次大戦期の機械式暗号から始まり、John NashとGödelが1950年代に書いた「手紙」の中に現代暗号の萌芽が読み取れるという驚くべき歴史的事実を起点に、RSA暗号・公開キー暗号の登場を論理的に位置づけます [p.12], [p.41], [p.43]。

• 論理展開:
• EnigmaやLorenz SZ42といった第二次大戦期の暗号機械と、それを解読したTuring Bombe・Colossusの対比から、暗号と計算能力の不可分な関係が示されます [p.19], [p.21], [p.23]。
• John Nashが1955年にNSAへ送った手紙には「鍵の計算に指数関数的時間のかかる暗号は事実上破れない」という洞察が明記されており、計算複雑性理論の萌芽として位置づけられます [p.43], [p.45]。GödelもNSAへの1956年の手紙で同様の問題意識に到達していました [p.46], [p.47]。
• RSA暗号の基礎となる「素因数分解の非対称性」（N=p×qの計算は易しいが逆は難しい）と、公開キー暗号の仕組みがAlice/Bobモデルで解説されます [p.50], [p.52]。なお、GCHQのEllis・Cocks・Williamsonがこれに先行していたことも示されます [p.55], [p.56]。
• 計算複雑性理論の階層（P・NP・NP-完全・BQP等）と「一方向関数」の概念が整理され、現代暗号がいかにNP問題の難しさの上に立っているかが明確にされます [p.62], [p.63], [p.68], [p.72], [p.73]。

■ Part 2: 量子コンピュータと暗号・Post-Quantum Cryptography標準化動向

• この部の核心:

Shorのアルゴリズムの数学的構造（古典部・量子部）を概説し、素因数分解がBQPクラスに属することを示した量子複雑性理論上の意義を解説します。続いて、NSA・NISTによる実際の政策・標準化プロセスの詳細を一次資料に基づいて提示し、「今なぜ移行しなければならないか」を Moscaの定理 [p.164] によって定式化します。

• 論理展開:
• Shorのアルゴリズムは「周期（位数）発見」を量子フーリエ変換（Phase Estimator回路）で高速化することで素因数分解を多項式時間化するものであり、RSAだけでなく楕円曲線暗号の基礎である離散対数問題も同様に破ります [p.85], [p.94], [p.95], [p.100]。
• BQPクラス（量子コンピュータで多項式時間で計算可能）は P⊆BQP⊆PSPACE と位置づけられ、FACTORINGがBQPに属することがShorの発見の理論的意義です [p.110], [p.112], [p.113]。
• NSAは2015年に「量子耐性アルゴリズムへの移行を早期に計画・開始する」と公表し、楕円曲線暗号が長期的解でないことを明言しました [p.120], [p.121], [p.124]。
• NISTはNISTIR 8105（2016年）でPQCの枠組みを整理し [p.130], [p.132], [p.138]、2019年1月にNISTIR 8240を発表してラウンド2候補として26アルゴリズム（Key Encapsulation 17件・署名 9件）を選出しました [p.148], [p.153], [p.156]。格子暗号・コード暗号・多変量多項式暗号・ハッシュ署名等が候補ファミリです [p.143], [p.144], [p.145], [p.146]。
• Moscaの定理「x（現在の暗号の必要寿命）＋y（移行期間）＞z（量子コンピュータ実現まで）なら今すぐ心配せよ」が移行の緊急性を端的に示します [p.161], [p.164]。Michele Moscaは2031年までにRSA-2048が破られる確率を1/2と推定しています [p.5], [p.171]。

■ Part 3: 量子暗号・古典量子ハイブリッドの展望・量子貨幣（Appendix）

• この部の核心:

「計算の難しさ」という経験的仮定に依存しない、量子力学の物理的性質そのものを安全保障の根拠とする「量子暗号」の原理を解説します。「観測の原理」と「No-Cloning定理」という二つの量子の本質的性質を丁寧に説明した上で、量子鍵配送プロトコルBB84の動作原理と盗聴検知能力を示します [p.186], [p.187], [p.190], [p.192]。

• 論理展開:
• 量子状態を観測すると重ね合わせが崩壊して古典bitが得られる一方、観測前の状態は復元不可能です（観測の原理）。またNo-Cloning定理により、未知の量子状態を完全にコピーすることは原理的に不可能です [p.189], [p.190], [p.191]。
• BB84では、AliceとBobが「標準基底（|0⟩,|1⟩）」と「アダマール基底（|+⟩,|−⟩）」をランダムに選んでエンコード・デコードし、一致した基底のビットだけを秘密鍵として共有します [p.193], [p.194], [p.198], [p.199]。盗聴者Eveが正しく情報を転送できる確率は最大25%であり、盗聴は確率的に検知できます [p.200], [p.201]。
• 量子貨幣（Appendix）では、No-Cloning定理を通貨偽造防止に応用するWiesner（1970年）の秘密キー方式 [p.207], [p.209], [p.211] と、2009年のLutomirski・Aaronson・Farhiらによる公開キー量子通貨方式 [p.215], [p.216] が紹介されます。後者は「誰でも真贋を検証できるが誰もコピーできない」という現代の公開キー暗号のアナロジーを量子の世界で実現しようとする試みです。
• 最後に、古典コンピュータと量子コンピュータ、古典通信と量子通信が共存する「ハイブリッドの時代」において、計算の複雑さではなく量子の物理的性質に直接依拠した新しい暗号技術が開花するという展望が示されます [p.11], [p.202]。