完整介绍了第一个零知识证明协议的背景知识、构造以及证明。

原文标题：《第一个零知识证明协议：二次剩余》
撰文：胡鹏，安比技术社区

人类对很多概念的认识是漫长的、不断更新且曲折的。即使今天很多人看了零知识证明的定义，还是会一头雾水。不用担心，提出这个概念的图灵奖级别论文《交互证明系统的知识复杂度》(GMR[85])，曾连续四次被业界顶级的计算理论研讨会 STOC 拒绝。看来不只是我们，那个时代最聪明的头脑们同样难以理解这篇极为重要的论文所蕴含的深刻意义。

在《不可思议的零知识证明》一文中，我们通过三个小故事介绍了零知识证明里面的重要概念：红绿色盲游戏（交互和随机性），阿里巴巴洞穴（模拟器），旅行中的数学家（非交互和公开验证）。但从直觉到严格的定义、证明之间，需要一些新的工具和方法论。这些由 GMR[85] 第一次给出，并且在之后得到广泛的研究和推广。第一个正式的零知识证明协议是二次剩余 (Quadratic Residue) 的判定，通过它，我们介绍零知识证明中的工具——计算不可区分(computationally indistinguable) 和模拟范式(simulation paradigm)，并且给出必要的证明。

背景知识

二次剩余是数论里面历史悠久的问题，起源于同余理论的研究。高斯在《算术研究》中，第一次系统的研究了剩余理论，总结了包括欧拉、费马、勒让德等前人的理论成果。

在自然数的领域里面，余数 (remainder) 和模数 (modulus) 指的都是公式 a = nq + r 中的 r；在高斯引入了同余符号≡后，则这个公式可以等价的写成 a ≡ r (mod n)。

定义：如果存在整数 x，使得 a ≡ x^k (mod n)，则 x 叫做 a 模 n 的 (k 次) 原根，其中当 k = 2 时，则称 a 是模 n 的二次剩余。

比如 12 ≡ 25 ≡ 5^2 (mod 13)。这种幂形式显然吸引了高斯的兴趣，在他的著作中研究了包括一次同余、二次同余以及高次同余等关系。在后面的文章后我们还将提到同余与群论的关系。

二次剩余问题，即给定互为质数的 a, n(否则，a ≡ 0 (mod n))，判断 a 是否是模 n 的二次剩余 (是否存在模平方根 x)。人们在寻找这个问题的算法时，发现它的难度等价于整数分解难题 (integer factoring)。当 n 是质数时，存在多项式时间算法，但 n 是合数时，则找不到多项式时间的算法。二次剩余问题是一个 NP 问题。

二次剩余问题的零知识证明协议

GMR[85] 利用二次剩余问题构造了第一个零知识证明协议，来解决以下问题：Alice 声称「a 是模 n 的二次剩余」，她可以直接展示模平方根 x(或者是 n 的因数分解)，但她不想泄漏除了「a 是模 n 的二次剩余」外的任何信息；Bob 一方面想着避免被 Alice 欺骗，另外一方面，可能也想尽办法想在和 Alice 的交流中获得「额外的信息」。

尽管上述采用了 Alice 和 Bob 这样的人格化比喻，但所有的计算机协议的执行者实际都是运行在计算机上的程序。在理论分析中，一般采用图灵机模型 (Turing Machine，TM)。也就是说 Alice，Bob 是两台 TM。其中 Alice 作为证明者 (prover) 被认为有无限计算资源，所以她能够计算出模平方根，或者说能够解答 NP 问题；Bob 作为验证者 (verifier)，受限于计算资源，无法破解出模平方根 x，否则他就能自己判断 Alice 的声称是否为真了。

Alice 对 Bob 说，有两个公式 :

1. s ≡ r^2 (mod n)
2. as ≡ (xr)^2 (mod n)

如果 s 和 as 都是模 n 的二次剩余，那么 a 也是模 n 的二次剩余。但我不会一次性全展示给你，我每次随机生成第一个公式，然后乘以 a 得到第二个公式，并且按照你抛硬币的结果随机展示其中一个：如果你抛到 0，我就给你公式 1 的模平方根 r；如果你抛到 1，我就给你公式 2 的模平方根 rx。下面是协议的示意图：

运行这个协议 m 次，如果 Alice 成功通过 check，则以 1-(1/2)^m 的概率说服 Bob。那么我们看下这个协议要满足的目的：

1. 如果 Alice 能计算出模平方根 x，则她能够完成任意次挑战；
2. 如果 Alice 不能计算出模平方根 x，则她无论采用什么策略，也会以极大概率被 Bob 拒绝；
3. 不管 Bob 采用什么策略，也无法从 Alice 这里得到「a 是模 n 的二次剩余「外的任何信息；

其中：

1. 显而易见，
2. 由于 Alice 不知道 Bob 会抛到什么结果，则她无法通过操纵第一步中的 s 来通过测试 (如果她知道是 0，则会生成 s ≡ r^2 (mod n)，如果她知道是 1，她可以通过生成 s ≡ r^2/a (mod n)，这样发送的 w 就是 r，也能通过检查)；
3. 直觉上来看，Bob 抛到 0，返回 r；抛到 1，返回 rx，Bob 无法从 s ≡ r^2 (mod n) 中计算出 r，无法获取 x。

