Yibin Yang, Georgia Institute of Technology; David Heath, University of Illinois Urbana-Champaign
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 optimized 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.
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
author = {Yibin Yang and David Heath},
title = {Two Shuffles Make a {RAM}: Improved Constant Overhead Zero Knowledge {RAM}},
booktitle = {33rd USENIX Security Symposium (USENIX Security 24)},
year = {2024},
isbn = {978-1-939133-44-1},
address = {Philadelphia, PA},
pages = {1435--1452},
url = {https://www.usenix.org/conference/usenixsecurity24/presentation/yang-yibin},
publisher = {USENIX Association},
month = aug
}
