なぜ量子計算が暗号を突破するのか
2025年12月29日
この記事を簡単にまとめると（AI要約）
目次
- ブロックチェーンと公開鍵暗号
- 「公開鍵暗号」とは？
- 暗号の種類
- なぜブロックチェーンに公開鍵暗号が必要なのか
- 公開鍵暗号の主な使い道
- 公開鍵暗号の仕組み
- 素因数分解から公開鍵暗号まで
- 簡単な例
- なぜ公開鍵は安全なのか：計算量とP/NP問題
- 計算量とは
- 現実的に解ける問題、解けない問題
- P/NP予想とその意義
- 公開鍵暗号と量子計算
- 素因数分解と量子計算：Shorのアルゴリズム
- 量子コンピュータはブロックチェーンを破壊できるのか
- 補遺：RSA暗号の詳細
- 参考文献
本稿では量子コンピューターと暗号理論について、誤解や批判を恐れず、出来るだけわかりやすくなるよう、細かい議論や細部のことは気にせず、大胆にも、大きな分類や比喩を多用した。専門家からすれば、「言い過ぎだ」、「簡略化し過ぎだ」と非難されることは承知で読者の理解に努めた。本稿を通じて読者諸君が、量子コンピューターや暗号理論がぼんやりとでも理解出来れば、著者らとしては大いに満足である。
近年、量子計算や量子コンピューターは、もはや基礎研究の話題にとどまらず、産業や情報セキュリティの文脈でも現実的に議論されるようになってきた。量子コンピューターは量子回路を用いて計算を行うため、特定の問題においては、従来のコンピューターでは現実的な時間で解くことが難しい計算を効率的に処理できる場合がある。
この点で注目されるのが、現代の情報インフラの多くを支えている暗号技術である。ブロックチェーンも例外ではなく、取引の正当性や資産の所有者を証明する仕組みは、公開鍵暗号をはじめとする暗号技術を前提として設計されている。もし量子計算が、これらの暗号が依拠してきた「計算の困難さ」を実用的に突き崩すとすれば、ブロックチェーンの安全性にも無視できない影響を与えることになってしまう。
本稿では、量子コンピューターが暗号技術に与えうる影響を整理したうえで、ブロックチェーンのどの部分が影響を受けやすく、どの部分は比較的影響を受けにくいのかを考察する。まずは、ブロックチェーンの基盤でもある公開鍵暗号の仕組みから確認していこう。
ブロックチェーンと公開鍵暗号
暗号技術の基本的な考えとして、鍵穴に合った鍵を作ることは難しいが、鍵穴とそれに対応した鍵であることの確認は簡単だ、ということがある。これを噛み砕いて、数学的な表現で言うなら、素因数分解と掛け算の対比になるだろう。「15を素因数分解しろ」と言われれば、「3×5=15だ」と容易に答えられるが、「では、2047を素因数分解してみろ」と問われて、即答できるだろうか？実際には、23×89=2047であるが、桁が大きくなるにつれ、人間どころか、コンピューターでさえ、素因数分解することも、素因数分解できるかどうか判定することも困難になることは想像に難くない。
現在世界中で利用されている暗号技術は、この素因数分解の性質と少しばかりの工夫を加え、堅牢な鍵と鍵穴、あるいは門番としての役目を果たしている。だが、昨今の量子コンピューターの発達により、この門番を蹴散らし、世界中の暗号が突破されてしまうという話を聞いたことはないだろうか？それが「Shorのアルゴリズム」であり、量子コンピューターの存在を前提とした、効率よく鍵を開けるマスターキーのようなものだ。要するに、量子コンピューターが汎用化すれば、素因数分解という門番は居ないも同然、という世界が訪れるかもしれない、ということなのだ。
以下、様々な具体例を交えて、ブロックチェーンを取り巻く暗号技術や量子コンピューターの実現可能性、それによるブロックチェーンの今後について論じていこう。
さて、まずは世界中で使われ、最も有名であろう暗号方式「公開鍵暗号」について考えていこうか。もはや公開鍵暗号は現代の情報通信技術の基盤だと言っても過言ではないほど普及している。公開鍵暗号のおかげで、インターネット上で安心して通信でき、ネットバンキングやオンライン決済といった秘匿性の高いアプリケーションが実現しているのも公開鍵暗号の力によるものである。もちろん、ブロックチェーンも例外ではなく、むしろ公開鍵暗号を基礎として成り立つ技術であり、公開鍵暗号が破られると、ブロックチェーンも一気に安全ではなくなるだろう。
では、その「公開鍵暗号」とは、一体何者なのだろうか？
※免責事項：本レポートは、いかなる種類の法的または財政的な助言とみなされるものではありません。