量子暗号の新しい数学

この物語 のオリジナル版はQuanta Magazineに掲載されました。

難しい問題は、通常は歓迎されません。しかし、暗号学者はそれを好みます。なぜなら、ある種の難しい数学の問題は、現代の暗号の安全性の基盤となっているからです。それらを解くための巧妙なトリックがあれば、ほとんどの暗号は破滅するでしょう。

数年前、研究者たちは、この潜在的な弱点を回避できる、根本的に新しい暗号化手法を発見しました。この手法は量子物理学の特異な性質を利用しています。しかし、従来の量子暗号化方式が限られた特定のタスクにしか対応していなかったのに対し、この新しい手法ははるかに幅広いタスクに対応可能です。さらに、従来の「古典的」暗号の核心となる問題がすべて容易に解決可能になったとしても、この手法は有効に機能する可能性があります。

しかし、この驚くべき発見は非現実的な仮定に基づいていました。カリフォルニア州バークレーにあるシモンズ計算理論研究所の暗号研究者、フェルミ・マー氏は、この結果は「概念実証に近い」と述べ、「現実世界に関する記述ではありません」と付け加えました。

今回、2人の暗号学者による新たな論文が、そうした突飛な仮定に頼ることなく量子暗号への道筋を示した。「この論文は、他の特定の仮説が正しいとすれば、量子暗号は必ず存在するはずだと述べている」とマー氏は述べた。

天空の城ラピュタ

現代の暗号は、3つの重要な部分からなる塔に例えることができます。最初の部分は塔の奥深くにある岩盤で、難解な数学的問題で構成されています。塔自体は2番目の部分であり、プライベートメッセージの送信、デジタル文書への署名、秘密投票などを可能にする特定の暗号プロトコルが存在します。

日常的なアプリケーションを数学的な基盤にしっかりと固定するのは、一方向性関数と呼ばれる構成要素からなる基盤です。この関数は、あらゆる暗号化方式に内在する非対称性の原因です。「メッセージを暗号化することはできても、復号することはできないため、一方向性なのです」と、NTTリサーチの暗号学者マーク・ザンドリー氏は述べています。

1980年代、研究者たちは一方向性関数上に構築された暗号が、様々なタスクのセキュリティを保証できることを証明しました。しかし、数十年経った今でも、その基盤がそれを支えるほど強固であるかどうかは確信が持てません。問題は、その基盤が特殊な難問（専門用語ではNP問題）で構成されていることです。NP問題の特徴は、候補となる解が正しいかどうかを容易に検証できることです。（例えば、数を素因数に分解することはNP問題です。大きな数の場合は困難ですが、検証は容易です。）

これらの問題の多くは本質的に困難に思えますが、コンピュータ科学者はそれを証明できていません。もし誰かが最も難しいNP問題を迅速に解く独創的なアルゴリズムを発見すれば、基盤が崩れ、塔全体が崩壊するでしょう。

残念ながら、塔を別の場所に移動するだけでは不十分です。塔の基盤である一方向性関数は、NP問題という岩盤の上にしか置けないのです。

より困難な問題の上に塔を築くには、暗号学者は一方向性関数ではない新たな基盤を必要とします。これは、ほんの数年前まで不可能と思われていましたが、研究者たちは量子物理学が役立つことに気付きました。

それは、ウィリアム・クレッチマーという大学院生が2021年に発表した論文から始まりました。この論文は、量子システムの特性に関する奇妙な問題に注目を集めました。研究者たちはすぐに、クレッチマーの問題が一方向性関数に取って代わり、暗号プロトコルの新たな塔の基盤となり得ることを示しました。翌年、クレッチマーらは、この代替アプローチがNP問題が困難な場合でも機能することを証明しました。突如として、はるかに堅牢な暗号要塞を構築できる可能性が出てきたのです。

しかし、それをどこに構築すればいいのでしょうか？クレッチマーが基礎として用いた量子問題は、特定の質問に瞬時に答えることができる「オラクル」と呼ばれる仮想的な計算装置に関するものでした。オラクルは理論上は便利なツールになり得ますが、実際には存在しません。クレッチマーの証明は、まるで空中に城を建てるための設計図のようでした。それを地上に実現する方法はあったのでしょうか？

第二のファウンデーション

2022年秋、この疑問はイリノイ大学アーバナ・シャンペーン校とNTTリサーチの暗号学者、ダクシタ・クラナの注目を集めました。クラナと大学院生のカビール・トメルは、暗号の新たな塔の構築に着手しました。まずは、古典的な一方向性関数の代わりに量子構成要素を用いた新たな基盤を構築する必要がありました。次に、この新たな基盤が他の暗号プロトコルの塔を支えられることを証明する必要がありました。基盤が塔を支えられることを証明したら、その塔全体を安定して設置できる堅固な場所、つまり古典的な暗号で用いられるNP問題よりもさらに困難と思われる現実世界の課題の基盤を見つける必要がありました。

最初のステップとして、クラーナとトメルは、一方向性関数の量子版である一方向性状態生成器に焦点を当てました。この生成器は、一方向性関数を有用にする3つの特性を満たしていました。第一に、この関数は高速に実行され、送信したいメッセージごとに暗号ロックとそれを開くための対応する鍵を容易に生成できる必要があります。第二に、各ロックは安全で、正しい鍵がなければ解錠するには多大な労力が必要です。最後に、すべてのロックは正しい鍵があれば簡単に開けられる必要があります。

