---
tags: 暗号理論
---

# ゼロ知識証明完全に理解(し|できなかっ)た

## あゔすと!!

自分がとある秘密(例えば難しい問題の解)を知っているとする。これを他者に知らせたい場合はどうすればよいだろうか?当然"ぼく答え知ってりゅ～"と吹聴するのは駄目な訳で、しっかりした形で答えを知っていることを"証明"しなくてはならない。
手っ取り早いのはその答えを相手に伝えて検証してもらうことだが、相手に答えを知らせずに答えを持っていることを証明したいケースが存在する。このように相手に秘密情報を与えずにそれを保持していることを示すことをゼロ知識証明という。

## 用語

* 証明者(Prover): その問題の答えを知っていることを示す側
* 検証者(Verifier): 証明者が答えを知っていることを検証する側

以下はゼロ知識証明のプロトコルの際に必要な3要件である。

* 安全性: 証明者が答えを知っていた場合に検証者は必ずそうだと判断できる
* 健全性: 証明者が答えを知らない場合に検証者は"高い確率"でそうだと判断できる
* ゼロ知識性: 検証者はどう頑張っても証明者から"証明者は知識を保有している"以外の情報を引き出せない

健全性の部分で"高い確率"と書いたが、これは非常に低い確率で証明者が答えを知らなくても検証者を騙すことが出来ることを意味している。

## 離散対数問題とゼロ知識証明

離散対数問題は解くのが難しいとされているがこれの解を秘密として知っていることを証明する方法が存在する。今回伝える秘密を $s$ として次のような問題を考える(ここで $y, g$ は整数で $p$ は素数)。

$$
y \equiv g^s \mod p
$$

なお、ここではPohlig-Hellmanのアルゴリズム等で簡単に解ける場合は考えず、この問題を解く難易度は高いものとする。
具体的には $p$ は安全素数とし、$g$ は $p$ の原始根とする。

### プロトコル

離散対数問題の計算困難性を利用したゼロ知識証明のプロトコルを紹介する。

ここではAliceを証明者、Bobを検証者とする。

まず、両者共に知っている情報(公開鍵)を生成する。
素数 $p$ と $g \in \mathbb{F}_p$ を用意し秘密 $s \in \mathbb{F}_p$ に対して $h \equiv g^s \bmod p$ を用意する。この内 $p, g, h$ は両者共に知っており(公開情報)、 $s$ はAliceのみが知っているものとする。

続いて検証段階に入る。
Aliceは $r \in \mathbb{F}_p$ を1つ選び $x \equiv g^r \mod p$ を用意してBobへ送信する。
Bobは $c \in \{0, 1\}$ を選んでAliceへ送信する。
Aliceは $y = r + sc$ をBobへ送信する。
Bobは送られてきた $y$ と先程生成した $c$ を利用して $g^y \equiv xh^c \mod p$ であることを確かめる。もし合同式が成り立てば受理とし、成り立たなければ拒否とする。

この一連の流れを事前に決めた回数だけ繰り返して全て受理された場合にAliceは正当な証明者としてBobに検証されたことになる。

#### 安全性の証明

安全性の証明は簡単に行える、Aliceが $s$ を知っていると仮定し、このプロトコル中の $c$ が $0,1$いずれの場合でも最終的にBobが受理することを示せば良い。
$c = 0$ の場合は $y = r$ となるので $g^y = g^r \equiv x h^0 = h \mod p$ であり、受理される。
$c = 1$ の場合は $y = r + s$ となるので $g^y = g^{r+s} = g^r g^{s} \equiv x h^1 \mod p$ であり、受理される。
よってどのような $c$ が来てもAliceが正当な証明者(秘密を知っている)であればBobはそれを受理することになる。

#### 健全性の証明

