Schnorr 协议充分利用了有限域和循环群之间单向映射,实现了最简单的零知识证明安全协议:Alice 向 Bob 证明她拥有
PK
复制代码
对应的私钥
sk
复制代码
。
第一步:为了保证零知识,Alice 需要先产生一个随机数,
r
复制代码
,这个随机数的用途是用来保护私钥无法被 Bob 抽取出来。这个随机数也需要映射到椭圆曲线群上,
rG
复制代码
。
第二步:Bob 要提供一个随机数进行挑战,我们把它称为
c
复制代码
。
第三步:Alice 根据挑战数计算
z = r + a * c
复制代码
,同时把
z
复制代码
发给 Bob,Bob通过下面的式子进行检验:z*G ?= R + c*PK = rG + c*(aG)
大家可以看到 Bob 在第三步「同态地」检验
z
复制代码
的计算过程。如果这个式子成立,那么就能证明 Alice 确实有私钥
a
复制代码
。
可是,这是为什么呢?
z
复制代码
的计算和验证过程很有趣,有几个关键技巧:
首先 Bob 必须给出一个「随机」挑战数,然后 Bob 在椭圆曲线上同态地检查
z
复制代码
。如果我们把挑战数
c
复制代码
看成是一个未知数,那么
r+a*c=z
复制代码
可以看成是一个一元一次方程,其中
r
复制代码
与
a
复制代码
是方程系数。请注意在
c
复制代码
未知的前提下,如果
r + a*x = r' + a'*x
复制代码
要成立,那么根据 Schwatz-Zippel 定理,极大概率上
r=r'
复制代码
,
a=a'
复制代码
都成立。也就是说, Alice 在
c
复制代码
未知的前提下,想找到另一对不同的
r'
复制代码
,
a'
复制代码
来计算
z
复制代码
骗过 Bob 是几乎不可能的。这个随机挑战数
c
复制代码
实现了
r
复制代码
和
a
复制代码
的限制。虽然 Bob 随机选了一个数,但是由于 Alice 事先不知道,所以 Alice 不得不使用私钥
a
复制代码
来计算
z
复制代码
。这里的关键:
c
复制代码
必须是个随机数。
Bob 验证是在椭圆曲线群上完成。Bob 不知道
r
复制代码
,但是他知道
r
复制代码
映射到曲线上的点
R
复制代码
;Bob 也不知道
a
复制代码
,但是他知道
a
复制代码
映射到曲线群上的点
PK
复制代码
,即
a*G
复制代码
。通过同态映射与Schwatz-Zippel 定理,Bob 可以校验
z
复制代码
的计算过程是否正确,从而知道 Alice 确实是通过
r
复制代码
和
a
复制代码
计算得出的
z
复制代码
,但是又不暴露
r
复制代码
与
a
复制代码
的值。
还有,在协议第一步中产生的随机数
r
复制代码
保证了
a
复制代码
的保密性。因为任何一个秘密当和一个符合「一致性分布」的随机数相加之后的和仍然符合「一致性分布」。
证明零知识
我们这里看一下 Schnorr 协议如何证明一个弱一些的「零知识」性质—— Special Honest Verifier Zero-Knowledge「SHVZK」:
SHVZK 要求协议中的 Bob 的行为不能不按常理出牌,比如他必须按协议约定,在第二步时,去传送带上取一个新鲜的随机数,并且立即使用。而通常意义上的「零知识」是不会对 Bob 做任何要求,所以我们说这里是一个弱一些的性质。虽然目前 Schnorr 协议不能证明完全的「零知识」,但经过添加一些协议步骤,就可以达到完全零知识的目的,细节这里不展开。以后我们在讨论 Fiat-Shamir 变换时,还会再次讨论这个问题。
首先「模拟器」模拟一个「理想世界」,在理想世界中模拟出一个 Zlice 和 Bob 对话,Zlice 没有 Schnorr 协议中的知识,
sk
复制代码
,而 Bob 是有公钥
PK
复制代码
的。请大家看下图,Bob 需要在 Schnorr 协议中的第二步出示一个随机数
c
复制代码
,这里有个额外的要求, 就是 Bob 只能「诚实地」从一个外部「随机数传送带」上拿一个随机数,每一个随机数都必须是事先抛k次「硬币」产生的一个
2^k
复制代码
范围内的一次性分布随机数。Bob 不能采用任何别的方式产生随机数,这就是为何我们要求 Bob 是诚实的。
下面演示 Zlice 如何骗过 Bob:
序幕:请注意 Zlice 没有关于 sk 的知识,这时 Bob 的随机数传送带上已经预先放置了一些随机数。
第一步:Zlice 产生一个一致性分布的随机数 c,并且利用一个新的「超能力」,将刚刚产生的随机数 c替换掉 Bob 的随机数传送带上第一个随机数。这时候,Bob 无法察觉。
第二步:Zlice 再次产生一个随机数 z,然后计算 R'=z*G - c*PK,并将 R' 发送给 Bob。
第三步:这时候Bob 会从随机数传送带上取得 c,并且将 c 发送给 Zlice。请注意这个 c 正好就是第一步中 Zlice 产生的 c。
第四步:Zlice 将第三步产生的随机数 z 发送给 Bob,Bob 按照 Schnorr 协议的验证公式进行验证,大家可以检查下,这个公式完美成立。
大家可以再对比下「现实世界」的 Schnorr 协议,在两个世界中,Bob 都能通过验证。
但区别是:
在「理想世界中」,Zlice 没有
sk
复制代码
;而在「现实世界中」,Alice 有
sk
复制代码
在「理想世界中」,
z
复制代码
是一个随机数,没有涉及
sk
复制代码
;而在「现实世界中」,
z
复制代码
的计算过程里面包含
sk
复制代码
在「理想世界中」,Zlice 使用了超能力,替换了 Bob 的随机数;而在「现实世界中」,Alice 看不到 Bob 的随机数传送带,也无法更改传送带上的数字
这里请大家思考下:
Schnorr 协议中,Bob 在第二步发挑战数能不能和第一步对调顺序?也就是说 Bob 能不能先发挑战数,然后 Alice 再发送 R = r*G。
答案是不能。
如果 Alice 能提前知道随机数,那么 (现实世界中的)Alice 就可以按照模拟器 Zlice 做法来欺骗 Bob。
再遇模拟器
其实,「可靠性」和「零知识」这两个性质在另一个维度上也是存在着一种对称性。可靠性保证了恶意的 Alice 一定失败,零知识保证了恶意的 Bob 一定不会成功。有趣地是,这种对称性将体现在模拟出来的「理想世界」中。
我们分析下可靠性这个定义:Alice 没有知识导致 Bob 验证失败。它的逆否命题为:Bob 验证成功导致 Alice 一定有知识。
我们再次求助模拟器,让他在可以发挥超能力的「理想世界」中,去检验 Alice 的知识。
再次,请大家设想在平行宇宙中,有两个世界,一个是叫做「理想世界」,另一个叫做「现实世界」。理想世界有趣的地方在于它是被「模拟器」模拟出来的,同时模拟器可以在理想世界中放入带有超能力的 NPC。这次把 Alice 的两个分身同时放入「理想世界」与「现实世界」。
假设「你」扮演 Bob 的角色,你想知道和你对话的 Alice 是否真的是「可靠的」。于是把你放入「理想世界」,借助一个具有超能力的 NPC,你可以把对面的 Alice 的知识「抽取」出来。
W...hat?我们不是刚刚证明过:协议是零知识的吗?零知识就意味着 Bob 抽取不出任何的「知识」碎片。这里敲黑板,「零知识」是对于「现实世界」而言的。我们现在正在讨论的是神奇的「理想世界」。
重复一遍,在「理想世界」中,你可以借助一个有超能力的 NPC 来抽取 Alice 的知识,从而可以保证「现实世界」中的 Alice 无法作弊。可以想象一下,一个作弊的 Alice,她肯定没有知识,没有知识也就不可能在「理想世界」中让 NPC 抽取到任何东西。
然而在「现实世界」中,你无法借助 NPC,当然也就看不到 Alice 的知识,也就不会和「零知识」性质冲突。因为两个世界发生的事件是「不可区分」的,我们可以得到这样的结论:在「现实世界」中,Alice 一定是存在知识的。
整理一下思路:如何证明在一个交互会话中 Alice 不能作弊呢?我们需要为这个交互会话定义一个「模拟算法」,该算法可以模拟出一个「理想世界」,其中有一个特殊的角色叫做「抽取器」(Extractor),也就是我们前面说的 NPC,它能够通过「超能力」来「抽取」Alice 的知识,但是让对方「无所察觉」。
当年 Sony PlayStation 3 的工程师在调用 ECDSA 库函数时,本来应该输入随机数的参数位置上,却传入了一个常数。熟悉密码学的黑客们发现了这个严重的后门。2011年1月,神奇小子 Geohot 公开发布了 Sony PS3 的主私钥,这意味着任何用户都可以轻松拿到游戏机的 root 权限。Sony 随后大为光火……
如果 Alice 在两次交互过程中使用了同一个
K
复制代码
,那么 Bob 可以通过发送两个不同的
c
复制代码
和
c'
复制代码
来得到
s
复制代码
和
s'
复制代码
,然后通过下面的公式算出私钥
a
复制代码
:
k = (c - c')/(s - s')a = (k * s - c)/e
那么我们应该怎么来看这个「安全后门」呢?大家想想看,这个安全后门和我们前面证明过的 Schnorr 协议的可靠性证明几乎一模一样!这个算法正是 ECDSA 认证协议的「可靠性」证明中的「抽取器」算法。只不过在可靠性证明中,为了让 Alice 使用同一个随机数
k
复制代码
来认证两次,「抽取器」需要利用「时间倒流」的超能力。
但是在 Sony PS3 系统中,随机数被不明所以的工程师写成了一个固定不变的值,这样相当于直接赋予了黑客「超能力」,而这是在「现实世界」中。或者说,黑客在不需要「时间倒流」的情况下就能实现「抽取器」。