Paper 2021/587

PrORAM: Fast O(logn) Private Coin ZK ORAM

David Heath and Vladimir Kolesnikov

Abstract

We construct a concretely efficient Zero Knowledge (ZK) Oblivious RAM (ORAM) that consumes 2logn oblivious transfers (OTs) of length-2σ secrets per access of an arithmetic value, for statistical security parameter σ 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/2log2n OTs of length-2σ 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 faster for arrays of size of -bit values.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. Asiacrypt 2021
Keywords
Oblivious RAMZero Knowledge
Contact author(s)
heath davidanthony @ gatech edu
kolesnikov @ gatech edu
History
2021-09-14: revised
2021-05-10: received
See all versions
Short URL
https://ia.cr/2021/587
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/587,
      author = {David Heath and Vladimir Kolesnikov},
      title = {{PrORAM}: Fast $O(\log n)$ Private Coin {ZK} {ORAM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/587},
      year = {2021},
      url = {https://eprint.iacr.org/2021/587}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.