使用される記号と意味
| 記号 | 意味 |
|---|---|
| $G$ | 集合 |
| $g$ | ジェネレーター |
| $q$ | ジェネレーターの位数 |
| $s$ | 秘密鍵 |
| $h$ | 公開鍵 $\,h=g^s\,$ |
| $H$ | ハッシュ関数 |
| $m$ | メッセージ |
シュノア証明
ゼロ知識証明を改良して、手順の繰り返しの必要をなくしたもの。
例
証明者が、ESDSAの秘密鍵を$\,s\,$を知っていることを、秘密鍵が検証者にもれない形で、検証者が確かめる。
- 証明者は、$Z_q\,$から$\,r\,$をランダムに選択し、$x = g^r$を計算して、検証者に送る。
- 検証者は、ゼロ知識証明とは違って$c\,$を$\,0, 1\,$からではなく、$Z_q\,$から選択して、証明者に送る。← ゼロ知識証明との違いはここだけ
- 証明者は、$y = r + sc \bmod q\,$を計算して検証者に送る。
- 検証者は、$g^y = xh^c\,$が成り立つかを調べる。
証明者が秘密鍵を知っていれば、
$$
y = r + sc\,,\;
g^y = g^{r+sc} = g^r g^{sc} = xh^c
$$
となるので、検証式（ステップ４）は成り立つ。
また、この手順では、検証者に秘密鍵は漏れない。
証明者が秘密鍵を知らない場合に、検証式が成り立つ確率は$\,1/q\,$なので、$\,q\,$を大きくすることで、その確率を無視できる程度に小さくできる。
シュノア証明の非対話化
検証者から証明者にランダムな数値を送るステップを省き、証明者が代わりにその数値を作成することで、対話的なやりとりをゼロにすることが出来る。
以下は、上の例を非対話化したもの。現実には、証明者がランダム数値の代わりに、$\,x\,$にハッシュ関数を適用した値が使われるので、その形で変えてある。
- 証明者は、$Z_q\,$から$\,r\,$をランダムに選択し、$x = g^r$を計算して、検証者に送る。
- 証明者は$\,c = H(x)\,$を計算して、検証者におくる。← 上の例との違いはここだけ
- 証明者は、$y = r + sc \bmod q\,$を計算して検証者に送る。
- 検証者は、$g^y = xh^c\,$が成り立つかを調べる。
通信の効率化
上の手順では、証明者から検証者に$\,x, c, y\,$がバラバラに送られているが、一度に送っても問題ない。また、$\,x = g^y/h^c\,$なので、$\,x\,$を送らないことで、データー量を削減できる。
シュノア署名
非対話型のシュノア署名のハッシュ関数の入力にメッセージを含めると、デジタル署名として使うことが出来る。
- 証明者は、$Z_q\,$から$\,r\,$をランダムに選択し、$x = g^r$を計算する。
- 証明者は、$\,c = H(x || m)\,$を計算する。
- 証明者は、$y = r + sc \bmod q\,$を計算して、署名を$\,\sigma = (c, y)\,$とする。
- 証明者は、検証者に$\,(m, \sigma)\,$を送る。
- 検証者は、$\,x = g^y/h^c\,$を計算する。
- 検証者は、$\,c = H(x || m)\,$が成り立つかを調べる。成り立てば署名は正しい。
参考文献
暗号技術のすべて/IPUSIRON