零知识证明性能的安全性

Question

最近学习研究零知识证明的安全性

从Wikipedia看来，最流行的例子是阿里巴巴洞穴。我对阿里巴巴洞穴零知识证明的安全性有疑问

在验证过程中，Prover会传递

的价值

e = [0,1 ...]

和e将根据0或1找到left或right的解决方案。并且根据列表的长度e，据说这个过程的安全复杂度为O(2 ^ n)。但是，只有两条路径，并且根据e的值，密钥值在A和B方向上没有改变。所以，这个算法的安全性不应该只是O(2)吗？

Answer 1

阿里巴巴洞穴包括以下场景：

Peggy 选择了一条随机路径（A 或 B），没有来自 Victor 的任何信息。
Victor 在不知道 Peggy 选择的进入路径的情况下要求（在洞穴中喊叫）Peggy 从两端之一（A 或 B）退出洞穴。
Peggy 通过 Victor 选择的路径退出。

对于单个证明，这与随机机会具有相同的概率：如果我们称P_inPeggy进入的路径，V_outVictor让Peggy出去的路径，

如果P_in = V_out，那么Peggy可以在不知道如何打开里面的门的情况下轻松离开洞穴。
如果P_in != V_out，那么Peggy需要知道从洞穴的一侧到另一侧的钥匙。

我们有以下等概率场景：

P_in=A,V_out=A
P_in=A,V_out=B
P_in=B,V_out=A
P_in=B,V_out=B

它们是等概率的，因为 Peggy 随机选择，而 Victor 在不知道 Peggy 选择什么的情况下随机选择（即 zero-knowledge 部分）。

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

但是，如果 Victor 反复要求 Peggy 进入洞穴，则概率成倍增加。即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

Peggy 知道密钥的概率现在提高到 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

指数级复杂性背后的原因在于 一次失败 会建立不信任，而通过随机机会积累 "winning streak" 是指数级的困难。因此，给定先验概率，你得到 O(2 ^ n) 因为你得到 "times two" 每次尝试的难度。

零知识证明性能的安全性

The security of Zero knowledge proof performance

security

encryption

proof