CryptoDB
Zero-Knowledge RAM: Doubly Efficient and Black-Box
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2025 |
| Abstract: | We consider the problem of verifying the computations of a RAM program on a committed database $x\in\{0,1\}^n$. A recent work by Ishai, Ostrovsky, and Shah (Crypto 2023) obtained a {\em doubly efficient} solution, in which the communication and verifier’s work are polylogarithmic in $n$ and the prover’s work is comparable to the (possibly sublinear) running time of the RAM program. This only makes a {\em black-box} use of a collision-resistant hash function, or alternatively can be implemented unconditionally and non-interactively in the random oracle model. In the current work, we extend this prior work by providing an additional {\em zero-knowledge} guarantee and by supporting {\em database updates}. This gives the first doubly efficient zero-knowledge implementation of RAM programs that makes a black-box use of symmetric cryptography. While the extra zero knowledge and updatable database features of our solution are orthogonal in scope, our means for achieving them are technically related: to verify with zero knowledge many computations on the same database, we rely on a database refreshing procedure that we also use to accommodate updates. |
BibTeX
@inproceedings{eurocrypt-2025-35103,
title={Zero-Knowledge RAM: Doubly Efficient and Black-Box},
publisher={Springer-Verlag},
author={Yuval Ishai and Rafail Ostrovsky and Akash Shah},
year=2025
}