Experimental asymmetric relativistic zero-knowledge proofs with unconditional security

本論文は、特殊相対性理論と量子非局所性を活用することで、従来の対称的な手法における非現実的なラウンド複雑性を克服し、量子攻撃に対する無条件の安全性を実現する、実験的に検証された効率的な非対称相対論的ゼロ知識証明プロトコルを提示する。

要約

全体像：秘密を明かさずに、自分が知っていることを証明する

想像してみてください。あなたは宝物の地図を持っていますが、疑り深い門番に対して「自分はその地図を持っている」ということを証明したいと考えています。しかし、地図を盗まれるかもしれないので見せたくはありませんし、宝物がどこにあるかも教えたくありません。ただ、「道を知っている」ということだけを証明したいのです。

デジタル世界では、これを**ゼロ知識証明（ZKP）**と呼びます。これは、パスワードや銀行の残高を明かすことなく、「自分が誰であるか」や「取引に必要な十分な資金を持っていること」を証明できる魔法のような技術です。

問題点：量子モンスター

数十年の間、これらのデジタルの魔法は、人間には解くのが難しいがコンピュータには解きやすい数学パズルに依存してきました。しかし、科学者たちは量子コンピュータという、まるで「スーパーファストなモンスター」のような存在を作り上げています。これらのモンスターは、従来の数学パズルを瞬時に解いてしまい、現在のデジタルロックのセキュリティを破壊してしまいます。

私たちは、数学パズルに頼らない新しい種類のロックを必要としています。物理法則に基づいたロックが必要です。

解決策：「光速」のロック

この論文は、相対論的ゼロ知識証明と呼ばれる新しいタイプの証明を紹介しています。これは、難しい数学に頼るのではなく、光速に依存しています。

比喩：二つの頭を持つドラゴン
二つの頭を持つドラゴン（頭Aと頭Bと呼びましょう）を想像してください。あなたは裁判官に対して、そのドラゴンが実在することを証明したいのですが、二つの頭が互いに会話することを許してはいけません。

• 裁判官は、頭Aから遠く離れた場所に立ちます。
• もう一人の裁判官は、頭Bから遠く離れた場所に立ちます。
• その距離は非常に大きく、たとえ宇宙で最も速いもの（光）であっても、質問に答える時間内に頭Aから頭Bへ移動することはできません。

なぜなら、頭Aと頭Bは、嘘を合わせるために通信できるほど速く動けないため、真実を話さざるを得なくなるからです。もし彼らが騙そうとしても、物理法則（具体的には、光より速く移動できるものは存在しないという法則）によって捕まってしまいます。

このチームが行ったこと

研究者たちは、この「二つの頭を持つドラゴン」証明の実装版を構築しました。彼らは以下のように改良を行いました。

1. 従来の方法は遅すぎた： 以前のこの「二つの頭を持つドラゴン」証明の試みは、巨大な迷路を一本一本の道をすべて歩いて進むようなものでした。もしマップ（グラフ）が大きければ、証明を終えるのに数千年かかることもありました。理論的には可能ですが、実用的ではありませんでした。
2. 新しい方法は速い： チームは、よりスマートな**非対称（アシンメトリック）**バージョンを設計しました。これは、ドラゴンの片方の頭がすべての重労働を行い、もう片方の頭は見守るだけという仕組みです。
   • 結果： 彼らは、必要とされる時間を「数千年」から0.22秒へと短縮しました。
   • コスト： 「ランダム性」（トランプのデッキをより何度もシャッフルすることのようなもの）を少し多く使用しましたが、使用されるデータの総量は、現代のハードドライブに収まるほど十分に小さくなりました（約430 MB）。

実験

これが現実世界で機能することを証明するために、彼らは南京大学で実験を行いました。

• 二台のコンピュータ（「頭」）を、300メートル離れた異なる建物に配置しました。
• 高速レーザーとGPS時計を使用し、コンピュータ同士が光よりも速く通信できないようにしました。
• コンピュータに対し、複雑な地図を3色だけで塗り分ける方法（古典的な数学パズル）を知っていることを、色を見せずに証明するよう求めました。
• 結果： コンピュータはこの証明全体を0.22秒で完了しました。

なぜこれが重要なのか

この論文は、これが大きな前進であると主張しています。その理由は以下の通りです。