決定的な違いは、鍵の性質にありました。古典的な一方向性関数は、ビット（古典コンピュータで情報を記憶する0と1）で構成される数学的な鍵を生成します。一方、量子一方向性状態生成器は、量子ビットと呼ばれる量子情報の単位で構成される鍵を生成します。これらの量子鍵は、たとえすべての古典的な鍵が簡単に破られてしまうとしても、安全性を維持できる可能性があります。クラーナ氏とトメル氏は、この新しい量子基盤を基盤として、その上に暗号プロトコルの塔を構築したいと考えました。「これは非常に困難であることがわかりました」とクラーナ氏は言います。「何ヶ月も行き詰まってしまいました。」

2023年7月、クラナは妊娠9ヶ月近くになり、育児休暇の取得を計画していた。トメルは何も考えていなかった。「ダクシタよりずっと悲観的なんだ」と彼は言った。「彼女はいつもうまくいくと信じているからね」

そして彼らは突破口を開いた。決定的なステップは、地下室の床のような役割を果たす別の数学的構成要素を定義することだった。つまり、一方向状態生成器の基礎を暗号プロトコルの塔に接続する構造だ。クラーナとトメルがその構成要素に必要な特性を解明したところ、量子特性と古典特性が複雑に混ざり合った一方向関数に似ていることがわかった。通常の一方向関数と同様に、錠前と鍵はどちらも古典ビットでできているが、これらの錠前と鍵を生成する手順は量子コンピュータでしか実行できない。さらに奇妙なことに、この新しい構成要素は一方向関数の最初の 2 つの定義特性を満たしていたが、3 つ目の特性は満たしていなかった。錠前と鍵を生成するのは簡単で、どの錠前も破るのは困難だった。しかし、鍵でその錠前を簡単に開けることはできない。

クラーナ氏とトメル氏は、これらの難解な新しい構成要素を「一方向性パズル」と名付けました。直感的に、これらがどのように役立つのか想像しにくいでしょう。決して使えない鍵に何のメリットがあるでしょうか？しかし、二人の暗号学者は、一方向性パズルを他の量子トリックと組み合わせることで、多くの暗号プロトコルを実現できることを示しました。原理的に互いに適合する錠前と鍵を生成できれば、解錠手順が極めて非効率的であっても問題にはなりません。

「任意に遅くなるアルゴリズムが存在するというだけで十分です」と、現在シモンズ研究所の研究員であるクレッチマー氏は述べた。「これは非常に驚くべきことです。」

欠けていたピースが揃ったので、彼らは8月4日にすぐに証明を終えた。クラーナさんの娘はそのわずか数日後に生まれた。

永久記録

11月までにクラーナは仕事に戻り、計画の第二段階に挑戦する準備が整った。彼女とトメルは、多くの種類の暗号が一方向性パズルの上に構築できること、そして一方向性パズルが一方向性状態生成器からなる新しい量子基盤の上に構築できることを示した。当初の計画における次のステップは、その量子基盤を新たな基盤、つまりNPよりもさらに解くのが困難な、比較的難解な数学問題群に接続することだ。

しかし、Khurana 氏と Tomer 氏はその課題に取り組む中で、より直接的なアプローチを取ることを決めました。つまり、一方向の状態生成器を忘れ、代わりに一方向のパズルを数学的な基盤に直接固定するというものでした。

ある観点から見ると、それは奇妙な選択に思えました。一方通行パズルは、クラーナとトメルが証明の中間段階で用いた数学的な奇妙な性質でした。

しかし、一方向パズルにはいくつかの利点もあった。一つには、量子的な性質を持つ一方で、生成される錠前と鍵は古典的なものだ。クラーナは、これによって一方向パズルを古典数学の基盤に結び付けやすくなるのではないかと考えた。さらに、一方向パズルは、錠前を実際に開けるには扱いにくい鍵を生成する。そのため、解法の検証さえ絶望的に困難に思えるほど複雑な問題に一方向パズルを結び付けやすくなる可能性もある。

しかし、具体的にどのような問題が有効なのでしょうか？クラーナは候補として、行列と呼ばれる数値表の要素の特定の組み合わせを計算する問題を念頭に置いていました。この問題は行列永久問題として知られており、大規模な行列では解くのが非常に困難で、計算が正しいかどうかを確認する簡単な方法はありません。行列永久問題には、暗号学者が魅力的と考える他の特別な数学的性質もあります。

「これは暗号の基礎となる素晴らしい問題となるだろう」とクラーナ氏は語った。

行列の永久問題は、量子コンピュータは容易に解けるものの、古典コンピュータでは解けないと思われる別の問題にも関連しています。研究者たちは、この量子計算の優位性を理論的に正確に証明しようと取り組んでいます。クラナとトメルは、そのような証明によって、永久問題の上に安全な一方向性パズル、ひいては量子暗号の塔全体を構築できることを示しました。

「彼らは綿密に研究された前提に基づいて、これを実現したのです」とクレッチマー氏は語った。「それを見て、本当に嬉しかったです。」

クラーナ氏とトメル氏は、今回の新たな結果によって、2つの未解決問題を実質的に1つに削減しました。研究者たちが、量子コンピュータが特定のタスクにおいて古典コンピュータを真に凌駕することを証明できれば、量子暗号は実質的にあらゆる古典暗号よりもはるかに強固な理論的基盤の上に立つことになります。

残念ながら、クラーナ氏とトメル氏の新しいアプローチを使って秘密のメッセージを送信することは、すぐには不可能です。近年の進歩にもかかわらず、量子コンピューティング技術はまだ彼らのアイデアを実用化できるほど成熟していません。一方、他の研究者たちは、より早期に実用化が期待できる量子暗号方式を考案していますが、真に安全であることを証明するには、さらなる研究が必要です。

量子暗号は既に驚くべき成果に満ちており、研究者たちはつい最近になってその可能性を探り始めたばかりだ。「私たちは、ずっと前から存在していたこの新しい世界を理解しようとしているだけです」とザンドリー氏は述べた。

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、 シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得 て転載されました。