超多项式提取器对零知识证明安全性的影响

Question

交互式零知识论点被证明是安全的，分为三部分：

1. 完整性(如果验证者是诚实的，验证者会接受)
2. 稳健(不诚实的证明者无法说服验证者)
3. 零知识(证明不泄露任何信息给诚实的验证者)

可靠性通常是使用某种提取器来证明的:通过对协议进行多次回绕，验证器可以发送多个挑战，并且最终可以计算出验证者持有的证据。

这是Benedikt Bünz的讲话提到原始Bootle J.等。2016年年协议(防弹的前身)的提取器有一个问题:提取器在超多项式时间内运行。

提取器的超多项式复杂度的影响是什么？仅仅是一个提取者的存在不足以证明证明者必须持有证人吗？

Answer 1

提取器和知识背后的哲学是，如果证明器能够产生证据，那么它本身就可以运行提取器。因此，如果它能证明，那么它就知道证人。

如果提取器在超多项式时间内运行，则证明器本身无法运行提取器。请注意，如果你把它带到了一个极端，那么在指数时间内，总是有可能找到目击证人。因此，任何ZK证明都可以说是知识的指数型时间提取器的证明。但这毫无意义。

从技术上讲，使用这种零知识证明的协议的安全性证明会崩溃。