何が変わったか

これまで暗号理論では、Goldwasser・Micali・Rackoff が 1985 年に提案したゼロ知識証明は対話的でなければ成立しないことが、Goldreich・Oren の 1994 年の定理で証明されていた。「証明者と検証者のやり取りなしに、命題が真であることだけを伝える」ような証明は数学的に不可能とされ、暗号研究者の多くは「諦めて他の道を探せ」と語っていた。

MIT 博士課程 (現在はプリンストン高等研究所) の Rahul Ilango 氏が IACR ePrint で公開した論文で、証明複雑性理論 (proof complexity, 命題を証明するのに必要な最短の証明長を扱う計算機科学のサブ分野) を用いて「実効ゼロ知識 (effective zero knowledge)」という新しい定義を導入し、非対話型でも本質的にゼロ知識として機能する証明を構築する手法が示された。UCLA の Amit Sahai 氏は「これは絶対に新しい方向性だ」と評している。

社会にどんな影響があるか

主たる影響として、「対話必須」という制約が外れることでブロックチェーンや電子投票、身元証明などゼロ知識証明を実装する全領域で設計の選択肢が大きく広がる。暗号通貨の zk-SNARK 系の非対話型構成は実装上の便宜で「対話を信頼できる第三者で吸収する」近似が使われてきたが、Ilango 氏のアプローチは数学的に純粋な非対話型ゼロ知識への新しい道筋を提供する。

副作用として、暗号研究と数学基礎論 (ゲーデル流の証明不可能性、論理学) の境界に新しい交流が生まれる。Johns Hopkins の Abhishek Jain 氏は「孤立した結果にはならない」「ドアの隙間が見えただけで人は十分に動く」と語り、他の暗号構成にも証明複雑性のアイデアが応用される展開を予測している。

ニュースの詳細

Ilango 氏のトリックは「証明したい命題に、ほぼ確実に真だが原理的に証明不可能 (証明が天文学的に長くなる) な追加仮定を組み込む」点にある。具体的には「この地図は 3 色塗り可能 (NP 問題の典型例) — ただし標準的な数学公理から矛盾を効率的に導く方法が存在しないと仮定する」という形に書き換える。この追加仮定はゲーデル型の証明不可能命題で、誰も真偽を確かに判定できない。結果として、検証者は「自分が居る世界 (公理が無矛盾なら従来通り) が、もし崩れた世界 (公理が矛盾している) ならシミュレータが存在しうる」という余地を排除できないため、Goldreich-Oren の不可能性結果 (シミュレータが存在しないことを必須要件とする) が形式的に回避される。Ilango 氏は IBM の Marco Carmosino 氏らと共に、証明複雑性が暗号構成にどこまで応用できるかを引き続き探索している。

キーワード解説

ゼロ知識証明 (zero-knowledge proof) とは、命題が真であることを相手に納得させる一方で、その理由 (具体的な解や秘密) は一切漏らさない暗号プロトコル。Goldwasser・Micali・Rackoff の 1985 年論文以降、認証・電子投票・プライバシー保護暗号通貨の中核技術。

ゲーデルの不完全性定理 とは、1931 年に Kurt Gödel が証明した二つの定理で、ペアノ算術以上の表現力を持つ無矛盾な公理系には「真であるが証明できない命題」が必ず存在する (第一定理)、そしてその公理系自身が無矛盾であることをその公理系内では証明できない (第二定理) ことを示す。Ilango 氏は第二定理の構造を暗号の安全性仮定として再活用した。

証明複雑性 (proof complexity) とは、ある命題を証明するのに必要な最短の証明長を研究する計算機科学の分野。「実用的に書き下せない長さの証明しか存在しない命題」は事実上の証明不可能と扱われ、暗号への応用余地が新しく見出されつつある。