Paper 2023/1115 Original: eprint.iacr.org/2023/1115 ↗
Two Shuffles Make a RAM: Improved Constant Overhead Zero Knowledge RAM
Abstract
We optimize Zero Knowledge (ZK) proofs of statements expressed as RAM programs over arithmetic values. Our arithmetic-circuit-based read/write memory uses only 4 input gates and 6 multiplication gates per memory access. This is an almost 3× total gate improvement over prior state of the art (Delpech de Saint Guilhem et al., SCN’22). We implemented our memory in the context of ZK proofs based on vector oblivious linear evaluation (VOLE), and we further optimize based on techniques available in the VOLE setting. Our experiments show that (1) our total runtime improves over that of the prior best VOLE-ZK RAM (Franzese et al., CCS’21) by 2-20× and (2) on a typical hardware setup, we can achieve ≈ 600K RAM accesses per second. We also develop improved read-only memory and set ZK data structures. These are used internally in our read/write memory and improve over prior work.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2023-11-03: last updated
- 2023-07-17: published
- Short URL
- https://ia.cr/2023/1115
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2023/1115,
author = {Yibin Yang and David Heath},
title = {Two Shuffles Make a RAM: Improved Constant Overhead Zero Knowledge RAM},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1115},
year = {2023},
url = {https://eprint.iacr.org/2023/1115}
}