Scribble at 2026-04-21 12:49:18 Last modified: 2026-04-22 08:04:24

上にご紹介するのは、暗号学の専門家であるフィリッポ・ヴァルソルダが書いたブログ記事だ。要点はシンプルであり、量子コンピュータが登場しても128ビットの対称鍵暗号は安全であり、ポスト量子暗号への移行の一環として鍵のサイズを大きくする必要はないということだ。

昨今は量子コンピュータの開発が多くの国で進められており、マスコミの短絡的な文章や番組などによって（素養のない新聞記者やジャーナリストやライターどもによる自己催眠のようなものだが）、あたかも既存の暗号技術が無意味になるかのような印象操作が普及しつつある。しかし、その多くは自分たちの開発している量子コンピュータを宣伝して投資や公的な補助金を集めるためのブラフであったり、開発者自身が暗号技術に対して無知であるがゆえの誤解に基づく解説だったりする（量子コンピュータを開発できるからといって、その人が情報セキュリティについても高度な理解や技術をもつとは限らない。コンピュータや数学の一分野を扱っているだけで何でも知っているなどと思い込むのは、それこそ学者やエンジニアに対する期待や羨望という名の偏見であろう）。

かようなわけで、IT 業界では、量子コンピュータがもたらす脅威によって対称鍵暗号技術のセキュリティ・レベルが半減し、従来の128ビットで扱ってきたのと同じていどの安全性を暗号化システムに持たせるためには256ビットの鍵が必要になるという説明が広まっている。著者はこのような説明が誤解を招くもの（あるいは誤解にもとづくもの）であると指摘し、それが誤解であるという理由を、理論と技術によって詳しく説明している。

著者のフィリッポによれば、こういう誤解の根本的な原因は、量子コンピュータの研究成果として知られるようになった、グローバーのアルゴリズムをどうやって適用するかという可能性を誤って解釈している点にあるという。そこでまずはグローバーのアルゴリズムを説明しよう。グローバーのアルゴリズム (Grover's algorithm)は、1996年にロブ・グローバーによって考案されたアルゴリズムであり、主に構造化されていないデータベースからの情報探索を劇的に高速化する手法として知られている。例として、N 個のデータがバラバラに並んでいるような状況を考えよう。その中から、目当ての情報１個を探索したい。どういう順番で、どんな基準で探索するのが最も効率的だろうか。これは、離散数学のアルゴリズム論という分野で「探索問題」と呼ばれているパターンの課題だ。ウェブの制作会社でコーダやデザイナーから「クラス・チェンジ」してプログラマをやっていたり、法律学科や国文学科を出て IT ゼネコンに新卒入社してからデジタル・ブルーカラーとなった諸君、あるいは「あなたも明日からウェブ・エンジニア！」などという教材でプログラマを名乗っているクラウド・ワーカーなどの多くは知らない話題だと思うが、開発ベンダーや IT ベンチャーのプログラマ、つまり最低でもコンピュータ・サイエンスの学士号をもつ人や応用情報技術者資格（AP）をもつ人であれば常識の類だろう。

古典的なアプローチでは、データを最初から一つずつ順番に確認していくしかない。データが不規則に並んでいるからだ。最悪の場合は N 回の確認が必要であり（つまり最後のデータまで全て確認しないとわからないかもしれないということ）、平均しても ^^N/2^^ 回の確認が必要だから、離散数学において何かを計算したり数えるために必要な「計算量」というスケールを使うのだが、その計算量は ^^O(N)^^ という評価になる。これに対して、グローバーのアルゴリズムは量子力学の性質を活用することで、およそ ^^\sqrt{N}^^ 回の確認で目的のデータを見つけ出せるため、計算量は ^^O(\sqrt{N})^^ となる。このアルゴリズムは確認する効率を二乗も向上させるとされていて、データの総数が ^^100,000,000個 = 10^6^^ だったら、最悪の場合は100万回の確認が必要となるところを、二乗の効率化により ^^10^3^^ つまり1,000回の確認で済ませられることになる。よって、短絡的な解説をする人々は、パスワードの解析における照合の回数も劇的に少なくなると騒いでいるわけだ。しかし現実には、対称鍵暗号方式のアルゴリズムで使われる暗号化関数は、暗号化するべき入力値を一つずつ直列に実行していく必要がある。古典的なコンピュータの総当たり攻撃のように、探索するデータの集合を分割して何万台ものマシンで一斉に並列処理させようとすると、アルゴリズムの効率が大幅に悪化してしまう。結果として、現実的な時間内で処理を終わらせようとすれば、解析のためのシステム全体で必要な仕事量が爆発的に増えるため、128ビットの対称鍵暗号の鍵の長さは依然として十分な安全性を持っている、というのが専門家たちの結論だ。

ここで、単純な疑問が出てくると思う。量子コンピュータの話をしているのに、どうして目的とするデータの探索を直列に実行しなくてはいけないのだろうか。そんな条件が必須であれば、そもそも量子コンピュータの性能である並列処理を使っていないのと同じであろう。実は、グローバーのアルゴリズムが効果を発揮するためには、それまでに計算した結果を再利用するという再帰性が必要であり、複数の確認を同時に並列に実行すると、お互いの結果を利用できないため、グローバーのアルゴリズムは適用できないのである。よって、量子コンピュータを使ったとしても、或る128ビットの暗号鍵を解読するためには、10年間継続して攻撃を実行したとしても、724の論理量子ビットを備えた量子回路が140兆個も必要になる。これは現実的な数字ではない。寧ろ、非対称鍵の暗号方式を破るために使われるショアのアルゴリズム (Shor's algorithm) が高い効率で実行できるとされていて、グローバーのアルゴリズムを用いて128ビットの鍵を破るコストは、ショアのアルゴリズムを用いて256ビットの楕円曲線暗号を破るコストよりも、4,300,000,000,000,000,000,000倍のコストがかかる。これでは論外だ。よって、現在の暗号化方式に対する現実的な脅威は、寧ろショアのアルゴリズムを応用する攻撃であろう。マスコミに煽られて、安全性が保たれている対称鍵暗号の更新を行おうとすれば、システムの複雑化や互換性の問題を引き起こすし、無用なコストもかかる。