• 量子耐性がある： 量子コンピュータがコードを破ろうとしても、物理法則（光速）を破ることはできないため、不正を行うことができません。
• 実用的である： 以前のバージョンは実用化するには遅すぎましたが、これはオンラインバンキングや投票のセキュリティ確保など、実生活での使用に十分な速さを持っています。
• 無条件である： 「この数学は難しいはずだ」という推測ではなく、「光には速度制限がある」という事実に基づいています。

まとめ

研究者たちは、「嘘つきを止めるために光速を利用する」という理論的なアイデアを、実際に動作するマシンへと作り上げました。彼らは、システムの一方がより多くの作業を行うようにすることで、遅すぎるという問題を解決し、プロセスを極めて高速かつ、将来の量子コンピュータに対しても安全なものにしました。

技術概要

技術要約：実験的な非対称相対論的ゼロ知識証明（無条件セキュリティ）

問題提起

ゼロ知識証明（ZKP）は、暗号通貨やスマートコントラクトなどのデジタル経済において、信頼とプライバシーを確立するために極めて重要である。しかし、古典的なZKPプロトコルは計算量的仮定（例：一方向関数の存在）に依存しており、将来の量子攻撃に対して脆弱である。量子ZKPは潜在的な代替案となるが、量子複製不可能定理（no-cloning theorem）による量子リワインディングの困難さや、無条件に安全な量子ビットコミットメントの不可能性といった、重大な実装上の障壁に直面している。

相対論的ZKP（RZKP）は、計算量的仮定を特殊相対性理論の原理（具体的には、信号非伝達原理：no-signaling principle）に置き換えることで、この解決策を提示している。最近の進展により、グラフの3彩色問題に対する対称的なRZKPが実証された。しかし、この対称プロトコルは、量子相関を持つプロバー（証明者）に対する**量子的な健全性（quantum soundness）**を確保しようとすると、法外な非効率性に陥る。量子的な健全性を実現するために、対称プロトコルでは $O(|E|^4)$ （$|E|$ はエッジ数）のラウンド複雑性を必要とし、これは現実的なサイズのグラフに対して、達成不可能な実行時間と膨大なランダムネスコストを強いることになる。

手法

著者らは、従来の対称的なアプローチにおける効率性の限界を克服しつつ、量子相関を持つプロバーに対しても無条件のセキュリティを維持するように設計された、非対称相対論的GMW ZKPプロトコルを提案し、実験的に実装した。

プロトコル設計

プロトコルは、2組の空間的に離れたプロバー・検証者ペア（$P_1-V_1$ および $P_2-V_2$）で構成され、$m$ 回のインタラクティブなラウンドにわたって、グラフ $G(V, E)$ が彩色を明かすことなく3彩色可能であることを証明する。

1. 準備（Preparation）: プロバー $P_1$ と $P_2$ は、ランダムな色の置換 $\pi$ と、ランダムな値の集合 $B = \{b_k\}$ を共有する。
2. クエリフェーズ（Query Phase）: 検証者 $V_1$ が $P_1$ に対してランダムなクエリ $X = \{x_k\}$ を送信する。
3. コミットフェーズ（Commit Phase）: $P_1$ は、コミットメント $A = \{a_k\}$（ここで $a_k = x_k \cdot y_k - b_k$、 $y_k$ は色）を計算し、$V_1$ に送信する。
4. チャレンジフェーズ（Challenge Phase）: 検証者 $V_2$ はランダムなエッジ $C = \{i, j\}$ を選択し、$P_2$ に送信する。
5. 開示フェーズ（Reveal Phase）: $P_2$ は、色 $Y(C)$ と対応する値 $B(C)$ を $V_2$ に開示する。
6. チェックフェーズ（Check Phase）: 検証者は、相対論的制約（時間遅延 $|t_1 - t_4| < \tau$ および $|t_2 - t_3| < \tau$、ここで $\tau = d/c$ を検証することで、$P_1$ と $P_2$ の間の信号伝達がないことを確認する）および論理的一貫性（色が異なり、かつコミットメントと一致していること）を検証する。

理論的分析

著者らは、量子的な健全性の課題に取り組んでいる。古典的なプロトコルではビットコミットメントは強力に拘束的（strongly binding）であるが、相対論的ビットコミットメントは「和拘束（sum-binding）」のみを保証する。著者らは、悪意のある量子プロバーが不正なエッジに対して成功する確率は、非局所的な CHSH$_{Q(2)}$ ゲーム の量子値によって上限が抑えられることを示した。このゲームとプロトコルの健全性誤差を関連付けることで、量子的な健全性誤差 $\delta$ に対する厳密な上限を導出した。

