量子科学が切り拓く、暗号理論の新しい数学

一般的に、複雑で解きにくい問題は歓迎されない。だが、暗号学者は難問を愛している。なぜなら、特定の難解な数学的問題こそが、現代の暗号のセキュリティを支えているからだ。それらを解く巧妙な方法が見つかれば、ほとんどの暗号技術は崩壊してしまう。

数年前、研究者たちはそのような潜在的な弱点をもたない、まったく新しい暗号化アプローチを発見した。このアプローチは、量子物理学の特殊な性質を利用したものだ。だが、いくつかの限られたタスクにしか使えなかった従来の量子暗号化スキームとは異なり、この新しい方法は、はるかに幅広いタスクを実現できる。そして、通常の「古典的」暗号化の基盤となる問題がすべて容易に解けるようになったとしても、このアプローチは機能し続ける可能性がある。

だが、この驚くべき発見は、非現実的な前提の上に成り立っていた。カリフォルニア州バークレーにあるシモンズ計算理論研究所の暗号研究者フェルミ・マーは、それを「どちらかと言えば概念実証であって、現実世界に関する主張ではありませんでした」と語る。

そして今回、ふたりの暗号学者が発表した新しい論文が、そうした現実離れした前提に頼らずに量子暗号へと至る道を示した。「この論文は、特定の仮定が正しければ、量子暗号は必ず存在することを示しています」とマーは語る。

オラクルで築く天空の城

現代の暗号は、3つの要素で構築される塔として捉えることができる。最初の要素は難解な数学的問題で、塔の土台となる岩盤に相当する。ふたつ目の要素は、地上にそびえる塔そのものだ。そこには、プライベートなメッセージの送信、デジタル文書への署名、秘密投票などを可能にする具体的な暗号プロトコルが組み込まれている。

岩盤と塔のあいだには、「一方向性関数」と呼ばれる構成要素でできた基礎があり、日常的な用途を数学的な岩盤にしっかり固定している。一方向性関数こそが、あらゆる暗号スキームに内在する非対称性を生み出すものだ。「メッセージを暗号化することはできても、復号化はできないため『一方向』と呼ばれています」と、NTTリサーチの暗号学者マーク・ザンドリーは説明する。

1980年代、研究者たちは一方向性関数に基づく暗号化を用いれば、さまざまなタスクにおいてセキュリティを保証できることを証明した。だが数十年が経ったいまも、研究者たちはその下の岩盤が本当に塔を支えられるだけの強度をもっているのか、確信をもてずにいる。というのも、その岩盤は専門家が「NP問題」と呼ぶ特殊で困難な問題で構成されているからだ。

NP問題の特徴は、解そのものを見つけるのは難しいが、その候補が正しいかどうかを確認するのは容易だという点にある（例えば、ある数を素因数に分解するのはNP問題のひとつであり、大きな数では実行が困難だが、確認自体は簡単にできる）。

こうしたNP問題の多くは、本質的に非常に困難であるように見えるが、コンピューター科学者はいまだそれが本質的に困難であるということを証明できていない。もし誰かが、最も困難なNP問題を高速で解く巧妙なアルゴリズムを発見すれば、岩盤は崩れ、塔全体が崩壊してしまうだろう。

残念ながら、塔を別の場所に移すことはできない。塔の基礎となる一方向性関数は、NP問題という岩盤の上にしか築けないからだ。

より強固な基盤の上に塔を建てるために、暗号学者たちは一方向性関数とは異なる新しい基礎を必要としていた。それは一見、不可能に思えた。だが数年前、研究者たちは量子物理学がその助けになるかもしれないことに気づいた。

2021年、大学院生のウィリアム・クレッチマーが発表した論文をきっかけに、量子システムの性質に関するある奇妙な問題に注目が集まった。やがて研究者たちは、クレッチマーの問題が一方向性関数に代わる存在となり、暗号プロトコルの新たな基礎になりうることを示唆し始めた。翌年、クレッチマーらはこの代替アプローチが、困難なNP問題を必要とせずに機能することを証明した。突如として、はるかに強固な暗号の要塞を築ける可能性が現実味を帯びてきたのだ。