cover_image

PSPACE在ZK里面！！怎么似乎没人关心？

Kurt Pan XPTY
2023年07月19日 18:24

作者 ：gasarch

译者 ：Kurt Pan

ZK=零知识。

证明 是一件大事。 这是 Goldreich-Micali-Wigderson 论文的选段（参见此处（FOCS-1986、JACM-1991）。在 JACM 论文版本中，他们写了下面一段话：

我们的结果「所有NP语言都具有零知识证明系统」，在相同的假设下，已被扩展到了 IP。 （该结果首先由 Impagliazzo 和 Yung 证明，但他们的论文 [53] 只包含对结果的声明，感兴趣的读者会被导向有一个（不同证明）的 [11]。）换句话说，任何能被有效证明的都可以被有效地以零知识的方式证明。可以认为这是可能的最好结果，因为只有具有交互式证明系统的语言才能具有零知识交互式证明系统。

  1. BEN-OR, M., GOLDREICH, O., GOLDWASSER, S., HASTAD, J., KILLIAN, J., MICALI, S,,  AND ROGAWAY, P. Everything provable is provable in zero-knowledge. In Proceedings of Advances in Cryptology— Crypto88. Lecture Notes in Computer Science, vol. 403. Springer-Verlag, New York, 1990, pp. 37-56.
  2. IMPAGLIAZZO. R., AND YUNG, M. Direct minimum-knowledge computations. In C. Pomerance, ed., Proceedings of Advances in Cryptology— Crypto87. Lecture Notes in Computer Science, vol. 293. Springer-Verlag, New York, 1987, pp. 40-51.

后来Lund-Fortnow-Karloff-Nisan和Shamir的论文证明了IP=PSPACE。 因此：

当我意识到这一点时，我想，“哦，这很有趣啊！” 然后我在网上查了一下，结果没有找到任何提及这点的信息。 我问了Lance和一些密码学领域的人，是的，他们都知道这是真的，但似乎没有人关心。

为什么如此冷漠呢？ 几个推测：

  1. ZK 是一个人们其实想在现实的加密货币中使用的概念（最近在这方面是取得了一些进展）。 而PSPACE 中 ZK 的证明者离强大到可以实用还有很长距离。我不太喜欢这个解释因为我们讨论的本就是理论家。 即使在与真实工作有更多联系的密码学领域，仍然存在大量“无用”的结果，比如Ramsey理论。
  2. IP=PSPACE 是个大新闻，有着有趣的证明和很好的想法。这里面没有什么密码学的东西。  所以推论 是事后的想法。
  3. SAT在ZK里面是个大新闻。IP在ZK里面也不错，但基本使用相同的想法。
  4. 是我错了——这是一个值得庆祝的结果，但我不知怎的错过了庆祝活动。
  5. ZK 在 PSPACE 中的证明使用了两个有趣的结果，但合起来没有添加任何内容。 简言之，证明太容易了。

有其他想法吗？

匿名评论：

我猜有两个原因：

  • NP在ZK中是一个有条件的结果（尽管是一个我们在安全加密中倾向于相信的条件），这与 IP=PSPACE 不同。 除非接受令人震惊的复杂性坍塌，否则该结果将不适用于 SZK。
  • 在多轮交互是一个问题的实用密码学场景下的ZK是最有趣的。 从这个角度来看，有界轮ZK 或 NIZK 是主要兴趣所在。 同样，如果没有令人震惊的复杂性坍塌，PSPACE 似乎不太可能处于有界 ZK 中，因为 IP=PSPACE 的证明严重依赖于无界交互轮数。

JT:

你可以将此结果解释为任何（非零知识）协议到零知识协议的通用转换。人们确实关心这种非 zk 到 zk 的转换，即使在实践中也是如此。例如，今天的大多数zk-SNARK都是通过首先给出一个非零知识SNARK，然后找到一种方法来“添加”零知识，且不会产生太多开销。当然，现在已知的转换比[11]中给出的要实用得多。并且，去为手头的非零知识协议定制转换可以带来具体的好处，而不是去使用一个完全通用的转换。