是否有任何生成零知识证明不实用的算法？

Question

这与我先前的问题有关：

或其他零知识证明可以用来证明消息的真实性而不泄露私钥吗？

是否有任何算法在计算上如此复杂，以至于无法在任何实际时间内由主流设备(个人电脑、智能手机)生成零知识证明？

我主要对加密算法感兴趣，但是任何例子都会很好。

Answer 1

下面是一个相当“无聊”的例子，但很有可能奏效(我稍后会指出我正在做的具体假设)。如果你也觉得它很无聊，它可能会帮助你完善你的问题，这样答案就会更有趣。

假设您有一些具有安全参数n的加密方案(我们不妨考虑一下n-bit RSA，任何示例都行)。假设加密需要T_E = O(f(n))时间来处理某些函数f(n)。现在考虑一些你感兴趣的陈述的ZK证明。假设需要T_P = O(g(n))时间来证明该语句，其中复杂性取决于为加密选择的安全参数。

我将假设加密比生成证明(或形式上的f(n) = o(g(n)) )更容易。这似乎相当自然，但我对这些细节还不太熟悉，不知道它是否适用于所有的加密方案/证明(虽然没有，但对于某个特定的加密方案，我们可以得到“免费”的证明，这似乎很奇怪)。

然后，我们可以考虑引入另一个参数k (它比n小)，并查看具有安全参数kn的加密方案/验证系统。我声称以下两件事应该站得住脚：

• 如果k足够小，在您想象的设备上使用安全参数kn的加密仍然是可行的
• 作为f(n) = o(g(n))，渐进证明生成将在加密之前变得不可行(因为证明生成的复杂性“严格地更快”)。

因此，如果k足够大，我们预计加密和证明生成都将变得不可行。但由于两者的渐近复杂性不同，我们认为证明生成首先是不可行的，因此应该存在一些k的“中间值”，这样我们仍然可以加密，但不能生成证明。