Skip to content

Latest commit

 

History

History
85 lines (47 loc) · 6.41 KB

readme.md

File metadata and controls

85 lines (47 loc) · 6.41 KB
Raw
title tags
Milestone 05. 初探零知识证明
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 除了知道命题为真和得到一堆随机数外，不会了解到任何其他信息。这个示例来自ZKP MOOC。

3.1 场景设置

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

3.2 交互式证明步骤

步骤 1： 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$ 无关。

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

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

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

不断重复上述步骤 1-4，直到 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$ 的值。

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