什么是零知识证明 (Zero-knowledge proof)

A zero-knowledge proof (ZKP) is a technique that enables one party (the prover) to demonstrate to another party (the verifier) the truth of a certain statement without revealing any additional information besides the fact that the statement is true. The core idea behind zero-knowledge proofs is that while it’s straightforward to prove you have certain knowledge by disclosing it, the real challenge lies in proving you have that knowledge without actually revealing the knowledge itself or any details about it.

零知识证明（Zero-Knowledge Proof，简称ZKP）是一种技术，使一方（称为“证明者”）能够向另一方（称为“验证者”）证明某个陈述的真实性，同时不泄露除该陈述为真这一事实以外的任何其他信息。零知识证明的核心理念在于：尽管通过直接披露信息来证明自己拥有某种知识是较为直接的方式，但真正的挑战在于如何在不暴露该知识本身或其任何细节的前提下，仍能证明自己确实掌握了这项知识。

A ZK Protocol has 3 important attributes:

1. Zero-Knowledge: this means that no information about the secret is revealed during the process.
2. Completeness: meaning that an honest prover will always get accepted.
3. Soundness: for this, we want that an impersonator has only a small cheating probability to get accepted.

一个零知识协议具有三个重要属性：

1. 零知识性（Zero-Knowledge）：这意味着在整个过程中，不会泄露关于秘密的任何信息。
2. 完备性（Completeness）：这表示如果证明者是诚实的，其证明将总是被验证者接受。
3. 可靠性（Soundness）：指的是伪装者（冒充的证明者）被验证者接受的概率应该非常低。

例子：
你需要向你的一位色盲朋友维克多证明，两只形状完全相同的球（一只是红色，另一只是绿色）是不同的，但又不能透露哪只是红的、哪只是绿的。为此，你采用了一种特定的证明系统。

你先向维克多展示这两只球。他由于无法分辨颜色，看不出它们的区别。接着他将球藏起来，随机选出一只给你看，然后可能会将它换成另一只，也可能不换，再次展示给你。你需要判断他是否交换了球。由于你能通过颜色分辨球的不同，你每次都能准确判断他是否更换了球。

这个过程重复足够多的次数（例如50次），而你每次都能正确识别是否换了球，这让维克多确信两只球确实不同，但他依然无法得知哪只是红色，哪只是绿色。这个证明过程没有泄露除“这两只球不同”之外的任何信息，因此，这是一个零知识证明的例子。

Feige–Fiat–Shamir identification scheme

Uriel Feige, Amos Fiat 以及 Adi Shamir 于1988年提出了一种基于二次剩余问题的零知识证明协议（ZK Protocol）。

整体流程主要分为2个阶段：生成密钥以及验证。

1. 生成密钥（Key generation）：

Prover选择2个不同的质数$p,q$，一个正整数$k$，并且计算$n:= pq$。

挑选$k$个与$n$互质的数：$s_1,…,s_k$，并计算

$$v_i := s_i^{-2} \quad \text{ mod }n$$

公钥（Verifier已知的信息）为$P = (n,v_1,…,v_k)$，密钥为$S= (p,q,s_1,…,s_k)$。

2. 验证（Verification）：

(1) Prover随机挑选一个整数$c$以及一个符号$\sigma \in \{-1,1\}$，计算

$$x \equiv \sigma c^2 \quad \text{ mod }n$$

并将这个结果$x$发送给Verifier。

(2) Verifier挑选一个challenge $b = (b_1,…,b_k) \in \{0,1\}^k$，将其发送给prover。

(3) Prover计算

$$r \equiv c \prod_{j\in [k] \text{ s.t } b_j = 1} s_j \quad \text{ mod }n$$

并将$r$发送给verifier。

(4) Verifier检查是否满足

$$x \equiv \pm \, r^2 \prod_{j\in [k] \text{ s.t } b_j = 1} v_j \quad \text{ mod }n.$$

那么这个Protocol为什么是有效的？不难发现：

$$\pm \, r^2 \prod_{j\in [k] \text{ s.t } b_j = 1} v_j = \pm \, c^2 \prod_{j\in [k] \text{ s.t } b_j = 1} s_j^2 v_j \equiv \pm \, c^2 \equiv x \quad \text{ mod }n.$$

因为$s^2_j \equiv v_j^{-1} \text{ mod }n.$

而这个Protocol的安全性是建立在求解二次剩余的困难性上，即找到以下等式的解：

$$y ^2 \equiv v^{-1}_j \quad \text{ mod }n.$$