零知识证明

https://www.bilibili.com/video/BV1Gb411R7dr/?spm_id_from=333.337.search-card.all.click&vd_source=1c8b4d276f629bbc2138253227fbb0a4

01 什么是零知识证明

什么是“零知识”
- 证明中信息的泄露：例如，n是否是合数
- 不泄露额外信息的证明
零知识证明
- 零知识证明允许一方（证明者）说服另一方（验证者）相信某个事实或声明，同时不泄露额外信息
  - Goldwasser, Micali与Rackoff提出（1980s）
  - 应用
    1. 身份识别协议
    2. 数字签名
    3. 加密
    4. 区块链隐私保护，zcash
How to Explain Zero-Knowledge Protocols to Your Children

交互式证明系统

交互图灵机（interactive Turing machine）
- 一条只读输入带，一条工作带，一条随机带，一条只读通信带，一条只写通信带
- 随机带：无限长随机比特序列（抛币）
交互协议（A，B）
语言：集合L
- L中的元素：x可编码成01串，长度|x|
  - L可看作集合{0，1}*一个子集
成员的交互证明系统

设L {0,1}* 是一个语言，（A,B）是一个交互协议。我们说（A,B）对L是一个成员的交互证明系统，如果它满足下列两个条件:

(1) 完备性：对每一个k > 0和充分长的x ∈L，将x 作为（A,B）的输入，B终止协议并至少以1-|x|^-k^的概率接收x。这里的概率是相对于协议（A,B）所有可能的掷硬币而言的。

(2)合理性：对每一个k >0和充分长的x L，对任意的交互图灵机A’，将x作为（A’,B）的输入，B至多以|x|^-k^的概率接收x。这里的概率是相对于协议（A’,B）所有可能的掷硬币而言的。

二次剩余：X^2^在数论中，特别在同余理论里，一个整数X对另一个整数p的二次剩余（英语：Quadratic residue）指X的平方除以p得到的余数。

当存在某个X，式子
$X^{2} \equiv d (mod p)$
成立时，称“d是模p的二次剩余”

当对任意不成立时，称“ d是模 p的二次非剩余”

但是这个过程并不是零知识证明系统，因为泄露了额外的信息，在这个条件下，B可以利用A来判断一个数是不是二次剩余。

第三步，如果A知道的话，那么y一定属于二次剩余集合里面的一个数，|就是y如果是一个二次剩余的话，因为w也是剩余，无论i取多少，无论i=1时的yw，还是i取0时的w，都一定能算出他的平方根。但如果y不是二次剩余，当i取1的时候，就算不出平方根了。所以在这种情况下，如果说每一次，每一轮他都能发过来一个，并且这个B收到了以后，他自己算一下，确实是这个的平方根，那么就接受A的证明。

如何证明零知识性

假设有个冒牌货，想冒充阿里巴巴，假设阿里巴巴洞穴出来的过程是一段录像，那么冒牌货虽然不知道协议（就是洞穴里的密码），但是他也有运气好的时候，有1/2的可能性能猜对，他可以通过剪辑的方法，把失败的剪辑去，生成一个和阿里巴巴相同的录像带，使得大家也以为他有。观众们看到这段视频和阿里巴巴的视频，并不能知道谁是真正知道咒语的阿里巴巴。这就能顾证明了阿里巴巴那个录像带并没有泄露任何知识。因为如果录像带泄露了知识，观众们就能够通过录像带里泄露的知识来区分谁是真正的阿里巴巴。