International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: PrORAM: Fast O(log n) Authenticated Shares ZK ORAM

David Heath , Georgia Institute of Technology
Vladimir Kolesnikov , Georgia Institute of Technology
DOI: 10.1007/978-3-030-92068-5_17
Search ePrint
Search Google
Conference: ASIACRYPT 2021
Abstract: We construct a concretely efficient Zero Knowledge (ZK) Oblivious RAM (ORAM) for ZK Proof (ZKP) systems based on authenticated sharings of arithmetic values. It consumes 2logn oblivious transfers (OTs) of length-2sigma secrets per access of an arithmetic value, for statistical security parameter sigma and array size n. This is an asymptotic and concrete improvement over previous best (concretely efficient) ZK ORAM BubbleRAM of Heath and Kolesnikov ([HK20a], CCS 2020), whose access cost is 1/2 log^2 n OTs of length-2sigma secrets. ZK ORAM is essential for proving statements that are best expressed as RAM programs, rather than Boolean or arithmetic circuits. Our construction is private-coin ZK. We integrate it with [HK20a]’s ZKP protocol and prove the resulting ZKP system secure. We implemented PrORAM in C++. Compared to the state-of-the-art BubbleRAM, our PrORAM is ~10x faster for arrays of size 2^20 of 40-bit values.
Video from ASIACRYPT 2021
  title={PrORAM: Fast O(log n) Authenticated Shares ZK ORAM},
  author={David Heath and Vladimir Kolesnikov},