TY - GEN
T1 - PrORAM
T2 - 27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021
AU - Heath, David
AU - Kolesnikov, Vladimir
N1 - Funding Information:
Acknowledgments. This work was supported in part by NSF award #1909769, by a Facebook research award, by Georgia Tech’s IISP cybersecurity seed funding (CSF) award. This material is also based upon work supported in part by DARPA under Contract No. HR001120C0087. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of DARPA.
Funding Information:
This work was supported in part by NSF award #1909769, by a Facebook research award, by Georgia Tech?s IISP cybersecurity seed funding (CSF) award. This material is also based upon work supported in part by DARPA under Contract No. HR001120C0087. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of DARPA.
Publisher Copyright:
© 2021, International Association for Cryptologic Research.
PY - 2021
Y1 - 2021
N2 - 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 2 log n 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 BubbleRAM of Heath and Kolesnikov ([HK20a], CCS 2020), whose access cost is 12log2n 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 ZKP protocol and prove the resulting ZKP system secure. We implemented PrORAM in C++. Compared to state-of-the-art BubbleRAM, PrORAM is ≈ 10 × faster for arrays of size 220 of 40-bit values.
AB - 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 2 log n 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 BubbleRAM of Heath and Kolesnikov ([HK20a], CCS 2020), whose access cost is 12log2n 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 ZKP protocol and prove the resulting ZKP system secure. We implemented PrORAM in C++. Compared to state-of-the-art BubbleRAM, PrORAM is ≈ 10 × faster for arrays of size 220 of 40-bit values.
KW - Oblivious RAM
KW - Zero knowledge
UR - http://www.scopus.com/inward/record.url?scp=85121925885&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85121925885&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-92068-5_17
DO - 10.1007/978-3-030-92068-5_17
M3 - Conference contribution
AN - SCOPUS:85121925885
SN - 9783030920678
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 495
EP - 525
BT - Advances in Cryptology – ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, 2021, Proceedings, Part 4
A2 - Tibouchi, Mehdi
A2 - Wang, Huaxiong
PB - Springer
Y2 - 6 December 2021 through 10 December 2021
ER -