Cryptology ePrint Archive: Report 2021/587

PrORAM: Fast $O(\log n)$ Private Coin ZK ORAM

David Heath and Vladimir Kolesnikov

Abstract: We construct a concretely efficient Zero Knowledge (ZK) Oblivious RAM (ORAM) that consumes $2 \log n$ oblivious transfers (OTs) of length-$2\sigma$ 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 Bub- bleRAM of Heath and Kolesnikov ([HK20a], CCS 2020), whose access cost is $1/2 \log^2 n$ OTs of length-$2\sigma$ 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 ZK Proof (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 $~10\times$ faster for arrays of size $2^{20}$ of $40$-bit values.

Category / Keywords: cryptographic protocols / Oblivious RAM, Zero Knowledge

Original Publication (with minor differences): Asiacrypt 2021

Date: received 4 May 2021, last revised 14 Sep 2021

Contact author: heath davidanthony at gatech edu, kolesnikov at gatech edu

Available format(s): PDF | BibTeX Citation

Version: 20210914:161004 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]