title: Milestone 05. 初探零知识证明
tags:
  - zk
  - basic
  - cryptography
  - quadratic residual​

WTF zk 教程 里程碑 05：初探零知识证明

这一讲，我们将初探零知识证明，介绍一个基于二次剩余问题的简单示例。我们会在后面的章节更系统的介绍它。

1. 背景介绍

零知识证明（Zero-Knowledge Proofs, zkp）最初由三位科学家 Goldwasser，Micali 和 Rackoff 在1985年的论文 "The Knowledge Complexity of Interactive Proof Systems" 中正式提出。这篇论文不仅首次引入了零知识证明的概念，还确立了交互式证明系统的知识复杂性框架。

零知识证明有三要素，可用于判断一个算法是否为零知识证明算法：

1. 完备性（Completeness）：如果陈述是真的，诚实的验证者将会被诚实的证明者说服。也就是“真的假不了”。
2. 可靠性（Soundness）：如果陈述是假的，不诚实的证明者无法说服诚实的验证者。也就是“假的真不了”。
3. 零知识（Zero-Knowledge）：如果陈述是真的，验证者除了陈述的真实性以外，不会了解到任何其他信息。

零知识证明的价值在于其强大的隐私保护功能，它能够确保个人或机构的敏感信息在验证过程中不被泄露。这一特性在安全协议设计、身份验证、区块链技术以及隐私保护等众多领域中都有广泛的应用。

2. 以二次剩余问题为例

二次剩余的问题： 给定 N =pq，其中 p 和 q 为大质数，在未知 p 和 q 的情况下，判断是否存在整数 x 使得 x^2 \equiv y \mod N （即 y 为二次剩余） 是困难的，难度不亚于大数的质数分解。而对于知道 p 和 q 的接收者，判断二次剩余问题是简单的，可以正确解码密文。

假设有这样一个场景，证明者 Alice 想向验证者 Bob 证明一个整数 y 为模 N 下的二次剩余。

最直接的方法就是将满足 x^2 \equiv y \mod N 的 x 发送给 Bob，然后 Bob 在收到 x 后验证 x^2 \equiv y \mod N 是否成立：若成立，则命题为真；否则命题为假。

这一证明方式满足完备性和可靠性，但不满足零知识，因为 Bob 除了知道命题为真之外，还知道了满足 x^2 \equiv y \mod N 的整数 x。那么我们如何在不透露 x 的情况下完成证明呢？这就用到了零知识证明。

3. 零知识证明示例

下面我们用一个示例来体会零知识证明的巧妙，在证明之后，Bob 除了知道命题为真和得到一堆随机数外，不会了解到任何其他信息。这个示例来自。

3.1 场景设置

假设 Alice 想向 Bob 证明他知道整数 y 是模 N 下的二次剩余，但不透露满足 x^2 \equiv y \mod N 的 x 的值。

3.2 交互式证明步骤

步骤 1： Bob 随机选择选择两个大素数p 和 q，计算N=pq，然后把N发送给Alice。

步骤 2： Alice 随机选择一个数 r，满足 1 \leq r \leq N 且 \text{gcd}(r, N) = 1（即 r 和 N 互质），然后计算 s = r^2 \mod N 并将 s 发送给 Bob。注意，这个 s 是由随机数 r 计算得到的，和 x 或 y 无关。

步骤 3： Bob 随机选择一个比特（布尔值） b，要么是 0，要么是 1，然后将 b 发给 Alice。

步骤 4： 如果 b = 0，Alice 发送 z = r 给 Bob；如果 b = 1，则发送 z = rx = r \sqrt{y} \mod N。

步骤 5： Bob 接收到 z 后，他验证 z^2 是否等于 s \cdot y^b \mod N。如果等式成立，Bob 在这次交互中接受证明。

不断重复上述步骤 2-5，直到 Bob 接受命题为真。

3.3 原理解析

这个例子属于交互式零知识证明，它是一种概率证明，即如果证明者是诚实的，那么在足够多的交互轮次后，验证者将以高概率被说服；即使证明者尝试欺骗验证者，由于随机性的引入，他们也只能以极低的概率成功欺骗。

下面，我们从零知识证明的三要素分析这个例子是否属于零知识证明。

1. 完备性： 若 Alice 知道满足 x^2 \equiv y \mod N 的 x 的值，那么他在每次的交互中都能正确的发送满足 z^2 = s y^b \mod N 的 z 值。如果验证者 Bob 是诚实的，那么它每一轮交互中都会接受命题为真，最终被说服。

2. 可靠性： 若 Alice 不知道满足 x^2 \equiv y \mod N 的 x 的值，那么她无法在 Bob 选择 b=1 时正确地计算出 z = rx \mod N。因此，如果她试图欺骗Bob，她必须猜测 b 的值。

   • 猜测 Bob 会选择 b = 0：那么 Alice 策略就是诚实的发送 s = r^2，再然后发送 z=r（对应 b = 0 的正确回应）。但如果 Bob 选择了 b=1，验证将会失败，因为 z^2 \neq s \cdot y \mod N。

   • 猜测 Bob 会选择 b = 1：那么 Alice 可以在第一步发送 s 的时候做手脚，不发送随机数 r 生成的 s，而是选择 s 使得 sy 成为二次剩余（比如 4）发送，然后再发送 z （比如 2）使得 z^2 = sy （对应 b = 1 的正确回应）。但如果 Bob 选择了 b=0，Alice 没法给出满足 z^2 = s 的 z，同样会导致验证失败。

   因此，Alice在不知道 x 的情况下，每轮只有 \frac{1}{2} 的概率能成功让Bob接受证明。经过足够多轮交互后，Alice成功说服Bob的概率会非常低，接近于 (\frac{1}{2})^k，其中 k 是交互轮数。这确保了证明的可靠性。

3. 零知识： 通过这种方法，Bob 能够验证 y 是二次剩余，但无法了解到 x 具体是多少。即使交互多次，由于每次 Alice 都会随机选择一个新的 r，Bob 无法构造出 x，得到的仅是一串随机数。

因此，这个示例中的算法满足三要素，是零知识证明。大家可以体会下零知识证明这种“我知道正确答案，不过我不告诉你正确答案，但是我可以证明当我想给你正确答案的时候，我的确做得到”的装逼感。

4. 总结

这一讲，我们简单介绍了零知识证明的三要素，并举了一个基于二次剩余问题的简单示例。在这个示例中，Alice 交互式的向 Bob 证明了 y 是模 n 下的二次剩余这一命题，并且不透露满足 x^2 \equiv y \mod N 的 x 的值。

零知识证明是一个很复杂但很有意思的学科，我们会在之后的教程中慢慢领略它的魅力。