什么是零知识证明

来源：密码学引论 / zero_knowledge_proof/什么是零知识证明.md

零知识证明

密码学中，零知识证明是一方（证明者）向另一方（检验者）证明某命题的方法，

特点是过程中除“该命题为真”之事外，不泄露任何信息。

因此，可理解成“零泄密证明”。 例如，欲向人证明自己拥有某情报，则直接公开该情报即可，但如此则会将该细节亦一并泄露；零知识证明的精粹在于，如何证明自己拥有该情报而不必透露情报内容。这也是零知识证明的难点

阿里巴巴洞穴的故事

应用

• 身份认证
• zcash
• 索尼相机，在相机里面加上数字签名，第三方可以确认这个图片确实是由索尼相机拍摄的

交互式证明系统

语言：集合L

L中的元素是\(\{0,1\}^{*}\)的一个子集

A说服B相信某个元素\(x \in L\)

满足两个条件

1. 完备性：对于充分长的\(x\in L\),将\(x\)作为\((A,B)\)的输入，且A与B能够遵照协议运行，B接受对\(x\in L\)的证明
2. 合理性(soundness)：对于充分长的\(x\notin L\),对任意的交互图灵机A',将x作为\((A',B)\)的输入，B至多以可忽略的概率接受\(x\in L\)的证明

交互图灵机

E.g

A向B证明\((n,y)\in QNR\),

B随机选择一个整数\(i \in \{0,1\}\)和一个整数\(r\in Z_n^{*}\)

发送\(w = y^i r^2 \mod n\)

A收到之后，调用计算能力判断w是否是二次剩余，如果是，发送j=0，不是，就发送j=1

B检验是否\(i=j\)

Soundness

如果y是二次剩余的话，那即使A具有无穷的计算能力，也无法求出i，

因为w一定是二次剩余，A是无法分辨的

构造零知识证明

A向B证明\((n,y) \in QR\)

1. A随机选择一个元素r，计算\(w=r^2 \mod n\),并将w发给B
2. B随机选择\(i\in\{0,1\}\),并且发给A
3. A收到i之后，计算\(y^iw\)的一个随机平方根Z，并将Z发送给B
4. B收到Z之后，验证\(Z^2 \equiv y^iw \mod n\)

理论上来说B如果一直选i=1，就好像可以避免A的欺骗

但是此时A又可以预测B的输入，从而构造非法的w

比如选择w为二次非剩余，这样两个二次非剩余乘起来就是二次剩余

如何证明这个是零知识的？