证明NP$中的任何语言$L \都有有效的零知识证明。

Question

设(P,V)是A \in NP语言(T,\epsilon)-\text{sound}和(T,\epsilon)-\text{ZK}的一个有效的零知识交互证明.

我想要证明的是，对于每一种语言L来说，都有一个有效的零知识交互证明(P_2, V_2)，也就是(T,\epsilon)-\text{sound}和(T,\epsilon)-\text{ZK}。

嗯，我不知道该如何开始描述这样的(P_2, V_2)，但也许我并不完全理解这一点，因为似乎只有一个简单的方法。

由于L是可还原为A的，所以从L到A有一个Levin还原。也就是说，有一个多项式算法R，例如R(x) \in A \leftrightarrow x \in A，还有一个多项式算法W，它将用于x \in L的见证w映射到用于R(x) \in A的见证W(x,w)。

我的想法是以证明系统(P,V)和输入x应用R(x)来模拟A的原始零知识证明。

然而，对我来说，这似乎太微不足道了。而且，通过这种方式，我只得到了(T-|R|,\epsilon)-\text{sound}和(T-|R|,\epsilon)-\text{ZK}，因为我需要运行算法R。

我会感谢你的帮助。

Answer 1

你的想法是正确的。虽然诚实的验证程序和验证器的运行时间确实会随着R的运行时间而增加，但这(与直觉相反)并不影响可靠性和ZK的具体界限(至少它们通常是如何定义的)。

请注意，T-soundness对于证明系统并没有真正的意义，因为它对即使是无界的欺骗验证程序也是无害的。然而，对于一个论证系统来说，这是有意义的，在这里，我们并不真正“失去”R的S运行时:对于某些实例，任何T-time欺骗证明器P_2^*本身都是实例R(x) \notin A的T-time欺骗验证器，因为它欺骗了验证器V (用于语言A)，而无需进行任何额外的计算。后者不存在于假设中，前者也不存在。

ZK也有类似的理由:一个T-time欺骗验证器V_2^*在某种情况下，x\in L本身就是R(x) \in A的T-time欺骗验证器，因为它在与P对话中扮演了V的角色。因此，我们不需要任何额外的计算来从与P有关R(x)的交互中“获取知识”。