Welcome to the resource topic for 2021/587
Title:
PrORAM: Fast O(\log n) Private Coin ZK ORAM
Authors: David Heath, 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.
ePrint: https://eprint.iacr.org/2021/587
Talk: https://www.youtube.com/watch?v=oJ_30plLyZo
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .