Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM

秘密を守る者たちと魔法のブラックボックス

あなたは、アリスとボブという二人の友人が、他の誰にも知られることなく共通のパスワードに合意しようとする、秘密のクラブを作ろうとしていると想像してください。彼らは声を出し合って会話することはできますが、ささやき声で話すことはできません。これを機能させるために、彼らは両方とも、質問に答える魔法の巨大な「ブラックボックス」にアクセスできます。特定の質問を投げかけると、ボックスはランダムな答えを返しますが、全く同じ質問を再び投げかけると、全く同じ答えを返します。これが現代の暗号技術の核心です。共有された、予測不可能なツールを使用して、公開された会話からプライベートな秘密を作り出すのです。

数十年にわたり、科学者たちは、もし友人たちが超高度な量子コンピュータを使用した場合、この設定が本当に安全であるかどうかを疑問に思ってきました。量子コンピュータは、スーパーパワーを持っているようなものです。それは、「重ね合わせ」（一度にすべてを行うという、おしゃれな言い方です）を用いて、ブラックボックスに多くの質問を同時に投げかけることを可能にします。大きな疑問はこうでした。アリスとボブは、これらの量子のスーパーパワーを使って、たとえ超スマートな盗聴者が彼らの公開された会話を監視していたとしても、解読できないような秘密を作り出すことができるのでしょうか？ この論文は、その問い、特に、友人たちが言葉による通常の古典的な言葉だけで会話するものの、数学的な計算やブラックボックスへの質問には量子の魔法を用いるというシナリオを深く掘り下げています。

不可能ではない、壊れない秘密

この論文は、この特定の量子設定において、完璧で壊れない秘密を作るという考えに対し、驚くべき、かつ決定的な「ノー」を突きつけています。著者たちのチームである研究者たちは、量子コンピュータとランダムなブラックボックスを使用し、もし友人たちが何度でもやり取りをすることを許される場合、完璧に安全な鍵合意プロトコルを作成することは数学的に不可能であることを証明しました。

彼らの発見の物語は以下の通りです。

セットアップ：かくれんぼのゲーム
アリスとボブがゲームをしていると想像してください。彼らはそれぞれ自分自身のプライベートで秘密のメモを持っています。彼らはメッセージを送り合いながら順番にターンを進めます。これらのメッセージは、「こんにちは」や「空は青い」といった、ごく普通のテキストです。しかし、メッセージを送る前に、彼らは両方とも、量子プログラムを実行して「魔法のブラックボックス（ランダム・オラクル）」に一連の質問を投げかけます。彼らはボックスに「質問Xに対する答えは何ですか？」や「では、質問Yはどうですか？」といった質問をするかもしれません。彼らはこれらの質問を量子の重ね合わせ状態で投げかけることができ、これは実質的に、何百万もの質問を同時に投げかけていることを意味します。これらの回答に基づいて、彼らは最終的な秘密の鍵に合意しようと試みます。

このゲームのルールは「完全な完備性（perfect completeness）」です。これは、もしブラックボックスが正しく機能しているならば、アリスとボブは必ず100%の確率で全く同じ鍵にたどり着かなければならないことを意味します。誤差の余地はありません。もし二人が異なる鍵を得てしまったら、プロトコルは失敗となります。

悪役：盗聴者
さて、イヴという名の悪党を想像してください。イヴは、アリスとボブが送るすべてのメッセージを監視しています。彼女は何も変更しません。ただ聞いているだけです。彼女もまた、同じ魔法のブラックボックスにアクセスできます。大きな疑問はこうです。イヴは、会話を聞き、自身でボックスに質問を投げかけることによって、秘密の鍵を解明できてしまうのでしょうか？

これまでの研究では、もしアリスとボブがたった2回しか会話をしなかった場合（2ラウンド・プロトコル）、イヴは簡単にコードを破ることができることが示されていました。しかし、もし彼らが10回会話したらどうなるでしょうか？ あるいは100回だったら？ 彼らの長い会話の中に、秘密を隠すことができるのでしょうか？

ブレイクスルー：不可能な盾
この論文は、アリスとボブが何度会話をしようとも、あるいは会話がいかに複雑になろうとも、イヴは常に勝利することを証明しています。著者たちは、イヴが100%の確実性で秘密の鍵を復元できる具体的な方法を構築しました。

この証明の仕組みを、簡単な比喩を使って説明します。

1. 可能性の地図： アリスとボブが会話するたびに、彼らはブラックボックスが提供しうるすべての回答の巨大な地図を、事実上絞り込んでいきます。彼らは量子の数学を使用しているため、彼らの回答の「形」は制限されます。著者たちは、アリスとボブが使用する関数の数学的な「次数（複雑さの尺度）」は、彼らがボックスに投げる質問の数によって制限されることを示しました。
2. 互いに素なパズル： アリスとボブが必ず全く同じ鍵に合意しなければならないため、彼らの数学的な経路は完璧に交差する必要があります。著者たちは、特定の会話のトランスクリプトに対して、アリスとボブが最終的に到達しうる鍵は、地図上の島のようなものであることを証明しました。これらの島は「互いに素（disjoint）」であり、重なり合うことはありません。もしアリスが鍵を「リンゴ」だと考えているなら、二人が合意するためには、ボブが「バナナ」と考えていることはあり得ません。
3. 探偵のトリック： 著者たちは、これらの「島」は数学的に非常に明確で、数も限られているため、イヴは推測する必要はないことを発見しました。彼女は巧妙な探索戦略を用いることができます。イヴがすべての可能な鍵のリストを持っていると想像してください。彼女はリストを半分に分け、本物の鍵が含まれているのがどちらの半分かを判断するために、ブラックボックスにいくつかの特定の質問を投げます。
4. 勝利の動き： この論文は、イヴがこの分割プロセスを非常に効率的に実行できることを示しています。たとえアリスとボブが膨大な数の量子的な質問をしたとしても、イヴは鍵を見つけるために、多項式個の「古典的な」質問（つまり、重ね合わせではなく、一つずつ順番に投げる質問）を投げるだけで済みます。具体的には、アリスとボブが $q_A$ 個および $q_B$ 個の質問をする場合、イヴは鍵を見つけるために $(q_A + q_B)^5$ 個程度の質問を投げるだけでよいのです。

結論
この結果の最もエキサイティングな部分は、これが「任意の」ラウンド数に対して有効であるということです。アリスとボブが1分間話したのか、あるいは1年間話したのかは関係ありません。秘密の鍵がどれほど長いかも関係ありません。この論文は、この特定のモデルにおいて、量子の重ね合わせという「盾」が秘密の鍵を守ることはできないということを証明しています。

著者たちは、単にこれが起こる可能性があると示唆しているのではなく、厳密な数学的証明を提供しています。彼らは、提示されたルールに適合するあらゆる可能なプロトコルに対して、盗聴者がそれを破るための特定の決定論的な方法が存在することを証明しました。盗聴者は天才である必要はありません。彼らは、証明によって提供されたレシピに従うだけでよいのです。そのレシピとは、ブラックボックスへの質問を行うプロセスを含んでいます。

要するに、この論文は、「より多くの会話」や「より多くの量子の魔法」が、この特定のモデルにおける完璧に完備された鍵合意を救うことができるという希望に、終止符を打ったのです。もしあなたが、この設定において受動的な盗聴者から100%安全な秘密を望むのであれば、この論文は、それは単純に構築不可能であると告げています。宇宙には、ヒントを世界に向かって叫ばなければならない状況において、どれほど上手く秘密を隠せるかという限界があるようです。