第一个零知识证明协议：二次剩余

在《不可思议的零知识证明》一文中，我们通过三个小故事介绍了零知识证明里面的重要概念：红绿色盲游戏（交互和随机性），阿里巴巴洞穴（模拟器），旅行中的数学家（非交互和公开验证）。但从直觉到严格的定义、证明之间，需要一些新的工具和方法论。这些由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是闭合的)。

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

参考

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