零知识证明性能的安全性

Question

最近我学会了学习零知识证明的安全性。

从维基百科看来，最受欢迎的例子是阿里巴巴洞。我对阿里巴巴洞零知识证明的安全性有疑问。

在验证过程中，Prover将提供

e = [0,1 ...]

e将根据0或1的不同，为left或right提供解决方案。根据列表e的长度，这个过程被认为具有O(2 ^ n)的安全复杂性。然而，只有两条路径，并且取决于e的值，秘密密钥值不会在A和B方向上改变，因此，该算法的安全性不应该仅仅是O(2)。

Answer 1

阿里巴巴洞穴包括以下情况：

1. 佩吉选择了一条随机路径(A或B)，而没有维克多的任何信息。
2. 维克多要求佩吉(在山洞里喊叫)离开洞穴的两端之一(A或B)，而不知道佩吉选择的进入路径。
3. 佩吉从维克多选择的那条路出去。

就一个证明而言，这和随机机会的概率是一样的:如果我们称P_in为佩吉进入的路径，并将V_out称为维克多让佩吉出去的路径，

• 如果是P_in = V_out，那么佩吉就可以在不知道如何打开里面的门的情况下就从洞穴里出来。
• 如果是P_in != V_out，那么佩吉需要知道如何从洞穴的一边穿越到另一边。

我们有以下几种可能的情况：

• P_in = A，V_out =A
• P_in = A，V_out =B
• P_in = B，V_out =A
• P_in = B，V_out =B

它们的可能性是相等的，因为佩吉是随机选择的，而维克多是随机选择的，而不知道佩吉选择了什么(这是零知识部分)。

从先前的假设中，我们很容易得到P(P_in = V_out) = 1/2：也就是说，佩吉能够在没有额外知识的情况下轻松地离开洞穴的概率与随机机会是相同的。

然而，如果维克多一再要求佩吉进入洞穴，概率就会成倍增加。也就是说，P_in#1 = V_out#1 = 50%；但是P_in#2 = V_out#2 = 50% (本身)，这意味着，由于有条件的概率(假设事件是独立的)，为了通过随机的机会将两次时间都弄出洞穴：

P(P_in#1 = V_out#1 /\ P_in#2 = V_out#2) = 1/2 * 1/2 = 1/4

佩吉知道钥匙的概率现在提高到了3/4：

P( (P_in#1 != V_out#1 /\ P_in#2 == V_out#2)
|| (P_in#1 == V_out#1 /\ P_in#2 != V_out#2)
|| (P_in#1 != V_out#1 /\ P_in#2 != V_out#2)) =

P( ((P_in#1 != V_out#1 || P_in#1 == V_out#1) /\ P_in#2 == V_out#2)
|| P_in#1 != V_out#1 /\ P_in#2 != V_out#2) =

P( P_in#2 == V_out#2
|| (P_in#1 != V_out#1 /\ P_in#2 != V_out#2)) = 1/2 + (1/2 * 1/2) = 3/4

指数复杂性背后的原因在于单一的失败建立了不信任，而随机机会积累“连胜”则是指数级的困难。因此，给定先前的概率，您将得到O(2 ^ n)，因为每次尝试都“乘以2”困难。