Speaker: Alessandro Chiesa (MIT CSAIL)
Time: Thursday August 9nd 2012, 14:00
Place: Schreiber 309, Tel Aviv University
Title: Fast Reductions from RAMs to
Delegatable Succinct Constraint Satisfaction Problems
Abstract:
Succinct arguments for NP are proof systems that allow a weak verifier to retroactively check computation done by a more powerful prover. These protocols prove membership in languages (consisting of succinctly-represented very large 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 and efficient 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. We thus study efficient reductions from RAM to other problem representations for which succinct arguments are known. Specifically, we construct reductions from the correctness of computation of a $T$-step non-deterministic random-access machine to:
1. (succinct) circuit satisfiability with $O(\log T)$ overhead, and
2. (succinct) algebraic constraint satisfaction with $O(\log^{3} T)$ overhead.
On the former problem representation, several argument systems based on bilinear techniques can be invoked.
On the latter problem representation, the best known Probabilistically Checkable Proofs can be directly invoked.
Our constructions are explicit and do not hide large constants.
To attain these, we develop a set of tools (both unconditional and leveraging computational assumptions) for generically and efficiently structuring and arithmetizing the computation of random-access machines.
Joint work with Eli Ben-Sasson, Daniel Genkin, and Eran Tromer.
[http://eprint.iacr.org/2012/071]