暗号証明は、「存在しないシミュレータ」を証明しにくくすることで秘密を隠せる

秘密が隠れていることを証明するのが仕掛けではない

まず、ゼロ知識の最も単純な形から始めよう。

Aliceは、ある数独に解があるとBobへ納得させたい。解そのものを送ればBobは納得するが、パズルは台無しになる。Aliceが欲しいのはもっと奇妙なものだ。解を明かさずに、解が存在することだけを証明する。

それがゼロ知識証明の約束だ。証明者（prover、Alice）は、検証者（verifier、Bob）に対し、ある主張が真であることを納得させる。ただし、その主張が真であるという事実以上のものは何も明かさない。

問題は、この約束には代償があることだ。普通の数学的証明には、心地よい二つの特徴がある。一通のメッセージで済む。書いて渡し、その場を離れられる。そして**完全健全性（perfect soundness）**がある。偽の主張には、そもそも有効な証明が一つも存在しない。古典的な不可能性結果によれば、ゼロ知識はこの二つを諦めなければならない。しかも「二つを同時には持てない」だけではなく、それぞれ単独でも禁じられる。

第一に、ゼロ知識証明には対話が必要だ。事前に信頼できるセットアップを用意せず、Aliceが一通だけ送るなら、ゼロ知識保証は崩れる。代わりに健全性をどれだけ犠牲にしても、この点は変わらない。

第二に、ゼロ知識証明には、ごく小さな誤り許容が必要だ。完全健全性を要求すると、実は静かに対話まで壊してしまう。どんな乱数を選んでも絶対に騙されない検証者なら、その乱数を最初から固定しても同じだ。そして検証者の行動が予測可能になれば、Aliceはすべての返答を一通のメッセージへまとめられる。まさに、すでに壊れると分かっている場合へ戻ってしまう。

Rahul Ilangoの論文は、この二重の壁を回り込む方法についての研究だ。壁が存在しないふりをするのでも、不可能な条件下で古典的ゼロ知識を実現するのでもない。動きはもっと微妙だ。「何も明かさない」の意味を弱める。ただし、暗号研究者が実際にテストできるセキュリティ性質を保つ形で弱める。

その概念を**実効的ゼロ知識（effectively zero-knowledge）**と呼ぶ。

従来のテスト：シミュレータが存在する

ゼロ知識を古典的に形式化するとき、**シミュレータ（simulator）**という架空の助っ人を使う。

考え方はこうだ。Aliceの秘密を知らないJaneを想像する。もしJaneがAliceの秘密を一切知らないまま、BobがAliceから受け取ったものと見分けのつかない証明を自力で生成できるなら、Aliceの証明はBobに新しい情報を教えていない。Janeは秘密なしで、同じ体験を偽造できたのだから。

したがって古典的ゼロ知識は、本物のシミュレータを要求する。秘密――専門用語でいう証拠（witness）――を知らなくても、本物らしい証明を効率よく生成できるアルゴリズムが実際に存在しなければならない。数独なら、この証拠は単に完成した解答盤面だ。

この定義は強力だが、古い不可能性が噛み付く場所もまさにここである。直感はこうだ。本当に非対話型の証明は、ただの文字列になる。Bobがその文字列を受け取れば、他人にも見せられる。つまりBobは、主張を第三者へ証明する能力を得たことになる。それはすでに「何も得ていない」以上のものに聞こえる。古典的定理は、この直感を上の不可能性へ厳密化する。

メガ数独で感じる違い

違いを掴むため、意図的に単純化した例を使おう。

本気の比喩に普通の9×9数独を使ってはいけない。小さすぎ、有限すぎる。コンピュータなら解いてしまうか、解がないことを証明できる。代わりに、**MegaSudoku(n)**というパズル族を想像する。通常の規則を拡大する。ブロックサイズをnとし、N = n^2と置く。そしてN×Nの盤面をn×nのブロックへ分け、N種類の記号を使う。普通の数独は、ごく小さなn = 3、N = 9の場合――9×9盤面、3×3ブロック、9記号――にすぎない。証明複雑性の話が始まるのは、nを大きくでき、さらに盤面へ追加の「ガジェット」を組み込み、SAT式を数独の衣装で表せるようになってからだ。SAT式は、要するにyes/no制約のリストである。変数へ真／偽を割り当て、すべての制約を同時に満たせるか、という問題だ。

