Cryptology ePrint Archive: Report 2012/071

Fast Reductions from RAMs to Delegatable Succinct Constraint Satisfaction Problems

Eli Ben-Sasson and Alessandro Chiesa and Daniel Genkin and Eran Tromer

Abstract: Succinct arguments for NP are proof systems that allow a weak verifier to retroactively check computation done by a powerful prover. Constructions of such protocols prove membership in languages consisting of \emph{very large yet succinctly-represented constraint satisfaction problems} that, alas, are unnatural in the sense that the problems that arise in practice are not in such form.

For general computation tasks, the most natural representation is typically as random-access machine (RAM) algorithms, because such a representation can be obtained very efficiently by applying a compiler to code written in a high-level programming language. Thus, understanding the efficiency of reductions from RAM computations to other NP-complete problem representations for which succinct arguments (or proofs) are known is a prerequisite to a more complete understanding of the applicability of these arguments.

Existing succinct argument constructions rely either on circuit satisfiability or (in PCP-based constructions) on algebraic constraint satisfaction problems. In this paper, we present new and more efficient reductions from RAM (and parallel RAM) computations to both problems that (a) preserve succinctness (i.e., do not ``unroll'' the computation of a machine), (b) preserve zero-knowledge and proof-of-knowledge properties, and (c) enjoy fast and highly-parallelizable algorithms for transforming a witness to the RAM computation into a witness for the corresponding problem. These additional properties are typically not considered in ``classical'' complexity theory but are often required or very desirable in the application of succinct arguments.

Fulfilling all these efficiency requirements poses significant technical challenges, and we develop a set of tools (both unconditional and leveraging computational assumptions) for generically and efficiently structuring and arithmetizing RAM computations for use in succinct arguments. More generally, our results can be applied to proof systems for NP relying on the aforementioned problem representations; these include various zero-knowledge proof constructions.

Category / Keywords: delegation of computation; succinct arguments; random-access machines; proba- bilistically checkable proofs; zero-knowledge proofs

Date: received 17 Feb 2012, last revised 18 Aug 2012

Contact author: alexch at csail mit edu

Available format(s): PDF | BibTeX Citation

Note: Revised introduction and technical sections.

Version: 20120818:081427 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]