Skip to content

Latest commit

 

History

History
86 lines (48 loc) · 6.52 KB

readme.md

File metadata and controls

86 lines (48 loc) · 6.52 KB
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: 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$ 的值。

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