分析 3 并不能叫人满意，因为按照定义，Bob 不仅不会得知 x，也不能获得除命题为真外的「任何「信息。如何证明一个协议真的做到了零知识泄漏呢？

如何证明「零知识」

Bob 作为验证者，在零知识证明协议运行过程中，能够「看到」的信息包括 Alice 发过来每条记录 (transcript) 以及自己的抛硬币结果 (local coins)，即 view = {tanscript, local coins}。如果存在某个计算资源和 Bob 一样的图灵机 S，能够独立的通过某个算法在概率多项式时间内模拟一个 view'，view 和 view'无法区分。那么 Bob 实际可以自己在家运行这个协议获得等价的信息，那么 Alice 在交互证明中除了说服 Bob 命题为真外，没有泄漏任何信息。

上面有两个概念需要严格的定义，「无法区分」和「模拟」：

• 「无法区分」是个日常表达，记住上面的 Alice, Bob, S 都是图灵机，它们并不关心对象间是否真的相同，只关心在计算模型和算法下能否观察到差别；即运行某个概率多项式时间的算法——叫做区分器 (Distinguisher)，对 view 和 view' 的分布判断的概率之差可以忽略不记，这种性质叫做「计算不可区分性」(computationally indistinguishable)：
  

  P 是 Prover(即 Alice)，V* 是所有的 Verifier(包括诚实和恶意的 Bob)，S 是 Simulator，D 是 Distinguisher，V*, S, D 都是概率多项式时间的图灵机，w 是 P 的私有信息 (或者说是 P 能够计算得到的，而 V 无法计算出来)，x 是共有输入 (a, n)，在这里即「a 是模 n 的二次剩余「这个命题，negl 表示差异可忽略不计的 (negligible)。

• 上面的「模拟器」S 最容易让人误解的地方在于，view 和 view' 计算不可区分，那么 Bob 岂不是也会被 S 说服？这种误解来源于把 S 看作是协议中 Alice 的角色，S 产生 view' 的过程并不是 Alice 和 Bob 按照零知识证明协议交互产生 view 的过程；S 是一个独立运行的程序，只要能证明它能够在概率多项式时间生成这个 view' 就可以了，无须和 Bob 交互。
   同样由于这个原因，Bob 只可能在和 Alice 交互过程中被说服，而产生的 view 无法再去说服另外一个 Bob'。即 Bob 对 Bob' 说：我确信 Alice 是知道模平方根 x，你看这是我们俩对话的 view。Bob‘无法对此采信，因为 Bob 可以通过模拟生成 view' 来糊弄他，他必须自己去和 Alice 进行交互证明才能被说服。这种局限导致零知识证明不具备公开验证(publicly verifiable) 的性质，这也说明一般意义上的数字签名（digital signature) 并不是 [完美的] 零知识证明，这在后面介绍非交互零知识证明 (NIZK) 再进一步讨论。

有个上面两个概念，我们可以来构造一个「模拟器」S(a, n)：

首先，这个程序存在概率多项式时间算法模拟随机变量的生成，包括抛硬币和生成 s；程序终止 (halt) 并打印结果的概率是 1/2，尽管可能存在循环但依旧可以在多项式时间内终止。综上，即 S(x) 可以在多项式时间内完成；

其次，要证明这个程序生成的视图{s, b , w}与零知识证明系统生成的视图计算不可区分：

1. s 和交互证明中的第一条消息都是随机生成的，不可区分；
2. b 和交互证明中 Bob 的抛硬币都是随机的，不可区分；
3. w 的构造方法保证了即使 S 并没有关于 x 的信息，w 在 Bob 看来是合法的，w 与交互证明中 Alice 的第三条信息不可区分；

在更严格的证明过程中，还会引入一个辅助工具——混合模拟器 S'(a, n, x)，它是一个计算能力与 Prover 相同，但执行路径与 S(a, n) 等价的程序，感兴趣的读者可以去查阅原始论文。顺序 (sequential) 重复上面的模拟器 m 次，则能够得到一组完整的 view'，可以证明以上性质仍旧适用 (即对 sequential composition 是闭合的)。

到目前为止，我们完整的介绍了第一个零知识证明协议的背景知识、构造以及证明，终于可以得到一个严格的定义：交互证明系统是零知识的，当且仅当存在概率多项式时间的模拟器 S，使得：

其中 x 是 P 要证明的命题，L 是某类命题的集合，z 是抛硬币的结果，w 是只有 P 拥有 (或能计算出) 的私有信息，V*指所有的验证者。无论 V 采用什么抛硬币策略 z 与 P 交互，S 都可以同样使用 z 来复现出来一个不可区分的版本。

看到这里的读者，相信你已经有了从数学上准确理解零知识证明的能力了，下一篇文章我们将讨论非交互和可公开验证的零知识证明协议 (NIZK)

参考

1. Shafi Goldwasser, Silvio Micali, Charles Rackoff: The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). STOC 1985: 291-304

来源链接：mp.weixin.qq.com