这是一个安全的零知识证明，两个更好的加密是相等的？

Question

我们有加密的c_1和c_2，知道明文和随机性的人都想证明他们知道。设r_1和r_2分别是c_1和c_2中的随机性值。然后，验证程序随机生成另一个随机数，z。然后计算a_1 = r_1^n z^n，a_2 = r_2^n z^n。这些是证据。验证器只需将a_2与c_1相乘，a_1与c_2相乘，并检查产品是否相等。如果是的话，那么可以安全地假设c_1和c_2包含相同的秘密。如果a_1是c_2，a_2是c_1，那么尽管等式为真，证明显然是假的。

Answer 1

这太不安全了。任何人都可以出示两个密文等同的假证据。

给定c_1和c_2，选择一个随机的x，让a_1=c_1x\mod {n^2}和a_2=c_2x\mod {n^2}。我们看到符合验证标准的a_1c_2\equiv a_2c_1\pmod {n^2}。

证明c_1和c_2是相同值的加密相当于证明c_1/c_2\pmod{n^2}是n的第四次幂。这是一个西格玛协议，用来证明你可以与通常的菲亚特-沙米尔施蒂克进行非交互。

证明k是nth幂模n^2

我们假设证明器具有s:k\equiv s^n\pmod{n^2}。

承诺

验证器生成一个统一的随机数r\mod{n^2}，计算c=r^n\mod{n^2}并发布c。

挑战

验证器请求验证程序发布r这样的r^n=c\mod{n^2}或r'这样的r'^n=ck\mod{n^2}。

响应

Prover根据挑战发布r或r'=rs\mod{n^2}。

如果两种可能的响应都提供给响应者，那么响应者就会知道s=r'/r，因此对这两种响应的了解证明了对s的了解。因此，随着协议迭代次数的增加，该协议具有较高的正确性。

通过首先选择挑战，然后是响应，然后是承诺，韦尔弗可以为自己生成随机的协议记录。因此，该协议是零知识。