Paper 2023/1115
Two Shuffles Make a RAM: Improved Constant Overhead Zero Knowledge RAM
, Georgia Institute of Technology, University of Illinois Urbana-ChampaignAbstract
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
- Published elsewhere. Minor revision. USENIX Security 2024
- Keywords
- Zero KnowledgeZK RAM
- Contact author(s)
-
yyang811 @ gatech edu
daheath @ illinois edu - History
- 2023-11-03: revised
- 2023-07-17: received
- See all versions
- Short URL
- https://ia.cr/2023/1115
- License
-
CC BY
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},
note = {\url{https://eprint.iacr.org/2023/1115}},
url = {https://eprint.iacr.org/2023/1115}
}
