Zero knowledge proof - Schnorr protocol

以另一 Discrete log problem 遮掩原有的 Discrete log

t

A --------------------> B

(t = g^r mod p) , r random

c (random)

A <-------------------- B

s
 A --------------------> B

s = r + cx mod q

A有自己的 x (原有的 DL problem)
之後新增一個 r (新 DL problem)

第1步是告訴B已經準備好一個 r (t)
第2步是告訴A 試這個 c
第3步則是說這個 s 能滿足你的c , 我的r (t) 及我隱藏的 x

其實這個和 Diffie-Hellman 有相似之處

ax是a的 private key x
B只知道 g^ax(不知ax), 之後準備一個 c
A 知道 ax, 之後也準備一個 r(t)

DH的合體Key就是 g^{(ax * c + r)} ... 雖然B不知道這是什麼 囧

在這protocol , A有 ax, r, c ...能造出全部東西
B除了 c之外什麼也沒有
但B能用 A 的 public 資料 (g^ax , t = g^r)和自己的 c作驗證
計出 g^s = ty^c

另一說法就是以 s ( r, c 及 x) 去隱藏/測試 x