実験的実装

チームは、以下のものを用いて原理実証実験を実施した。

• ハードウェア: 低レイテンシ処理のためのFPGA（Field-Programmable Gate Arrays）および、高精度なGPS時刻同期サーバー（原子時計搭載）。
• セットアップ: 300メートルの距離（$\tau = 1000$ ns の時間分離に相当）で離れた2組のプロバー・検証者ペア。
• グラフ: $|V| = 588$ 頂点、 $|E| = 1097$ エッジを持つ3彩色可能なグラフ。
• 実行: 実験は、必要なすべてのインタラクティブなラウンドを約 0.22秒 で完了した。

主な貢献

1. 効率的な非対称プロトコル: 著者らは、量子的な健全性を備えた従来の対称型プロトコルのラウンド複雑性を $O(|E|^4)$ から $O(|E|)$ へと削減する、非対称相対論的GMW ZKPを設計した。これは、GMWフレームワーク内で2プロバー相対論的ビットコミットメントを利用することで、証明と一貫性チェックを単一のラウンド内で同時に行うことを可能にした。
2. 量子的な健全性の証明: 著者らは、エンタングルメント状態にあるプロバーの不正確率を非局所的なCHSH$_{Q(2)}$ ゲームに関連付けることで、計算量的仮定に依存することなく、量子的な健全性の厳密な証明を提供した。
3. 実験的実現: 300メートルの分離距離においてプロトコルを実行することに成功し、要求される実行時間とランダムネスコストが、現実世界の展開において実現可能であることを示した。

結果

• ラウンド複雑性: プロトコルは、健全性誤差 $e^{-k}$ を達成するために $m = 2k|E|$ ラウンドを必要とする。実験パラメータ（$|E|=1097, k=100$）の場合、約 $2.2 \times 10^5$ ラウンドとなった。
• 実行時間: 実験全体は 0.22秒 で完了した。対照的に、以前の量子的な健全性を備えた対称プロトコル [23] では、同じグラフに対して同じセキュリティレベルを達成するために、約 6.72万年 を要していた。
• ランダムネスコスト: 実験における総ランダムネスコストは 430.81 MB であった。対称プロトコル [23] では、同じタスクに対して約 5.92 $\times 10^9$ GB （5.92エクサバイト）が必要であった。
• セキュリティ: 時間差 $|t_1 - t_4|$ および $|t_2 - t_3|$ は、GPS同期誤差を考慮しても、一貫して1000 nsの閾値を下回る値として測定され、相対論的な信号非伝達制約を満たした。

意義と主張

本論文は、本研究が、特殊相対性理論と量子理論を統合することで、量子攻撃に対して計算量的困難性に依存しない、トラストレスな暗号システムを構築できる強力な可能性を示していると主張している。

意義に関する主な主張は以下の通りである：

• 実用的な実現可能性: ラウンド複雑性を $O(|E|^4)$ から $O(|E|)$ へと削減したことは、RZKPを理論的な構成物から、ある程度の大きさのグラフを扱う実社会のシナリオにおいて、実用的に展開可能なテクノロジーへと変貌させた。
• 無条件のセキュリティ: プロトコルは、信号非伝達原理のみに基づいた量子的な健全性とゼロ知識特性を提供し、将来の量子コンピューティングの進展に対しても堅牢である。
• スケーラビリティの可能性: 非対称な性質により一方のプロバー・検証者ペア（$V_1-P_1$）への計算負荷が高くなるものの、著者らは、このトレードオフは実現可能な実行時間を達成するために必要であると主張している。彼らは、このプロトコルがスマートフォンなどの日常的なデバイス上で実装可能であることも示唆している。
• 将来の用途: 著者らは、ブロックチェーン、スマートコントラクト、匿名電子投票、オンラインオークションなどのプライバシーに敏感な領域における潜在的な用途を強調している。また、アイデンティティ検証のためのゼロ知識知識証明（ZKPoK）へとこの枠組みを拡張できる可能性についても述べている。

著者らは、光ファイバーネットワークにおける実用的な展開には、プロバーの正確な位置の検証や計算負荷の管理といった課題が依然として存在することを認め、今後の研究におけるオープンな問題として、スケーラビリティの課題に対して謙虚な姿勢を保っている。