Feige-Fiat-Shamir识别方案:关于ZK协议的一部分问题
我的问题(在下面)是关于协议的哪个部分，验证器通过发送位b ( b = 0或b = 1 )来挑战Prover。
上下文
示例
One时间设置
p = 3
q = 5
n = 15
privKey = 8 (co-prime to n)
pubKey = privKey^2 mod n ⇒ 64 mod 15 = 4此时，验证者知道：
n = 15pubKey = 4
Protocol:以下是重复t次
- 验证器选择一个随机数randNum = 11
- 验证器按以下方式计算x，并将x发送给验证器
x = randNum^2 mod n ⇒ 121 mod 15 = 1 - 验证器选择一个位，
b = 0或b = 1，并将其作为一个挑战发送给Prover。 - Prover将
(privKey^b • randNum) mod n计算为响应
通过选择位
b = 0或b = 1，验证器选择查看：Case 1 b= 0：randNum mod n ⇒ 11 mod 15 = 11(如果randNum是<n__，验证器将接收randNum__) OR大小写2 b= 1:(randNum • privKey) mod n ⇒ 88 mod 15 = 13
Case 1: b = 0作为来自Prover的响应，验证程序接收：11验证程序计算：
11^2 mod 15 = (x • pubKey^b) mod n
11^2 mod 15 = (1 • 4^0) mod 15
121 mod 15 = 1 mod 15
1 = 1 //passes the testCase 2: b = 1作为来自Prover的响应，验证程序接收：13验证程序计算：
13^2 mod 15 = (x • pubKey^b) mod n
13^2 mod 15 = (1 • 4^1) mod 15
169 mod 15 = 4 mod 15
4 = 4 //passes the test我的问题
在Case 1中，验证程序实际上检查的是：
randNum^2 mod n = (randNum^2 mod n) mod n 本质上是randNum = randNum
我不明白为什么这部分协议是必要的。在这里，似乎所有的Prover都证明了他们选择了一个randNum。任何不知道privKey的人都能做到这一点。
我了解到，在任何一轮中，只有50%的机会选择这种情况，而一个错误的Prover (不知道privKey的人)将不可避免地失败，但似乎Case 2 ( b = 1 )足以使验证者确信Prover知道privKey，同时获得关于privKey 和的零知识，没有任何虚假的Prover能够通过这个测试。
为什么Case 1是协议的必要部分？我一定是漏掉了什么。
我希望这是明确的，谢谢！
回答 1
Cryptography用户
发布于 2019-09-09 18:05:02
如果b总是相同的值，那么您可以让验证程序相信您拥有私钥，即使您实际上没有！
案例b = 1：
假验证器可以发送x = {\text{randNum}}^2 \bmod n，而不是发送x = {\text{randNum}}^2 / \text{pubKey} \bmod n。
假设验证程序发送b = 1，则false Prover可以发送\text{randNum} \bmod n。
当验证器验证响应时，它们会检查{\text{randNum}}^2 == (({\text{randNum}}^2)/\text{pubKey} \bmod n) \times \text{pubKey} \bmod n)是否简化为{\text{randNum}}^2 == {\text{randNum}}^2 \bmod n，这显然是正确的。因此，即使假验证器实际上没有私钥，验证也成功了。但问题是:如果b变成了0，那么他们必须在最后一步发送\sqrt{x} \bmod n。这在计算上是不可行的。
正如您所观察到的，如果错误验证程序发送x = {\text{randNum}}^2和b结果为0，则它们可以通过验证。但是如果是b = 1，错误的验证程序不能通过最后一步，因为他们不知道\text{privKey}。
总之，在发送b之前，false Prover必须提交0或1。每个猜测都有50/50的概率是正确的。因此，在t回合之后，Prover实际上是一个假Prover的机会是(1/2)^t。
https://crypto.stackexchange.com/questions/56127
复制相似问题
腾讯云开发者
