はじめに

本記事では、ゼロ知識証明とは何かについて説明したのち、ゼロ知識証明プロトコルの一例として代表的なシュノアプロトコルを紹介し、ゼロ知識証明の応用例についても軽く紹介します。

ゼロ知識証明とは

ゼロ知識証明とは、一方の当事者がある主張を証明したいときに、他方の当事者に対して、その主張が正しいということ以外の情報を与えることなく証明することのできるやりとりの方法です。ゼロ知識対話証明とも呼ばれます。

ゼロ知識証明において、主張を証明する側の人のことを証明者（Prover）、証明を検証する側の人のことを検証者（Verifier）といいます。

ゼロ知識証明が満たす性質

ゼロ知識証明のプロトコルは、以下の3つの性質を持ちます。

完全性（Completeness） 証明者の主張が真であるならば、検証者はその主張が真であることが高い確率でわかる。
健全性（Soundness） 証明者の主張が偽であるならば、検証者はその主張が偽であることを高い確率で見抜くことができる。
ゼロ知識性（Zero-Knowledge） 証明者の主張が真であるならば、検証者は「主張が真である」こと以外には何の情報を得ることができない。

完全性と健全性は対話型証明が備えている性質であるため、ゼロ知識対話証明は、ゼロ知識性をもつ対話証明と考えることができます。

なお、特殊な条件下では対話が不要なゼロ知識証明を構成できることが知られており、そのようなゼロ知識証明は非対話ゼロ知識証明と呼ばれます。

知識のゼロ知識証明

ゼロ知識証明の手法によって示すことのできる主張にはいくつかの種類があります。そのうちの1つに、ある知識を持っているという主張を、その知識に関する情報を明かすことなく証明する知識のゼロ知識証明があります。ここでは、知識のゼロ知識証明の具体例であるシュノアプロトコルを紹介します。

ここでいう知識とは、主張が「問題 $X$ に対する答え $x$ を知っている」というものである場合の $x$ のことです。ただし、$x$ は一般に求めることが困難であり、$x$ が与えられれば現実的な計算時間で検証できるようなものです。

シュノアプロトコル

シュノアプロトコルとは、離散対数の知識（離散対数問題の解）のゼロ知識証明です。

離散対数問題

離散対数問題とは、素数 $p$ と2整数 $g,y$ に対して方程式 $g^x\equiv y\pmod p$ の解 $x$ を求める問題のことです。現在、この解 $x$ を効率的に求めるアルゴリズムは知られておらず、そのようなアルゴリズムが存在しないという仮定を離散対数仮定といいます。

この仮定の下では、十分大きな $p$ に対しては離散対数問題の解 $x$ の解を求めることは現実的ではないといえます。

離散対数問題について簡単に確認をしたので、離散対数の知識をゼロ知識で証明する手続きであるシュノアプロトコルを見てみましょう。

問題設定

証明者Pは、 $y\equiv g^x\pmod p$ を満たすような $x$ を知っているとし、 $x$ を検証者Vに明かすことなく示したいとします。

パラメータの共有情報

証明者Pと検証者Vの間で、パラメータの組 $(g,p,q,y)$ が共有されているとします。

ここで、 $q$ は $g^q\equiv 1\pmod p$ を満たす最小の正整数であるとします。

なお、離散対数問題に対する攻撃手法のことを考慮すると、 $q$ は素数である方が望ましいです。

プロトコルの流れ

証明者は、 $x$ を知らなければパスできないような以下のようなステップを踏むことで、検証者に $x$ を明かすことなく、 $x$ を知っていることを証明できます。

証明者Pのステップ (P1) 証明者Pは、乱数 $r\in\{0,\ldots,q-1\}$ を選んで $c=g^r\mod p$ を計算し、検証者Vに送信します。
検証者Vのステップ (V1) 検証者Vは、乱数 $e\in\{0,\ldots,q-1\}$ を選んで証明者Pに送信します。
証明者Pのステップ (P2) 証明者Pは、 $z=r+ex\mod q$ を計算し、検証者Vに送信します。
検証者Vのステップ (V2) 検証者Vは、 $g^z\equiv cy^e\pmod p$ が成り立つかどうかを検証し、成り立てば主張を受け入れ、成り立たなければ主張を受け入れないこととします。

ゼロ知識証明の性質を満たしていることの確認

上に示したプロトコルをゼロ知識証明の性質を満たしていることを確認してみます。

