International Association for Cryptologic Research

International Association
for Cryptologic Research


Akash Shah


Succinct Arguments for RAM Programs via Projection Codes
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.


Yuval Ishai (1)
Rafail Ostrovsky (1)