この「証拠」という考え方は、ここでも直感的に描ける。Aliceはメガ数独の完全に正しい完成盤面を知っている。Bobはそのような盤面が存在すると納得したいが、Aliceはそれを明かしたくない。完成盤面を丸ごと送ればBobは納得するが、秘密は失われる。

古典的ゼロ知識の版では、AliceとBobは対話する。昔ながらの直感モデルの一つでは、伏せたタイルを使う。Aliceは完成盤面を隠し、各ラウンドの前に記号を秘密裏に別名へ置換し、Bobにはランダムに選んだ局所制約一つ――行、列、ブロック、またはガジェット――だけを検査させる。開いたセルの記号がすべて異なれば、Bobの確信は増す。その後すべてを再び隠し、記号を新しく置換する。（一つ問題がある。元から印刷されたヒントも記号置換で隠れてしまうため、別の仕掛けが必要になる。下の注記で古典的プロトコルの処理法を説明する。ここから先の理解には、この単純化した絵で十分だ。）

これは論文そのもののプロトコルではない。古典的ゼロ知識を理解するための思考モデルだ。

• AliceとBobは往復する。
• Bobがランダムな検査を選ぶ。
• Aliceは局所的な整合性だけを明かし、完全な解は明かさない。
• プライバシーの証明は、Bobが見たものがAliceの秘密の解なしでも生成できた、と示すことで成り立つ。

したがって、古典的ゼロ知識は肯定的な事実を中心に立っている。

シミュレータが本当に存在する。

では、心地よい部分を取り去ろう。Aliceは一通の証明文字列を送り、その場を去る。信頼されたセットアップも、事前に用意された共有乱数列もなく、Bobは偽のパズルを絶対に受理してはならない。古典的ゼロ知識が生き残れない設定である。

仕掛けへ進む前に、もう一人だけ登場人物が必要だ。形式的証明体系を一つ固定する。直感のため、ここではこれを「ルールブック」と呼ぼう。固定された公理群と、書かれた数学的証明を機械的に検査する規則の集合である。数学の標準的公理系ZFCが典型例だ。ここから先のすべては、あらかじめ選んだ証明体系に対して述べられる。選択自体は柔軟で、ZFCを含め、どの証明体系を固定しても構成は働く。

（用語上の注意：論文でいう「proof system」は、ここで「ルールブック」と呼んでいる形式的証明体系を指し、Aliceが送る証明メッセージそのものではない。AliceとBob側の仕組みは、それぞれ**証明者（prover）と検証者（verifier）**と呼ばれる。）

Gödel風の版はメガ数独の物語を維持し、証明の作り方だけを変える。

同じ表示サイズの第二の制約系を選び、Dと呼ぼう。物語ではSとDは同じ形式の二つのMegaSudoku(n)である。裏側ではDは異なるサイズの難しい論理式から始まっていてもよく、必要なら無害なダミー制約を加えて同じ盤面サイズへ合わせられる。Dは、実際には**充足不能（unsatisfiable）**な論理式から作る。すべての制約を真にする値の割当は存在せず、壊れたパズルに合法的な完成盤面がないのと同じだ。おもちゃの例なら、「Xは真」と「Xは偽」を同時に要求する式である。したがってDには有効な完成形がない。

しかしDは、簡単に壊れていると暴けるパズルではいけない。今のおもちゃ例は失格だ。どんな証明体系でも「Xかつ¬X」のような矛盾なら一行で反証できる。Dは、偽でありながら、選んだ証明体系が短い議論ではその偽を証明できない形でなければならない。証明体系がDを短い証明で反証できれば、下の物語は崩れる。Aliceの秘密なしで証明を作れたかもしれない代替経路が形式的に排除され、それとともにプライバシー保証も消える。そこでDは、固定された証明体系が効率よく反証できない族から選ぶ。その証明体系の内部には、「Dに解はない」という短い証明が存在しない。

Aliceが一通で送る証明は、次の「どちらか」の主張についてになる。

本物のメガ数独Sに解がある、または、おとりDに解がある。

ここが論理的な接続点だ。Dは、魔法のようにSを真にするために生成されるのではない。証明は「Dに解がない、だからSに解がある」と論じているわけではない。SまたはDという選言そのものを証明する。完全健全性によれば、偽の選言には有効な証明は存在しない。現実にはDは偽――解なし――なので、選言が真になる唯一の方法はSが真であることだ。したがって証明が受理されれば、Sには必ず解がある。おとりDが、偽のSを真へ変えることはできない。

一方、ゼロ知識風の部分では、もしDに解があったら何が起きるかを考える。そのおとりの解が代わりの証拠として働き、Aliceの本物のメガ数独解を知らなくても証明を作れる。つまりシミュレータになる。現実にはDに解がないので、このシミュレーション経路は閉じている。重要なのは、証明体系が「閉じている」と効率よく証明できないことだ。

したがってDには二つの仕事がある。健全性についてはDが偽なので、「SまたはD」の有効な証明はSを強制する。実効的ゼロ知識についてはDの反証が難しいので、証明体系は「シミュレーションを可能にしたはずのおとり経路が閉じている」と素早く証明できない。

するとセキュリティテストは、もはや

シミュレータが本当に存在すると証明できるか？

ではなく、

あなたの証明体系は、シミュレータが不可能だと効率よく証明できるか？

になる。

答えが「できない」なら、驚くほど強いことが従う。（a）実際にテストを走らせれば観測でき、（b）シミュレータの存在から、その証明体系の内部で証明可能な形で導かれるセキュリティ保証は、どれも実際に成立する。もしそのいずれかへの攻撃が成功すれば、その成功自体が、存在しないはずの短い反証を与えることになる。しかしその短い反証は存在しない。ここが「実効的」ゼロ知識と呼ばれる理由だ。

教室的に対比するとこうなる。

古典的ゼロ知識： シミュレータが存在するから証明は安全である。

Gödel風の実効的ゼロ知識： シミュレータが不可能だと証明体系が効率よく証明できないので、観測可能なセキュリティテストについて証明は安全として振る舞う。

後者の主張は弱い。だからこそ、古典版では同時に保てなかった三つ――一通のメッセージ、セットアップなし、完全健全性――を維持できる。

新しいテスト：シミュレータが存在しないと証明できない

Ilangoの緩和は問いを変える。

古典的ゼロ知識はこう問う。

シミュレータは存在するか？

実効的ゼロ知識は、もっと弱いことを問う。

選んだ証明体系は、シミュレータが存在しないと効率よく証明できるか？

技術的な抜け道に聞こえるかもしれないが、ここが中心である。構成は奇妙な状態にある。シミュレータは実際には存在しない――論文は明記している――が、固定した証明体系は、その不在を効率よく証明できない。もし気にする悪い結果がすべて、そのような反証を必要とするなら、その結果についてシステムは依然としてゼロ知識のように振る舞う。

ここでGödelが入ってくる。飾りとしてでも、「Gödelが暗号を安全にする」という意味でもない。つながりは証明論的だ。証明体系は、厳密な意味で可能な限り「最良」であるとき**最適（optimal）**と呼ばれる。関連する種類の式について、どんな別の証明体系が短い証明で反証できるものでも、その最適な体系も高々多項式倍長い証明で反証できる、という意味だ。KrajíčekとPudlákは1989年に、最適証明体系は存在しないと予想した。どの証明体系を固定しても、ある真の主張の族について、別の証明体系ならはるかに短く証明できる。これは証明複雑性における中心的な未解決予想の一つであり、Gödelの不完全性定理の有限・計算量論的な親戚と見なせる。固定した証明体系には短い証明を持たない真の主張がある。ただし原理的に証明不能だからではなく、どの固定された証明体系にも「短い真理なのに短い証明がない」ものが残るからだ。