完全性 証明者Pが離散対数の知識 $x$ を用いて正しく $z$ を計算すれば $$ g^z\equiv g^{r+ex}\equiv g^r (g^x)^e\equiv cy^e\pmod p $$ が成り立ち、検証者Vは確率1で主張を受け入れます。
健全性 もし離散対数の知識 $x$ を知らない証明者Pに対して、証明者Vが主張を受け入れられるとすれば、ある同じ $c$ に対して、少なくとも2つの異なる $e$ について $g^z\equiv cy^e\pmod p$ を満たすような $z$ を返せなければなりません。ここで異なる $e$ と $z$ を $e_1,e_2$ と $z_1,z_2$ と表記することにします。このとき、 $$ g^{z_1}\equiv cy^{e_1},\,g^{z_2}\equiv cy^{e_2}\pmod p $$ となることから $$ g^{z_1-z_2}\equiv y^{e_1-e_2}\pmod p $$ が成り立ちます。ここで $$ \begin{split} \frac{z_1-z_2}{e_1-e_2}&=\frac{(r+e_1x)-(r+e_2x)}{e_1-e_2}\\ &=\frac{e_1x-e_2x}{e_1-e_2}\\ &=x \end{split} $$ が成り立つので $$ g^{\frac{z_1-z_2}{e_1-e_2}}\equiv g^x\equiv y\pmod p $$ が成り立ちますが、このことは証明者Pは離散対数の知識 $x=(z_1-z_2)/(e_1-e_2) \mod q$ を持つことを意味し、離散対数の知識 $x$ を知らないとしていた最初の仮定と矛盾します。したがって、証明者Pが離散対数の知識 $x$ を知らないならば、検証者Vはそのことを確率1で見抜くことができます。別の説明として、離散対数の知識 $x$ を知らない証明者Pに対して、 $g^z\equiv cy^e\pmod p$ が成り立つ確率は $1/q$ であることから、 $q$ が十分大きければ健全性が成り立つと言うこともできます。
ゼロ知識性 まず、離散対数仮定が成り立つ場合、検証者Vは共有パラメータから直接離散対数の知識 $x$ を計算することはできません。また、証明者Pと検証者Vの間で交換される情報は $c,e,z$ ですが、検証者Vは証明者Pから $c,z$ を受け取らずとも、離散対数の知識 $x$ を得た場合と同じ分布から $c,e,z$ を生成することができます。具体的には、 $z$ を $\{0,\ldots,q-1\}$ からの乱数とし、 $c=g^zy^{-e}\mod p$ によって定めると、証明者Vが証明者Pからプロトコルのやりとりで受け取る $c,z$ と比較して、それらを生成している分布の見分けがつかないものを生成できます。したがって、 $x$ を知っていても知らなくても、検証者Vが証明者Pからこのプロトコルで得る情報量は同じです。ただし、ここでの検証者Vは正直な検証者、すなわちプロトコルに従って乱数 $e$ を正しくランダムに生成しているとします。正直ではない、悪意のある検証者Vに対してゼロ知識性を示すことはできません。

シュノアプロトコルに対する攻撃手法

ここでは、上で示したシュノアプロトコルにおいて、証明者Pと検証者Vの間でやりとりされているパラメータ $(c,e,z)$ を第三者が盗聴可能であったとし、第三者が離散対数の知識 $x$ を復元することを考えます。

第三者がプロトコルの2回以上の盗聴を行い、ある2回で得られたパラメータ $(c,e,z)$ の組を $(c_1,e_1,z_1),(c_2,e_2,z_2)$ とします。このとき、乱数の質が悪かった等なんらかの理由により、 $c_1=c_2$ が成り立っていれば、これらを生成する際に使用した乱数 $r_1,r_2$ についても $r_1=r_2$ が成り立つので

$$ \begin{split} \frac{z_1-z_2}{e_1-e_2}&=\frac{(r_1+e_1x)-(r_2+e_2x)}{e_1-e_2}\\ &=\frac{e_1x-e_2x}{e_1-e_2}\\ &=x \end{split} $$

が成り立ち、離散対数の知識 $x$ を得ることができます。

$c_1=c_2$ が成り立つ場合でなくても、なんらかの方法で第三者が $g,p$ を知ったとすれば、以下のように離散対数の知識 $x$ を得ることができます。

第三者がプロトコルの2回以上の盗聴を行い、ある2回で得られたパラメータ $(c,e,z)$ の組を今回も $(c_1,e_1,z_1),(c_2,e_2,z_2)$ とします。ここで $c_1,c_2$ を生成する際に使用した乱数 $r_1,r_2$ とし、 $r_1\geq r_2$ が成り立っているとします。このとき、裏で $m=1,2,\ldots$ として $d_m=g^m\mod p$ を計算しておきます。ただし、必ずしも数列 $d_m$ のすべてが得られている必要はありません。もし、 $c_1\equiv c_2d_m\pmod p$ を満たすような最小の $m$ が見つかれば、これは $g^{r_1}\equiv g^{r_2}g^m\pmod p$ 、すなわち $r_1=r_2+m$ の関係がわかるので、このとき

$$ \begin{split} \frac{z_1-z_2-m}{e_1-e_2} &=\frac{(r_1+e_1x)-(r_2+e_2x)-m}{e_1-e_2}\\ &=\frac{\{r_1-(r_2+m)\}+(e_1x-e_2x)}{e_1-e_2}\\ &=x \end{split} $$

が成り立ち、離散対数の知識 $x$ を得ることができます。

ゼロ知識証明の応用例

ゼロ知識証明の技術は、認証、電子署名、公開鍵暗号、ブロックチェーンなど、多くの応用があります。

例えば、認証であれば、IDやパスワード等をなんらかの方法で数値化し、それを離散対数の知識 $x$ とみなせば、上記で示したシュノアプロトコルを利用することができます。ゼロ知識証明のプロトコルの健全性により、ユーザーは正しく入力を行わなければ正しさを証明できず、ゼロ知識性により個人情報そのものは漏れることがありません。

まとめ

ゼロ知識証明は、証明者がある主張を検証者に証明する際に、秘密情報を明かさずに証明する技術である
ゼロ知識証明は完全性、健全性、ゼロ知識性をの3つの性質を持つ
シュノアプロトコルは、離散対数の知識のゼロ知識証明である
ゼロ知識証明は認証、電子署名、公開鍵暗号、ブロックチェーン等多くの技術への応用がなされている

参考文献

[1] O. Goldreich, Foundations of Cryptography: Volume 1, Basic Tools, Cambridge University Press, 2008

[2] 有限責任監査法人トーマツ, ゼロ知識証明入門, 翔泳社, 2021

[3] 有田正剛, 知識の証明と暗号技術, 情報セキュリティ総合科学第1巻, 2009

[4] F. Hao, Ed., RFC 8235 Schnorr Non-interactive Zero-Knowledge Proof, 2017