Succinct Arguments for RAM Programs via Projection Codes
Yuval Ishai, Rafail Ostrovsky, Akash Shah
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.
comment:
CRYPTO (2) 2023: 159-192
Fetch PDF file of the paper