ここで秘密を知らない攻撃者がAliceになりすまして証明を試みたとする。Bobとは通常通りのプロトコルを行わなくてはならないので、Bobから送られてきた $c$ に対して適切な $y$ を返すことが出来れば証明が出来ることになる。
ここでAliceが送る $x$ の生成を攻撃者もプロトコル通りに行ったとする、つまり指数 $r$ を攻撃者は用意している。この時、Bobが $c = 0$ を返してきた場合はこの $r$ を用いて $y = r$ を返せばBobに受理される。一方で $c = 1$を返してきた場合には $y = r + sc$ の $s$を知らない為、拒否される。
では、 $x$ 生成を $c=1$ に対応するように改造する。 ランダムに指数 $r$ を選び、 $x \equiv \frac {g^r} h \mod p$ としてBobに送る。Bobがこの時 $c=1$ を攻撃者に返した場合、攻撃者は $y=r$ を返せば受理される( $\because xh^c = xh \equiv g^r \mod p$ )。しかしBobが $c=0$を返してきた場合、 $x \equiv g^{r-s} \mod p$ であることから受理されるためには $y = r-s$ を返さなくてはならないが、攻撃者は秘密を知らないため確実に受理される $y$ を返すことが出来ない。
したがって上記のような $c$ に $0,1$ のどちらかが来ることを予想してそれぞれに対応するような $x, y$を返すような攻撃ではBobの応答次第で拒否されてしまう。

ではこれより攻撃力の高いスキームを仮定する、つまり $c$ が送られてきた段階で適切な $y$ を返すことが出来るアルゴリズム(入力は $p, g, c$ , 出力は $y$ )を攻撃者が保有しているとする。
これに従えば $y_0$ を $c=0$ の時の応答、 $y_1$ を $c=1$ の時の応答とすれば $g^{y_0} \equiv x \mod p, g^{y_1} \equiv xh \mod p$ となる。後式を前式で割ると $g^{y_1-y_0} \equiv h \mod p$ となる、ここで攻撃者は秘密を知らないはずだが、 $h \equiv g^s \equiv g^{y_1 - y_0} \mod p$ という関係から $y_0 - y_1 \equiv s \mod p$ であり、攻撃者にも関わらず事前に秘密を知っていることになり矛盾する。
故にこのような都合の良い攻撃スキームは存在しない。

というわけで $c$ に何が来るかを予期してそれに対応する $x,y$ を返すのが最良の攻撃方法になるのだが、この場合攻撃が成功する確率は、全ての繰り返し中で $c$ の予測に成功する確率なので、繰り返しの回数を $n$ とおいて $\frac 1 {2^n}$ である。したがって十分に大きい $n$ を用意すれば攻撃は失敗する可能性が高くなる( $n=10$ とした程度でも攻撃が成功する確率は0.1%ほどになる)。したがって健全性が証明された。

#### ゼロ知識性の証明

Bobがこのプロトコル中で入手できる情報は $g, p, h, x, y$ である。この内 $s$ が絡むパラメータは $h, y$ であるのでここから $s$ を求められないことを示す。
まず離散対数問題の困難性から、 $h \equiv g^s \mod p$ だけでは当然求めることが出来ない。
更に $c=0$ の場合は $y = r$ であるため、そもそも $s$ の情報が含まれていないことから求めることが出来ない
$c = 1$ の場合は $y = r + s$ であるため、 $r$ を求めることが出来れば $s$ も求まることになる
しかし、 $x \equiv g^r \mod p$ であることから公開情報だけから $x$ を手に入れる為にはBobは離散対数問題を解かなくてはならない、これは困難であるという仮定に基づいたプロトコルであるため当然Bobは解けない、故に( $r$ の選択を間違えない限り)Bobは $r$ を知ることは出来ず、同時に $s$ も知ることが出来ないことが示される

#### 実装

* https://github.com/Xornet-Euphoria/zero-knowledge_proof

### Schnorrのプロトコル

上記のプロトコルは無事に動いているが検証者に高い精度で証明するのには何回も受理プロセスを繰り返す必要がある。これは効率が悪いので一度の対話で証明できる用に改造されたのがSchnorrのプロトコルである。

