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 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 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 zero-knowledge guarantee and by supporting 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Zero-Knowledge RAM: Doubly Efficient and Black-Box

  • Yuval Ishai,
  • Rafail Ostrovsky,
  • Akash Shah

摘要

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 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 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 zero-knowledge guarantee and by supporting 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.