論文はこの予想を仮定する。暗号学でこの予想を使う際に標準的な、やや強い「無限回（infinitely often）」版である。Krajíček–Pudlákの定理による見返りは具体的だ。どの証明体系に対しても、本当に充足不能なのに、その証明体系では短く反証できず、しかも重要なことに、効率的なアルゴリズムで生成できる式の列が存在する。この最後の性質である**一様性（uniformity）**が、存在するだけの話をAliceが実際に走らせられるアルゴリズムへ変える。おとりDは空中から出てくるのではなく、組立ラインから出てくる。

暗号学上の動きは、この「証明能力の不足」をセキュリティへ使うことだ。

構成が実際にしていること

論文の構成を、形だけに削るとこうなる。

証明体系を一つ固定する。たとえばZFCだ。証明複雑性の仮定の下では、実際には充足不能だが、その証明体系には「充足不能である」という短い証明がなく、しかも効率的に生成できる式の列がある。

そこで、一通の証明を次の形にする。

本物の主張が充足可能である、または、この特別な難しい式が充足可能である。

特別な難しい式は、実際には充足不能だ。したがって基礎となる証明機構が完全健全なら、このメッセージを受理することは依然として本物の主張が真であることを意味する。これで完全健全性が得られる。

一方、ゼロ知識風の安全性については、この特別な難しい式がもし充足可能だったならと想像する。その証拠を使えば、本物の証拠を知らなくても証明をシミュレートできる。現実には充足不能だが、証明体系はその事実を効率よく証明できない。したがって「シミュレータは不可能だ」とも効率よく証明できない。

ここが蝶番だ。システムは古典的シミュレータを実際に作って秘密を隠すのではない。大きなクラスの観測可能なセキュリティテストに対し、シミュレータの不在を証明体系が証明できないことの陰に秘密を置く。

論文が主張していること

主定理は段階に分かれる。核心となる結果はこうだ。

標準的な暗号仮定――複数の確立した仮定群から得られる、よく研究された非対話型証拠識別不能証明（non-interactive witness-indistinguishable proofs）の存在――と、（無限回という意味で）最適証明体系は存在しないという証明複雑性の予想の下で、論文は、どの証明体系を選んでも、それに対して実効的ゼロ知識であり、完全健全性を持ち、セットアップを必要としない、NP/SAT用の、一通のメッセージだけで動く証明者・検証者の仕組みを構成する。（NP/SATはパズル的問題の標準的な「最難共通分母」で、メガ数独はその衣装の一つだ。）

さらに、反証可能なセキュリティ性質を広く維持するという主張には、標準的なもう一つの仮定、脱乱択化に関する信念P = BPP（大ざっぱに言えば、乱数はアルゴリズムへ本質的な追加能力を与えない）を加える。

定理の言葉をほどくと：

• 証明は一通のメッセージ。
• 信頼されたセットアップはない。
• 偽の主張を証明できない。
• 証明者は古典的な意味ではゼロ知識ではない――シミュレータが存在しない。
• しかし、古典的ゼロ知識から得られる反証可能な、ゲームベースのセキュリティ帰結を、この設定で一つずつ達成できる。

「反証可能（falsifiable）」が重要だ。セキュリティ失敗を、敵対者をゲームで走らせることでテストできるという意味である。暗号セキュリティ定義の多くはこの形をしている。敵対者は二つの暗号文を区別できるか、関数を逆算できるか、証拠を回収できるか、指定された実験に勝てるか。定理は、反証可能な性質ごとに、それを満たす証明者を与える。

一つの証明者がすべての反証可能な性質を同時に満たすのは、おそらく不可能だ。古くからの再利用攻撃――「Bobが証明を他人へ見せられる」――それ自体が反証可能な性質であり、ここでは本当に失敗する。論文は、一つの証明者で、暗号実務に現れるすべての*自然な（natural）*反証可能性質を覆える可能性を提案する。ただし、この部分は「natural」という非形式的概念と、明示された追加予想に依存する条件付き定理である。保証が狙うのは観測可能な失敗であって、秘密性について考え得るすべての哲学的、あるいはシミュレーションベースの意味ではない。

