LoginSignup
4

More than 1 year has passed since last update.

シュノア署名

Last updated at Posted at 2020-03-15

 使用される記号と意味

記号 意味
$G$ 集合
$g$ ジェネレーター
$q$ ジェネレーターの位数
$s$ 秘密鍵
$h$ 公開鍵 $\,h=g^s\,$
$H$ ハッシュ関数
$m$ メッセージ

シュノア証明

ゼロ知識証明を改良して、手順の繰り返しの必要をなくしたもの。

証明者が、ESDSAの秘密鍵を$\,s\,$を知っていることを、秘密鍵が検証者にもれない形で、検証者が確かめる。

  1. 証明者は、$Z_q\,$から$\,r\,$をランダムに選択し、$x = g^r$を計算して、検証者に送る。
  2. 検証者は、ゼロ知識証明とは違って$c\,$を$\,0, 1\,$からではなく、$Z_q\,$から選択して、証明者に送る。← ゼロ知識証明との違いはここだけ
  3. 証明者は、$y = r + sc \bmod q\,$を計算して検証者に送る。
  4. 検証者は、$g^y = xh^c\,$が成り立つかを調べる。

証明者が秘密鍵を知っていれば、
$$
y = r + sc\,,\;
g^y = g^{r+sc} = g^r g^{sc} = xh^c
$$

となるので、検証式(ステップ4)は成り立つ。
また、この手順では、検証者に秘密鍵は漏れない。

証明者が秘密鍵を知らない場合に、検証式が成り立つ確率は$\,1/q\,$なので、$\,q\,$を大きくすることで、その確率を無視できる程度に小さくできる。

シュノア証明の非対話化

検証者から証明者にランダムな数値を送るステップを省き、証明者が代わりにその数値を作成することで、対話的なやりとりをゼロにすることが出来る。

以下は、上の例を非対話化したもの。現実には、証明者がランダム数値の代わりに、$\,x\,$にハッシュ関数を適用した値が使われるので、その形で変えてある。

  1. 証明者は、$Z_q\,$から$\,r\,$をランダムに選択し、$x = g^r$を計算して、検証者に送る。
  2. 証明者は$\,c = H(x)\,$を計算して、検証者におくる。← 上の例との違いはここだけ
  3. 証明者は、$y = r + sc \bmod q\,$を計算して検証者に送る。
  4. 検証者は、$g^y = xh^c\,$が成り立つかを調べる。

 通信の効率化

上の手順では、証明者から検証者に$\,x, c, y\,$がバラバラに送られているが、一度に送っても問題ない。また、$\,x = g^y/h^c\,$なので、$\,x\,$を送らないことで、データー量を削減できる。

シュノア署名

非対話型のシュノア署名のハッシュ関数の入力にメッセージを含めると、デジタル署名として使うことが出来る。

  1. 証明者は、$Z_q\,$から$\,r\,$をランダムに選択し、$x = g^r$を計算する。
  2. 証明者は、$\,c = H(x || m)\,$を計算する。
  3. 証明者は、$y = r + sc \bmod q\,$を計算して、署名を$\,\sigma = (c, y)\,$とする。
  4. 証明者は、検証者に$\,(m, \sigma)\,$を送る。
  5. 検証者は、$\,x = g^y/h^c\,$を計算する。
  6. 検証者は、$\,c = H(x || m)\,$が成り立つかを調べる。成り立てば署名は正しい。

参考文献

暗号技術のすべて/IPUSIRON

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4