プロトコルは至って簡単で $c$ を $0,1$ の代わりに $c \in \mathbb{F}_p$としてしまうことである。この場合、攻撃者は上記のプロトコル同様に $c$ を予想するしか攻撃方法は無いが、当然その成功確率は $\frac 1 p$ になる。

## 非対話の証明

上記2つは対話型の証明(Aliceが値 $x$ を送りつける -> Bobがチャレンジ $c$ を送りつける -> Aliceがそれを元に値 $y$ を送りつける)である、これをAliceが一方的に証明を送りつける方式に変えたものが非対話の証明である。
Wikipediaによれば通常、非対話の証明をすることは作ることが出来ないとされているが、ランダムオラクルの存在を仮定する等特殊な状況下であれば非対話な証明を作ることができる。
Schnorrのプロトコルを非対話に改造する場合、チャレンジ $c$ をAliceが予想できない状況でAliceに与える必要がある、そこでランダム関数(現実ではハッシュ関数が主)を用いて自分でランダムなチャレンジを生成してBobに送りつけることで証明を行うというものがある

なお、Bobが最後に検証を行うことからそのまま署名へと転用することもできる、そうやって出来たのがSchnorr署名である

## Fiat-Shamirプロトコル

2つの素数積 $n = pq$ を法とし、 $n$ の素因数分解が難しい下で平方根を求めるのが難しいという問題を利用した証明プロトコル。1回の通信だけで高い確率で証明を行えるよう改良することもできるが、簡単のため1/2の確率で証明可能な方法を提示する。

### プロトコル

1. 公開鍵として2素数の積 $n = pq$ を用意する、これは簡単に素因数分解できないものとする。
2. 秘密 $s$ を $n$ より小さい正の整数から選択しその2乗 $v :\equiv s^2 \mod n$ を公開鍵とする(当然だが $s^2 < n$ であると秘密が簡単にわかってしまう)。証明者は問題 $v \equiv s^2 \mod n$ の解、 $s$ を知っていることを証明する。
4. 証明者は $s$ と同様に $n$ 以下の正の整数 $r$ を選んでコミットメント $x :\equiv r^2 \mod n$ を検証者へ送る
5. 検証者は $0,1$ からランダムにビットを選択しチャレンジ $c$ として証明者へ送る
6. 証明者は $y \equiv rs^c \mod n$ を検証者へ送る
7. 検証者は $y^2 \equiv xv^c \mod n$ かどうかを検証し、そうなら正しい証明者とみなす

このプロトコルにおいて完全性は簡単に証明できる。証明者が送信した $y$ の値は $c$ 値に関わらず検証者にVerifyされる。
ゼロ知識性も示される、 検証者が $s$ の値を取得するのには $v$ から $s$ 直接求めるか $c=1$ を送信して得られた $y \equiv rs \mod n$ から $s \equiv \frac yr \mod n$ として $r$ を求める必要があるが、 $x \equiv r^2 \mod n$ より $r$ を求めるのにも $s$ を直接求めるのと同様の問題を解かなくてはならない。これは難しいという仮定があるので検証者は $s$ の値を求めることは出来ない。
健全性も離散対数問題の時同様に証明を偽装する攻撃者がチャレンジを予測する場合は高い確率で1回以上失敗することから示される。

## ΣプロトコルとFS変換

※勉強中
コミットメント, チャレンジ, レスポンスの3つからなるプロトコルの一般化とそれを署名へと変換する方法の事

## 参考文献

* 暗号技術のすべて - IPUSIRON
* https://ja.wikipedia.org/wiki/%E3%82%BC%E3%83%AD%E7%9F%A5%E8%AD%98%E8%A8%BC%E6%98%8E
* 暗号理論入門 - ブーフマン

## 次に読む

* [RFC8235](https://tools.ietf.org/html/rfc8235)
* https://techmedia-think.hatenablog.com/entry/2018/06/16/182735
* [Σプロトコル入門](http://lab.iisec.ac.jp/~arita/pdf/sigma.pdf)