Zero-Knowledge Proofs

秘密の乱数は教えないけど、自分を証明するための乱数を持っていることは信じてほしい。虫のいい話。でもこの虫のいい話が暗号数学で実現できてしまう。

封筒

僕が「ある秘密 $x$ を知っている」ことを君に証明したいとする。$x$ 自体は絶対に教えたくない。ここで封筒を持ち出そう。

$x$ を封筒に入れて封をする。君はその封筒を受け取って、封を開けずに「中身が条件を満たしているか」だけを検証できる。中身は見えていない。でも正しいことは確信できる。僕が本当に $x$ を知らなければこの封筒は作れない。

実際のZKPでは封筒の代わりにmod演算のトラップドア関数を使う。「封を開けずに中身を検証する」が一方向関数の性質で、「封筒を偽造できない」が計算量的困難性。暗号理論の定番の道具立て。

形式的には3つの性質を満たすプロトコルをゼロ知識証明と呼ぶ。完全性（正直者は必ず通る）、健全性（嘘つきはバレる）、ゼロ知識性（検証者は秘密そのものを一切学ばない）。3つ目がミソ。検証者が対話から得る「ビュー」が、証明者の助けなしにシミュレーション可能なら、検証者は新しい情報を得ていないと言える。

Fiat-Shamirの方式

1985年にGoldwasser, Micali, Rackoffが概念を出して、翌年Fiat-Shamirが実用的なプロトコルを作った。やってることは素因数分解の困難性を使った平方根パズル。

信頼できるセンターが2つの素数 $p, q$ を選んで $N = pq$ を公開する。$p, q$ 自体は秘密。$N$ から $p, q$ を逆算するのは計算量的に困難。RSAと同じ構造。

ユーザーAは公開ID $ID_A$ を登録する。センターは $p, q$ を知ってるから mod $N$ での平方根 $S_A = \sqrt{ID_A} \pmod{N}$ が計算できる。これがAの秘密鍵。$p, q$ を知らない人間にはこの計算が不可能。ここに全ての安全性がぶら下がっている。

具体例で追ってみる。$p = 13$, $q = 19$, $N = 247$。$ID_A = 101$ のとき $S_A = 71$。検算すると $71^2 = 5041 = 20 \times 247 + 101$。合ってる。

Aは乱数 $r = 50$ を選んで $y = 50^2 \equiv 30 \pmod{247}$ をBに送る。次に $z = S_A \cdot r = 71 \times 50 \equiv 92 \pmod{247}$ を送る。

Bは $v = 92^2 \equiv 66 \pmod{247}$ を計算して、$w = v / y = 66 \times 30^{-1} \equiv 66 \times 140 \equiv 101 \pmod{247}$ を得る。$w = 101 = ID_A$。認証成功。

なぜこうなるか。展開すれば一発。

$$w = \frac{z^2}{y} = \frac{(S_A \cdot r)^2}{r^2} = S_A^2 = ID_A$$

乱数 $r$ が分子と分母で消える。残るのは $S_A^2 = ID_A$ だけ。Bは $S_A$ を直接見ていない。$y$ は乱数の2乗だからランダム、$z$ も乱数で撹拌されてるからランダムに見える。Bはこのビューを $S_A$ なしで生成できる（適当な $z$ を選んで $y = z^2 / ID_A$ とすればいい）。シミュレーション可能。だからゼロ知識。

じゃあ攻撃者が $S_A$ を知らずになりすませるか？ $N = 247$ くらいなら全探索でいける。でも $N$ が100桁を超えたら無理。さらに実用プロトコルでは検証者がランダムなチャレンジビット $b \in \{0, 1\}$ を挟んで、なりすまし確率を $1/2$ に落とす。40ラウンド繰り返せば $1/2^{40} \approx 10^{-12}$。

非対話にする

Fiat-Shamirは対話的。AとBがリアルタイムにやり取りする。ブロックチェーンだとこれは困る。証明を一度生成したら誰でも検証できなきゃいけない。

Fiat-Shamir変換（プロトコルと名前が同じでややこしい）は、検証者のチャレンジをハッシュ関数で置き換える。$b = H(y \| \text{context})$。証明者は対話なしに証明を生成できる。ランダムオラクルモデルの下で安全。これで対話が不要になった。

Moneroとbulletproofs

ここから現代の話。Moneroが2018年に採用したBulletproofsは、送金額が非負であることを金額を明かさずに証明する。range proof。

なぜ金額の非負性を証明する必要があるか。暗号化された金額でトランザクションを作ると、金額が負じゃないことを保証しないと「-100 XMR送金」みたいなトリックでコインを無から生み出せてしまう。Bulletproofsはこの穴を塞ぐ。

やってることの直感はシンプル。値 $v$ が $[0, 2^n)$ の範囲にあることを証明したい。$v$ をビット分解して $v = \sum b_i \cdot 2^i$、各 $b_i$ が0か1であることを証明すれば、$v$ が範囲内だと保証される。素朴にやると $n$ 個のコミットメントが必要だけど、Bulletproofsは内積証明で $O(\log n)$ に圧縮する。

Pedersen commitment $C = g^v h^r$ の加法準同型性がカギ。$g, h$ は生成元、$r$ はブラインド因子。$v$ を明かさずにコミットメントだけで算術関係を検証できる。Trusted setupが不要で、証明サイズが対数的。Moneroはこれでトランザクションサイズを約80%削減した。

Moneroの匿名性は3層構造になっている。リング署名が送信者を匿名化して、ステルスアドレスが受信者を匿名化して、Bulletproofsが金額を秘匿する。全部合わせて初めて「誰が誰にいくら送ったか」が完全に隠れる。

zk-SNARKsとzk-STARKs

Zcashが2016年に採用したzk-SNARKsは、証明サイズが入力に依存せず数百バイトで一定、検証がミリ秒で終わる。ただしtrusted setupが必要で、セットアップの秘密パラメータが漏れたら偽造可能。儀式的に「パラメータを生成してから破棄する」のだけど、本当に破棄されたかは信じるしかない。

zk-STARKsはtrusted setupが不要。証明サイズは数十KBとデカいけど、量子計算機にも耐性がある。SNARKsは楕円曲線に依存してるから量子に弱い。StarkNetで使われている。

トレードオフは明確。SNARKsは証明が小さいけどセットアップが必要。STARKsはセットアップ不要だけど証明がデカい。Bulletproofsはセットアップ不要で証明も小さいけど検証が遅い。銀の弾丸はない。

面白さ

Goldwasser, Micali, Rackoffが1985年にこの概念を定式化したとき、40年後にブロックチェーンの匿名送金を支えることになるとは思ってなかったんじゃないかな。 素因数分解の困難性がRSAを支えて、離散対数が楕円曲線暗号を支えて、ゼロ知識証明がMoneroのプライバシーを支えている。純粋数学が何十年後に実用になる。暗号理論はそういう世界かもしれない。

---

参考文献

• Goldwasser, Micali & Rackoff (1985). "The Knowledge Complexity of Interactive Proof-Systems." STOC '85
• Fiat & Shamir (1986). "How to Prove Yourself." CRYPTO '86
• Bünz et al. (2018). "Bulletproofs: Short Proofs for Confidential Transactions and More." IEEE S&P
• Ben-Sasson et al. (2014). "Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture." USENIX Security
• Noether et al. (2016). "Ring Confidential Transactions." Ledger, 1, 1-18