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

ゼロ知識証明

  • このエントリーをはてなブックマークに追加

概要

ゼロ知識証明 (ZKP; zero-knowledge proof) は、ある命題 (statement) が真であるという証明者 (prover) による主張を、それ以上の情報を明かすことなく検証者 (verifier) が確実に知る (受理する) ことのできるスキームである。以下の特性を持っている[2]。

  1. 完全性 (completeness). 証明者に対してある命題が真であれば、検証者は「証明者にとっては命題が真である」ことが確実に分かる。つまり実際には真であるにもかかわらず検証者が偽と認識することがない (false negative が起きない)。
  2. 健全性 (soundness). 証明者に対してある命題が偽であれば、検証者がそれを真であると誤謬することが現実的に困難である (false positive が起きない)。つまり悪意のある証明者が虚偽の証明を用いて偽の命題を真であると信じさせることができない。
  3. ゼロ知識 (zero-knowledge). 証明者に対してある命題が真であれば、検証者には「証明者にとっては命題が真である」こと以外に何の情報も明らかにならない。特に証明者の持つ証拠は検証者には明かされない。

ゼロ知識証明における健全性は、現実的に無視できる程度の非常に低い確率で証拠を偽造できる可能性を許している。つまり健全性を証明者が有限の計算能力を持つ場合に限定することができる。この適用は (無限の計算能力を持ってしても破られることがない) 数学的意味の証明系とは異なっていることから、そのような健全性を計算量的健全性と呼び、計算量的健全性に基づく証明系を証明 (proof) ではなくアーギュメント (argument) と呼んで区別している。

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

Table of Contents

  1. 概要
  2. シュノアプロトコル
  3. 用語
    1. -
      1. -
        1. 共通参照情報 (CSR; common reference string)
        2. アーギュメント (argument)
        3. 簡潔な証明 (succinct proof)
        4. 知識, 証拠 (witness)
        5. コミットメント (commitment)
  4. 参考文献

ゼロ知識証明は以下の手順で行われる。

  1. 設定: 証明者 \(P\) と検証者 \(V\) はある命題と、それを証明するためのゼロ知識証明プロトコルについて合意しているものとする。またその命題の証明に必要な証明生成鍵 \(P_k\) と検証に必要な証明検証鍵 \(V_k\) をそれぞれが保管している。
  2. 証明: 証明者 \(P\) は証明生成鍵 \(P_k\) を用いて命題のインスタンス \(\alpha\) とそれが正しいことの証拠 \(w\) から証明 \(\pi\) を生成し検証者 \(V\) に送信する。このとき、証明 \(\pi\) を生成するために検証者 \(V\) とのやり取りが発生する方法を対話型 (interactive) と呼び、やり取りすることなく証明 \(\pi\) を一方的に送りつけるだけで完了する方法を非対話型 (non-interactive) と呼ぶ。
  3. 検証: 検証者 \(V\) は証明検証鍵 \(V_k\) を用いて証明 \(\pi\) から命題のインスタンス \(\alpha\) が正しいかどうかを検証する。証明者 \(P\) が証拠 \(w\) を知っている場合、検証は成功し検証者は命題が真であることを受理する。

ある数 \(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 はこの命題を受け入れる。

シュノアプロトコル

シュノアプロトコル (Schnorr protocol)冪余剰による離散対数問題の困難性を用いた対話型ゼロ知識証明の手法である。

命題
証明者 \(P\) は \(y = g^x \bmod p\) となるような証拠 \(x\) を知っている。
設定
証明者 \(P\) と検証者 \(V\) の間で命題のインスタンス \(\alpha=(g, p, q, y)\) が共有されているものとする (シュノアプロトコルでは証明生成鍵 \(P_k\) も証明検証鍵 \(V_k\) も \(\alpha\) に含まれて共有されているとみなす)。ここで \(g\) を生成元、\(p\) を素数位数とする。
証明
  1. 証明者 \(P\) は \(r \in \{0,\ldots,q-1\}\) をランダムに選択してコミットメント \(c = g^r \bmod p\) を算出し検証者 \(V\) に送信する。
  2. 検証者 \(V\) は \(e \in \{0,\ldots,q-1\}\) をランダムに選択して証明者 \(P\) に送信する。
  3. 証明者 \(P\) は \(z = r + ex \bmod q\) を算出して検証者 \(V\) に送信する。
検証
\(g^z \equiv g^{r+ex} \equiv g^r \cdot (g^x)^e \equiv c y^e \pmod{p}\) より、検証者 \(V\) は式 (\(\ref{schnorr_verify}\)) が成り立てば証明者 \(P\) が証拠 \(x\) を知っていることを受理する。\[ \begin{equation} g^z \equiv c y^e \pmod p \label{schnorr_verify} \end{equation} \]

このシュノアプロセスが以下のような考えでゼロ知識証明の要件を満たしている。

  • 完全性: 証明プロセスが正しければ検証プロセスの式 (\(\ref{schnorr_verify}\)) が成立し検証者 \(V\) は命題を受理することができる。
  • 健全性: 証拠 \(x\) を持たない虚偽の証明者 \(P\) が検証プロセスの式 (\(\ref{schnorr_verify}\)) を成立させるためには、検証者 \(V\) が決定する任意の \(e\) に対して式 (\(\ref{schnorr_verify}\)) を満たす \(z\) を求めることができるようなコミットメント \(c\) を証明者 \(P\) が先に提出しなければならない。証明者 \(P\) が \(e_1\), \(e_2\) に対して \(g^{z_1} \equiv cy^{e_1} \pmod p\)、\(g^{z_2} \equiv cy^{e_2} \pmod p\) となるような \(z_1\), \(z_2\) を算出できるとすると、この 2 つの式を除算して \[ \begin{eqnarray*} g^{z_1-z_2} & \equiv & y^{e_1-e_2} \pmod p \\ g^\frac{z_1-z_2}{e_1-e_2} & \equiv & g^x \equiv y \pmod p \end{eqnarray*} \] を算出可能ということになり、つまり証明者 \(P\) は \(x\) を算出可能である (知っている) ことを意味している。
  • ゼロ知識: 証明者 \(P\) と検証者 \(V\) の間で交換される情報は \(c\), \(e\), \(z\) である。ここで、検証者 \(V\) は証明者 \(P\) から \(c\), \(z\) を受信しなくても、\(z\) を \(\{0,\ldots,p-1\}\) で一様な乱数、\(c \equiv g^z y^{-e} \pmod p\) とすることで同じ分布となる \(c\), \(e\), \(z\) の組み合わせを生成することができる。つまり \(c\), \(e\), \(z\) の情報は証拠 \(x\) がどのような値であろうが取りうる分布は変わらず、したがって \(P\) と \(V\) との間でやり取りされている情報は \(y=g^x \bmod p\) 以外に含まれていないと言える。

用語

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

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

  • アーギュメント (argument)

    計算量的健全性に基づく証明系。つまり、ある種の計算困難性仮定が満たされている場合にのみ成立する証明のこと。計算能力が限られていれば命題に受理されるような間違った証明を作成することができない。これに対して攻撃者が無限の計算能力を持っていたとしてもそのような証明を作成できないことを完全健全性と呼ぶ。

  • 簡潔な証明 (succinct proof)

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

  • 知識, 証拠 (witness)
  • コミットメント (commitment)

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

参考文献

  1. 岡本龍明, "現代暗号の誕生と発展", 近代科学社 (2019)
  2. Shafi Goldwasser, Silvio Micali, and Charles Rackoff (1989) The knowledge complexity of interactive proofs
F