Certified Randomness with Optimal Rate

デジタル世界において、信頼は壊れやすい商品です。オンラインで投票したり、銀行用の秘密コードを生成したり、分散型ネットワークのリーダーを選出したりする際、私たちは真に予測不可能なランダム性に依存しています。もしこのランダム性が予測可能であったり偏っていたりすれば、システム全体が崩壊してしまいます。数十年にわたり、科学者たちは、生成を行っているマシンを信頼する必要のない方法でそのようなランダム性を生成する方法を模索してきました。理想的なシナリオとは、ビット（ゼロと一）の列を生み出すデバイスであり、その出力があまりにも混沌としていて均一であるため、デバイスの所有者であっても事前に結果を予想できないようなものです。これは「認定されたランダム性」という聖杯に関わる問題であり、事前の秘密シードを必要とせずに、誰でも検証可能な数学的保証をもたらすものです。

これまでの課題は、既存の手法がいずれか、操作されやすい弱いランダム性を生成するか、あるいは人間が小さなラン数の乱数となる開始番号を提供しなければならないという点でした。シッダールタ・ジェイン、サーチ・ムトレジャ、バスカール・ロバーツによる新しい研究は、この根本的な限界に対処しています。彼らは、量子コンピュータに対し、たとえそのコンピュータが悪意を持っていても、かつチェックを行う者が完全に決定論的（自身の持つ乱数を一切持っていない状態）であっても、それが極めて完璧に近いランダム性を持つビット列を生成したことを証明できるプロトコルを開発しました。この画期的な成果により、信頼できる出発点の必要性が排除され、理論的に可能な限り高いレベルでのランダム性の実現が可能となりました。

研究者たちは、「量子ランダムオラクルモデル」として知られるフレームワークの中で作業を進めました。これは、すべての当事者がユニバーサルハッシュのように機能する公開された完全なランダム関数にアクセスできる理論的な設定です。この環境下で、彼らは量子的プルーバー（証明者）が長いビット列を生成し、その文字列が真正にランダムであることを示す短い証明を提供するシステムを構築しました。鍵となる革新性は、証明を検証するベリファイア（検証者）自身がランダムである必要はなく、固定された決定論的なアルゴリズムであってもよいという点です。これを達成しようとした過去の試みは、高品質なランダム性を保証できなかったり、プロセスを開始するためにベリファイアが小さな信頼できるランダムシードを持っていなければならなかったりしました。新しいプロトコルはこのシードを完全に排除しており、決定論的なベリファイアであっても、信頼できない量子デバイスによって生成された長い文字列のランダム性を確信できることを証明しています。

意義を理解するためには、システムが完全にランダムではない場合に何が起こるかに注目する必要があります。もしビット列が「弱い」ランダム性しか持たない場合、それは混沌としているように見えても、特定のパターンに偏っている可能性があり、予測に対して脆弱になります。研究者たちは、彼らの手法が最大に近いエントロピー、すなわち無秩序さを保証することを証明しました。実用面では、これは特定の長さの文字列に対して、本当に予測不可能なビットの数が全長のほぼ等しくなることを意味します。唯一避けられないのは物理法則や計算の性質上生じる対数的な減少のみですが、これは非常に微小な損失です。これは、生成される文字列における保証されたランダム性の量が全長のほんの一部であった従来の多くの手法と比較して、大幅な進歩といえます。

プロトコルは主に2つの段階で作動します。第一に、量子デバイスは、量子攻撃に対して安全であることが証明されている特定の数学的構成を用いて、「弱い」ランダムソースを生成します。このソースはまだ高リスクなアプリケーションには十分ではありません。第二段階では、デバイスはこのソースをフィルターのような役割を果たす圧縮関数に通します。このフィルターは、弱いソースをより短く強力なビット列へと凝縮させます。研究者たちは、攻撃者が特定の入力を選択したり関数の挙動を観察したりすることでプロセスを操作しようとしても、最終的な出力を予測不可能にすることはできないことを示しました。最終的な文字列は、攻撃者が相互作用の履歴すべてを目にした後であっても困難な指標である「最小エントロピー（min-entropy）」の高い水準を維持します。

この研究の重要な要素は、「条件付き」最小エントロピーという概念です。例えば、1時間ごとに新しい乱数を放送するパブリック・ランダムネス・ビーコンのような現実世界の多くのアプリケーションでは、現在の数字のセキュリティは、以前の数字を知っていても現在の数字が予測できないという事実に基づいています。研究者たちは、自らのプロトコルが、それまでのメッセージやデータが与えられた条件下においても、それぞれ新しいランダムスの鼓動（パルス）が予測不可能であることを保証すると示しました。これは、ブロックチェーンネットワークにおけるリーダー選出や、暗号プロトコルのための共通ランダム文字列の生成など、現在のラウンドの整合性が過去の予測不可能性に依存する場合に不可欠です。

チームはまた、厳格な誠実さをもって自らの研究の限界についても言及しました。敵対者が多項式時間の実行を許容される場合、決定論的なベリファーを用いて完全で一様なランダム性を達成することは不可能であると彼らは証明しました。攻撃者は、一種の拒絶サンプリングと呼ばれる技術を使用して、出力の少数のビットを固定し、結果としてわずかなバイアスを生じさせるようシステムを操ることが理論的には可能です。しかし、研究者たちは自分たちのプロトコルが現実に即した制約の下で最善の結果を出していることを示しました。つまり、攻撃者が固定できるビット数は非常に小さいため、残りのランダム性はあらゆる実用的な暗号学的目的には十分であるということです。この損失は無視できるほど小さく、現実的なコンピューティング能力を持ついかなる攻撃者に対しても安全性は保たれます。

この研究は、セキュアな通信および分散型システムの未来に対して直接的な影響を与えます。信頼できるシードの必要性を排除することにより、本プロトコルは単一の信頼できない量子デバイス上で動作するランダムネス・ビーコンを作成することを可能にします。このようなビーコンは、誰もが検証可能な、新鮮で予測不可能な乱数を定期的に発行できます。これらの数値のセキュリティは、デバイス運営者の正直さに依存するのではなく、量子力学の法則とプロトコルの数学的構造に依拠することになります。現在の実装は理論的なモデルに基づいているものの、実用化への道筋はこれまで以上に明確になっており、機械を信頼することなく、現代のデジタル社会が必要とする信頼できるランダム性を生成する方法を提示しています。

この研究は、初期の研究者たちが提起した「認定されたランダム性」の限界に関する問いに対する確定的な回答となっています。決定論的なベリファイアにとって完全な一様性は数学的に到達不能であることを確認していますが、同時に、完全と区別がつかないほどのレベルのランダム性は達成可能であることを示しています。研究者たちは単にランダム性の率を向上させただけでなく、トラストレス（信頼不要）な環境における可能性の境界線を再定義しました。彼らの構築物は、量子ランダムオラクルモデルにおける堅牢で無条件のセキュリティ保証を提供し、量子時代におけるランダム性の考え方に新たな基準を打ち立てました。その結果としてのプロトコルは、理論的に健全であると同時に実践的にも関連性が高く、抽象的な量子理論と、安全なデジタル基盤が直面する具体的なニーズとの間の架け橋となっています。