零知识证明
大年初一学数学
阿里巴巴
零知识证明有一个经典的例子就是阿里巴巴与四十大盗。但是这个不是传统的《一千零一夜》里面的版本。
以下为 1989 的一篇美密的大致内容，标题为《How to Explain Zero-Knowledge Protocols to Your Children》
奇怪的洞穴
阿里巴巴每天都会去市场买东西，有一天被小偷偷了东西，他发现了然后去追，小偷进了一个洞穴就消失了。阿里巴巴进去发现有一个岔路口，沿左边的路口走到底，发现是死路。第二天还是这样，这次阿里巴巴选择了右边的路口，发现还是死路。
这时他觉得小偷一定都是选择了相反的通道，然后趁他进岔路后跑出来溜走了。
这样的事情持续了四十天，四十个大盗，阿里巴巴一个也没抓住。
这时阿里巴巴才发现事情不对劲，他在左边路口的尽头躲了起来，然后等到了一个小偷，小偷念动咒语“芝麻开门”，然后尽头的墙就打开了，小偷进去后门就关上了。被偷东西的人追到这里，只发现了阿里巴巴，很难受。
阿里巴巴后来研究了一阵子，成功把咒语改成新的了，然后记录了成了手稿。
手稿的命运
嫉妒的记者
另一家的记者找到 Mick Ali，想让他再拍一次，Mick Ali 说不行，已经跟一家签独家了。
但是 Mick Ali 调皮地（？）说你不知道秘密也可以拍，记者想了很久，终于搞懂了。
记者找了一个长得很像 Mick Ali 的人，让他也照着拍了一轮。由于冒牌货并不知道秘密，所以有一半的镜头都是失败的，记者就把这些镜头删掉，只留下成功的，最后凑够了四十轮。
两个视频同时播出，然后都被送上了法庭，但是法官和专家都没办法区分哪个是真的。
尾声
零知识证明的性质
完备性
如果你真的知道，一定是能证明的。
合理性
如果你不知道，那么证明的可能不大。
零知识性
实例
我觉得生活中有很多比较接近的例子，比如面试——你既需要向面试官证明你的能力，又不想他获得任何额外的信息，（防止他只是想从你这套方案之类的）
可能一开始接触 ZKP 会跟我一样迷糊，我现在的理解，大概就是 Schnorr 协议和 ZK 的关系 = RSA 和非对称加密的关系
Schnorr 协议
这是一个基于离散对数的交互式 ZKP，情景是 $P$ 需要向 $V$ 证明自己知道私钥 $x$，使得公钥 $y=g^x\pmod p$，其中 $g$ 是有限域循环群的生成元，阶为 $q$。
- $P$ 随机选一个数 $r \in \mathbb{Z}_q$，计算 $t=g^r\pmod p$，然后把 $t$ 发给 $V$
- $V$ 随机选一个数字 $c \in \mathbb{Z}_q$，发给 $P$
- $P$ 计算 $s=r+cx\pmod q$，然后把 $s$ 发给 $V$
- $V$ 验证 $g^s \equiv t\cdot y^c\pmod p$ 是否成立，成立就选择相信，反之则反之
先来看完备性，即知道了一定能证明：
$$
g^s \equiv g^{r+cx+nq} \equiv g^r (g^x)^c(g^q)^n \equiv t\cdot y^c \pmod p
$$
再看合理性，即不知道基本不可能证明：
逆推也十分自然，即需要找一个数 $s$，满足
$$
g^s \equiv t\cdot y^c \equiv g^rg^{cx} \equiv g^{r+cx} \pmod p
$$
那可不就是要找一个 $x$ 使得 $s=r+cx\pmod q$，容易看出，一个 $x$ 就对应一个 $s$，蒙对的概率就是 $1/q$，实际应用中 $q$ 往往是极大的，就算只选取 $2^{128}$ 次方的量级也基本没可能猜中。
最后看最重点的零知识性：
在说明这个协议为什么是零知识之前，我们先提出一个非零知识的证明，我相信这也是大多数读者会首先想到的一个证明流程：
假设在一个 RSA 协议中，公钥是 $(N, e)$，$P$ 需要向 $V$ 证明自己知道私钥 $d$
- $V$ 随机生成一个密文 $c$ 给 $P$
- $P$ 计算 $m\equiv c^d\pmod N$，然后发给 $V$
- $V$ 验证 $m^e \equiv c\pmod N$ 是否成立
合理性和完备性不再赘述，但是关于零知识性，我们可以很明显地发现，$V$ 可以利用这个协议来解密任何密文——只要他想，这是一个非常直观的感觉，下面我们可以进一步在定义上探讨他为什么不符合零知识性：
首先我们要明确一个基础的概念——这个知识是什么？
与生活中的知识不同，在密码学里，这个知识指的是“计算能力的提升”，泄露“知识”，即是使 $V$ 能计算出他原本无法计算出来的东西。
很显然，如果存在一个 $V$ 未知的消息 $m^*$，$V$ 得到了对应的密文 $c^*$，上面这个 RSA 的证明协议就可以使 $V$ 计算出他原本无法计算出来的 $m^*$，那么就发生了知识的泄露，也就不满足零知识性。
下面我们再来研究怎么比较严格地证明零知识性，这里需要引入一个全新的概念——模拟范式 (Simulation Paradigm)
假设在另一个平行时空里，同样存在一个 $P$，为了区别于现实世界的 $P$，我们可以把他记为 $P’$。
这两个世界别无二致——除了 $P’$ 拥有一个叫时光回溯的超能力。
那么以上面的 Schnorr 协议为例，借助这个神奇的外挂，$P’$ 完全可以在不知道私钥 $x$ 的情况下，完美伪造一份看似真实的交互记录：
- $P’$ 随便选一个 $t$ 发给 $V’$
- $V’$ 随机选一个数字 $c \in \mathbb{Z}_q$，发给 $P$
- $P’$ 发动技能，把时间调回到第一步，此时因为已经把 $c$ 骗到手了，所以他只需随便选一个 $s$，再计算 $t’\equiv g^sy^{-c}\pmod p$，在第一步把 $t’$ 发过去，然后在原本的这轮交互里把 $s$ 发过去
- 基于上一步的计算，$V’$ 验证 $g^s \equiv t’\cdot y^c\pmod p$ 自然成立，选择相信 $P’$
而对于上述的 RSA 证明来说，即便再怎么进行时光回溯，$P’$ 也无法在没有私钥的情况下把 $V’$ 给的密文解出来，所以不具有零知识性
// TO BE CONTINUED…
