Spooky Interaction and its Discontents: Compilers for Succinct Two-Message Argument Systems

摘要

We are interested in constructing short two-message arguments for various languages, where the complexity of the verifier is small (e.g. linear in the input size, or even sublinear if the input is coded appropriately).In 2000 Aiello et al. suggested the tantalizing possibility of obtaining such arguments for all of NP. These have proved elusive, despite extensive efforts. Our work builds on the compiler of Kalai and Raz, which takes as input an interactive proof system consisting of several rounds and produces a two-message argument system. The proof of soundness of their compiler relies on superpolynomial hardness assumptions.In this work we obtain a succinct two-message argument system for any language in NC, where the verifier's work is linear (or even polylogarithmic). This is the first non trivial two-message succinct argument system that is based on a standard polynomial-time hardness assumption. We obtain this result by showing that the compiler is sound if the verifier in the original protocol runs in logarithmic space and public coins. On the other hand, we prove that under standard assumptions there is a sound interactive proof protocol that, when run through the compiler, results in a protocol that is not sound.