Paper 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.
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
-
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}
}