\( \def\vector#1{\boldsymbol{#1}} \)

ゼロ知識証明

Takami Torao #SNARG #SNARK #zk-SNARK #ゼロ知識証明
  • このエントリーをはてなブックマークに追加

通常の証明系では証明者が無限の計算能力を持ってしても間違った命題に対して受理されるような照明を作ることはできないが、この証明系では計算能力が限定された証明車に限って、間違った命題に対して受理されるような照明を作ることができない。これを計算量健全性と呼び、計算量的健全性を持つ証明系をアーギュメント (argument) と呼ぶ。

命題が正しいことを証明するのではなく、知識 (命題が正しいことを示す証拠) を知っていることを証明することを知識のアーギュメント (または知識の証明) と呼ぶ。簡潔で非対話型の知識のアーギュメント (succient non-interactive argument of knowledge)SNARK と呼び、さらに完全なゼロ知識の SNARK を zk-SNARK と呼ぶ。ここで簡潔 (succient) とは証明のサイズが証明したい命題のサイズに依存せず十分に短いことを意味する。

コミットメント (commitment)
送信者が受信者にコミット (預託)

ある数 \(y\) が乗法演算において平方、つまり \(y=x^2\) となるような \(x\) を A が知っていると仮定する。この命題に対して B に \(x\) を開示せずに A がその平方根 \(x\) を知っていると確証させるには:

  1. A: ランダムな数 \(r\) を選び B に \(a=r^2\) を送る。
  2. B: ランダムな数 \(b\) を選び A に送る。
  3. A: B に \(c=x^br\) を送る。
  4. B: \(c^2 = y^b a\) であれば合格。

これを \(n\) 回 (\(y\) のビット長) 繰り返して全てのラウンドで合格ならば検証者 B はこの命題を受け入れる。

用語

  • 共通参照情報 (CSR; common reference string)

    信頼できる機関が正しく生成し公開している事前情報。このような事前設定を認めると非対話型ゼロ知識証明が実現できる。

  • アーギュメント (argument)

    計算量的健全性を持つ証明系。計算量的健全性とは計算能力が限られていれば間違った命題に受理されるような証明を作成することができない。これに対して攻撃者が無限の計算能力を持っていたとしてもそのような証明を作成できないことを完全健全性と呼ぶ。

  • 簡潔な証明 (succinct proof)

    証明のサイズが短く、証明したい命題のサイズに依存しない特徴を持つ証明。Gennaro らによって簡潔な非対話型ゼロ知識証明が提案された。

参考文献

  1. 岡本龍明, "現代暗号の誕生と発展", 近代科学社 (2019)