シュノアプロトコルとは、離散対数問題を利用したゼロ知識証明です。 シュノアプロトコルを利用することで、証明者は離散対数問題の答えを知っていることを、検証者に対してゼロ知識証明で証明することができます。
前提
まず、証明者はパスワード $x$ を知っていることを証明する代わりに、証明者は離散対数問題 $y \equiv g^x \pmod p$ の答え $x$ を知っていることを証明します。
ゼロ知識証明のプロトコルは、「完全性」と「健全性」と「ゼロ知識性」の3つの性質を持ちます。
- 完全性（Completeness）とは、証明者の主張が真であるならば、検証者はその主張が真であることが高い確率でわかる性質です。
- 健全性（Soundness）とは、証明者の主張が偽であるならば、検証者はその主張が偽であることを高い確率で見抜くことができる性質です。
- ゼロ知識性（Zero-Knowledge）とは、証明者の主張が真であるならば、検証者は「主張が真である」こと以外には何の情報を得ることができない性質です。
プロトコルの流れ
- 事前準備
- 証明者と検証者は、証明に必要なパラメータの組 $(y, p, g, q)$ を事前に生成して、お互いに共有します。
- ここで、$y, p, g$ は整数で、$q$ は $g^q \equiv 1 \pmod p$ を満たす最小の自然数とします。
- 例えば、$g=7, p=13$ のときは $q=12$ となります。
- 完全性、健全性の付加
- (1) 証明者は、$0$ から $(q-1)$ の範囲で乱数 $r$ を選び、$c = g^r \mod p$ を計算して、検証者に $c$ を送信します。
- (2) 検証者は、$0$ から $(q-1)$ の範囲で乱数 $e$ を選んで、証明者に $e$ を送信します。
- ゼロ知識性の付加
- (3) 証明者は、真偽以外の情報が分からなくなるように次の計算で乱数を付与した値 $z$ を計算して、検証者に送信する。
- $z = r + ex \mod q$
- (3) 証明者は、真偽以外の情報が分からなくなるように次の計算で乱数を付与した値 $z$ を計算して、検証者に送信する。
- 検証プロセス
- (4) 検証者は、受信した $z$ を使って、$g^z \equiv c\,y^e \pmod p$ が成立しているかを確認する。
上記が成り立つことは、以下の式から確認することができます。
\[\begin{aligned} g^z &\equiv g^{r + ex} \pmod p \\ &\equiv g^r \cdot (g^x)^e \pmod p \\ &\equiv c \, y^e \pmod p \end{aligned}\]それぞれの性質について
- 完全性 : 検証プロセスにて、完全性が担保されます。
- 健全性 : 仮に知識 $x$ を知らない証明者が検証プロセスをパスするためには、$g^z \equiv c\,y^e \pmod p$ を満たすような $z$ を作る必要がありますが、$z$ は知識 $x$ を使って作られるため、離散対数問題の $g^x \equiv y \pmod p$ の形に帰着します。離散対数問題は解くのが困難なため、知識 $x$ を知らない人が検証をパスすることはできません。
- ゼロ知識性 : ゼロ知識性の付加にて、ランダムな値（ノイズ）を付与することで、ゼロ知識性が担保されます。
以上です。