具体的な系として一つ名前を挙げる価値がある。この構成は、一様な証明者を持つ最初の非対話型証拠秘匿（witness hiding）証明を与える。「パズルの証明を見ても解を見つける助けにならない」を、対話なし、セットアップなしで実現する。控えめに聞こえる対象だが、何十年も構成できなかった。

この研究が言っていないこと

ここが記事を正直に保つ節だ。

古い不可能性定理が間違っていたとは言っていない。構成は定義を変えることでそれを回避する。

対話なし、セットアップなし、完全健全性を同時に持つ、普通の古典的ゼロ知識を与えたわけではない。論文は、構成された証明者にはシミュレータが存在しないと明記している。

証明を再利用できないという意味でもない。一通メッセージの証明は、依然として他人に見せられる。論文は否認可能性（deniability）のような性質を保たない。（信頼されたセットアップを使う非対話型ゼロ知識にも同じ制約がある。）

実運用へすぐ投入できる実践的プロトコルという意味でもない。これは計算量理論と暗号基礎論の研究だ。結果は証明複雑性と暗号学の大きな仮定に依存し、構成が示すのは原理的に何が可能かである。

「Gödel」が魔法のセキュリティプリミティブになったわけでもない。Gödelとのつながりは、証明体系、最適証明体系、不完全性の有限版を通している。有用な直感は「不完全性がパスワードを守る」ではない。「形式的証明体系がシミュレータの不可能性を効率よく証明できないなら、その証明を必要とする攻撃をセキュリティ定義のレベルで阻止できる」である。

それでも面白い理由

暗号学は、しばしば「難しさ」を安全性へ変換する。因数分解が難しいので、RSA型の仮定が役に立つ。格子問題が難しいので、格子暗号が役に立つ。ここでの難しさはもっと奇妙だ。「秘密を計算するのが難しい」ではなく、「ある証明オブジェクトが存在し得ないことを証明するのが難しい」。

そこがこの論文を変わったものにしている。公理や形式的証明体系を、ほとんど暗号資源のように扱う。通常の不可能性は、健全性とシミュレーションの間に緊張があると言う。Ilangoの動きは、その緊張を証明論的なカーテンの後ろへ置く。シミュレータは存在しないが、形式体系はその不在を効率よく暴けない。

読者にとって驚くべき点は、これが現在のゼロ知識システムを置き換えることではない。少なくとも直接には、おそらく置き換えない。驚きは、数理論理の限界を建設的に利用できることだ。壁としてだけでなく、一種の覆いとして使える。

証拠をどう評価するか

これは定理論文なので、「証拠」の意味は生物学や天文学の論文とは違う。実験が再現されたかを問うのではない。定義、仮定、証明の連鎖が主張を支えるかを問う。

証明は形式的で、論文は仮定を明示している。それらは軽い仮定ではない。非対話型証拠識別不能証明は暗号学で標準的に研究される対象で、複数の確立した仮定パッケージから導かれる。最適証明体系が存在しないという予想は、証明複雑性の中心的予想の一つだ。P = BPPは標準的な脱乱択化仮説で、より広い「反証可能性質」定理にだけ使われる。

さらに論文は、これらの仮定が任意に積み上げた足場ではなく、ほぼ必要な代償だと論じる。逆方向の結果を証明し、この種の構成が存在するなら非対話型証拠識別不能証明も存在しなければならず、さらに標準的な一方向関数を仮定すれば最適証明体系は存在できないことを示す。そして仮定には「win-win」の性質もある。どれかを反証できれば、それ自体が証明複雑性、暗号学、計算量理論における画期的発見になる。

ただし結果が条件付きなので、確信も条件付きだ。仮定が失敗すれば、定理の解釈は変わる。そして仮定が成立しても、保証は完全な古典的ゼロ知識ではなく、この論文の緩和された証明論的版である。

