Succinct arguments from multi-prover interactive proofs and their efficiency benefits

Nir Bitansky, Alessandro Chiesa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Succinct arguments of knowledge are computationally-sound proofs of knowledge for NP where the verifier's running time is independent of the time complexity of the NP nondeterministic machine for the considered language. Existing succinct argument constructions are, typically, based on techniques that combine cryptographic hashing and probabilistically-checkable proofs (PCPs), and thus, in light of today's state-of-the-art PCP technology, are quite inefficient: either one uses long PCP proofs with lots of redundancy to make the verifier fast but at the cost of making the prover slow, or one uses short PCP proofs to make the prover fast but at the cost of making the verifier slow. To obtain better efficiency, we propose to investigate the alternative approach of constructing succinct arguments based on multi-prover interactive proofs (MIPs) and stronger cryptographic techniques: (1) We construct a one-round succinct MIP of knowledge protocol where (i) each prover is highly efficient in terms of time AND space, and ALSO (ii) the verifier is highly efficient. (2) We show how to transform any one round MIP protocol to a succinct four-message argument (with a single prover), while preserving the time and space efficiency of the original MIP protocol. As a main tool for this transformation, we construct a succinct multi-function commitment that (a) allows the sender to commit to a vector of functions in time and space complexity that are essentially the same as those needed for a single evaluation of the functions, and (b) ensures that the receiver's running time is essentially independent of the function. The scheme is based on fully-homomorphic encryption (and no additional assumptions are needed for our succinct argument). (3) In addition, we revisit the problem of non-interactive succinct arguments of knowledge (SNARKs), where known impossibilities rule out solutions based on black-box reductions to standard assumptions. We formulate a natural (though non-standard) variant of homomorphic encryption that has a homomorphism-extraction property. We then show that his primitive essentially allows to "squash" our interactive protocol, while again preserving time and space efficiency. We further show that this variant is, in fact, implied by the existence of SNARKs.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology, CRYPTO 2012 - 32nd Annual Cryptology Conference, Proceedings
Pages255-272
Number of pages18
DOIs
StatePublished - 2012
Event32nd Annual International Cryptology Conference, CRYPTO 2012 - Santa Barbara, CA, United States
Duration: Aug 19 2012Aug 23 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7417 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other32nd Annual International Cryptology Conference, CRYPTO 2012
Country/TerritoryUnited States
CitySanta Barbara, CA
Period8/19/128/23/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Succinct arguments from multi-prover interactive proofs and their efficiency benefits'. Together they form a unique fingerprint.

Cite this