Two Shuffles Make a RAM: Improved Constant Overhead Zero Knowledge RAM
Yibin Yang, David Heath
33rd USENIX Security Symposium · Day 1 · USENIX Security '24
This talk, presented by Yibin Yang in collaboration with David Heath from UI, introduces a novel and highly efficient construction for **Zero-Knowledge Random Access Memory (ZK-RAM)**. ZK-RAM is a critical primitive that enables general-purpose computation within zero-knowledge proofs, moving beyond the limitations of purely circuit-based proofs. While prior work had achieved asymptotically optimal constant-overhead ZK-RAM, this research significantly reduces the *constant factor* associated with the overhead, making ZK-RAM substantially more practical for real-world applications.
AI review
This is a foundational piece of research that significantly pushes the practical boundaries of Zero-Knowledge RAM. By elegantly reducing the problem to two permutation proofs, the authors have drastically cut the constant factor overhead, making ZK-RAM viable for complex, memory-intensive applications like verifiable machine learning. This is a critical advancement for the entire field of zero-knowledge proofs.