したがって適切な確信はこうだ。論文が整合的な条件付き可能性結果を確立していることへの確信は高い。その仮定が私たちの実際の暗号世界を記述していることには中程度。すぐに使える実践的帰結には低い。

なぜ重要なのか

閉じているはずだった経路を、論文は一つ開いた。

古典理論は言う。完全なゼロ知識は、セットアップなしの一通メッセージにはできず、完全健全にもできない。Ilangoの論文はこう言う。セキュリティゲームでテストできるゼロ知識の帰結を求め、さらにセキュリティ定義が「形式的証明体系が何を効率よく反証できるか、できないか」に依存することを許せば、有用な振る舞いのかなりの部分を、一通のメッセージ、セットアップなし、完全健全性とともに回収できる。

これは小さな定義変更ではない。暗号保証を考える別の方法だ。何が存在するかだけを問うのではなく、自分が採用した証明体系で何を排除できるかを問う。証明不能性を哲学的な厄介者として扱うのではなく、構造として利用する。

実務の世界は明日変わらないかもしれない。しかし概念地図は変わる。「秘密が漏れなかった」から欲しかった多くのゲームベース保護を、「秘密が漏れたと誰も効率よく証明できない」という条件で回収できる、という形式的な意味が生まれた。

だからGödelがタイトルに入る。

まとめ

ゼロ知識証明では、証明者が証拠（witness）を明かさずに、主張が真であることを検証者に納得させる。古典的不可能性結果によれば、ゼロ知識はセットアップなしで一通のメッセージへ圧縮できず、完全健全性も持てない。Rahul Ilangoの論文は、その不可能性を反証しない。代わりに、実効的ゼロ知識（effectively zero-knowledge）という弱い概念を定義する。シミュレータが本当に存在することを要求するのではなく、ZFCのような選んだ証明体系――形式的なルールブック――が「シミュレータは存在しない」と効率よく証明できないことを要求する。暗号学（非対話型証拠識別不能証明）と証明複雑性（最適証明体系は存在しない）に関する大きな仮定の下で、論文はNP/SATについて、セットアップなし、完全健全性を持つ一通のメッセージだけで動く証明者を構成し、古典的ゼロ知識の反証可能なゲームベースの帰結を性質ごとに実現する。すべての「自然な」性質を一つの証明者で覆う拡張は、さらに一部予想的であり、文字どおりすべての反証可能性質を覆うのはおそらく不可能だ。証明は依然として再利用できるからである。結果は理論的・条件付きで、配備可能な暗号プリミティブではないが、証明論的な証明不能性を暗号資源として使う新しい方法を示している。

冷静に見ると

論文が示したこと： 明示された仮定の下で、どの証明体系を選んでも、それに対して実効的ゼロ知識となり、古典的ゼロ知識の各反証可能なゲームベース帰結を達成する、一通のメッセージ、セットアップなし、完全健全性を備えたNP/SAT用の証明者を構成できる。

もっともらしいが、無条件には証明されていないこと： 必要な証明複雑性・暗号学上の仮定が成立すること。どれも真剣に研究されている仮定で、論文は十分条件だけでなく本質的に必要でもあることを示しているが、それでも仮定である。

示していないこと： 対話なし、セットアップなし、完全健全性を持つ古典的ゼロ知識。実運用できるシステム。証明の否認可能性や再利用不能性。あるいはGödelの不完全性定理そのものが暗号を安全にする、ということ。

主な限界： 保証はゼロ知識の緩和版である。最も広い版は複数の仮定に依存する。一つの万能な証明者に関する主張は一部予想的なまま。結果の中心は基礎理論である。

一般読者はどの程度信頼すべきか？ 定義を受け入れるなら、重要な条件付き理論結果であることへの確信は高い。仮定が現実を正しく捉えていることには中程度。すぐ実用化できるという確信は低い。安全な結論はこうだ。この論文はゼロ知識の不可能性を壊したのではない。多くのセキュリティゲームで重要な部分を、証明論的な別の方法で回り込んだ。