Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-049 | 28th March 2016 19:55

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


Authors: Cynthia Dwork, Moni Naor, Guy Rothblum
Publication: 29th March 2016 06:52
Downloads: 1253


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.

ISSN 1433-8092 | Imprint