一文了解首个零知识证明协议「二次剩余」

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

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

人类对很多概念的认识是漫长的、不断更新且曲折的。即使今天很多人看了零知识证明的定义，还是会一头雾水。不用担心，提出这个概念的图灵奖级别论文《交互证明系统的知识复杂度》(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 说，有两个公式 :

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

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

其中：

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

如何证明「零知识」

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

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

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(a, n)：

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

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

在更严格的证明过程中，还会引入一个辅助工具——混合模拟器 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

—-

编译者/作者：安比实验室SECBIT

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。