CryptoDB
Succinct Arguments for RAM Programs via Projection Codes
| Authors: |
|
|---|---|
| Download: |
|
| 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. |
BibTeX
@inproceedings{crypto-2023-33265,
title={Succinct Arguments for RAM Programs via Projection Codes},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-38545-2_6},
author={Yuval Ishai and Rafail Ostrovsky and Akash Shah},
year=2023
}