Welcome to the resource topic for 2016/291
Title:
Spooky Interaction and its Discontents: Compilers for Succinct Two-Message Argument Systems
Authors: Cynthia Dwork, Moni Naor, Guy N. Rothblum
Abstract: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 it is coded properly). Suppose that we have a low communication public-coin interactive protocol for proving (or arguing) membership in the language. We consider a compiler'' from the literature that takes a protocol consisting of several rounds and produces a two-message argument system. The compiler is based on any Fully Homomorphic Encryption (FHE) scheme, or on PIR (under additional conditions on the protocol). This compiler has been used successfully in several proposed protocols. We investigate the question of whether this compiler can be proven to work under standard cryptographic assumptions. We prove: (i) If FHEs or PIR systems exist, then there is a sound interactive proof protocol that, when run through the compiler, results in a protocol that is not sound. (ii) If the verifier in the original protocol runs in logarithmic space and has no long-term’’ secret memory (a generalization of public coins), then the compiled protocol is sound. This yields a succinct two-message argument system for any language in NC, where the verifier’s work is linear (or even polylog if the input is coded appropriately). This is the first (non trivial) two-message succinct argument system that is based on a standard polynomial-time hardness assumption.
ePrint: https://eprint.iacr.org/2016/291
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .