International Association for Cryptologic Research

International Association
for Cryptologic Research


Succinct Arguments for RAM Programs via Projection Codes

Yuval Ishai , Technion
Rafail Ostrovsky , UCLA
Akash Shah , UCLA
DOI: 10.1007/978-3-031-38545-2_6 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: Motivated by the goal of proving statements that involve small subsets of a big database, we introduce and study the notion of projection codes. A standard error-correcting code allows one to encode a message x into a codeword X, such that even if a constant fraction of X is corrupted, the message x can still be recovered. A projection code extends this guarantee to any subset of the bits of x. Concretely, for every projection of x to a subset s of its coordinates, there is a subset S of comparable size such that the projected encoding X|_S forms a robust encoding of the projected message x|_s. Our first main result is a construction of projection codes with a near-optimal increase in the length of x and size of s. We then apply this to obtain our second main result: succinct arguments for the computation of a RAM program on a (big) committed database, where the communication and the run-time of both the prover and the verifier are close to optimal even when the RAM program run-time is much smaller than the database size. Our solution makes only a black-box use of a collision-resistant hash function, providing the first black-box alternative to previous non-black-box constructions with similar asymptotic efficiency.
  title={Succinct Arguments for RAM Programs via Projection Codes},
  author={Yuval Ishai and Rafail Ostrovsky and Akash Shah},