セキュリティ
\( \def\vector#1{\boldsymbol{#1}} \)

ゼロ知識証明

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

概要

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

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

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

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

共通参照情報 (CSR; common reference string) は信頼できる機関が正しく生成し公開している事前情報である。このような事前設定を認めると非対話型ゼロ知識証明が実現できる。

Table of Contents

  1. 概要
    1. コミットメント方式
  2. シュノアプロトコル
  3. 参考文献

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

  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\) を知っている場合、検証は成功し検証者は命題が真であることを受理する。

コミットメント方式

コミットメント (commitment) は証明プロトコルの開始時に証明者から検証者に送信される後で覆せない情報である。コミットメントを使用する証明スキームをコミットメント方式と呼ぶ。

例としてべき乗は容易だが平方根を求めることが極めて困難な世界を仮定する。証明者 A は、ある整数 \(y\) に対して \(y=x^2\) となるような整数 \(x\) を知っている、つまり整数 \(y\) が乗法演算において平方であるという命題が真であることを知っている。証明者 A が検証者 B にこの命題が真であることを確証させるには、証明者 A が証拠 \(x\) を明かすことなくその平方根 \(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 はこの命題を受け入れる。

この証明スキームにおいて、B は A から送信された \(a\) を受信したあとに \(b\) を送信しなければならないことに注意。これは \(x\) の知識を持たない A が \(b\) を確認してから \(c^2=y^b a\) となるような \(a\), \(c\) を見つけることが難しくないためである。したがって \(a\) はこのスキームでのコミットメントに相当する。

コミットメント方式のゼロ知識証明において行われる、チャレンジ-レスポンス方式の前段にコミットのフェーズが挿入されたこの対話手順を、その対話方向の形にちなんで Σ-プロトコル (sigma protocol) と呼ぶ。

Fig 1. \(\Sigma\)-protocol

シュノアプロトコル

シュノアプロトコル (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\) 以外に含まれていないと言える。

参考文献

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