CryptoDB
PrORAM: Fast O(log n) Authenticated Shares ZK ORAM
| Authors: |
|
|---|---|
| Download: | |
| 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
BibTeX
@inproceedings{asiacrypt-2021-31353,
title={PrORAM: Fast O(log n) Authenticated Shares ZK ORAM},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-92068-5_17},
author={David Heath and Vladimir Kolesnikov},
year=2021
}