Statistically-secure ORAM with O(^2 n) overhead

DOI10.1007/978-3-662-45608-8_4zbMATH Open1317.94097arXiv1307.3699OpenAlexW2964030750MaRDI QIDQ2936600FDOQ2936600

Authors: Kai-Min Chung, Zhenming Liu, Rafael Pass 

Publication date: 6 January 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We demonstrate a simple, statistically secure, ORAM with computational overhead $ildeO(lo{g}^{2}n)$; previous ORAM protocols achieve only computational security (under computational assumptions) or require $ildeOmega(lo{g}^{3}n)$ overheard. An additional benefit of our ORAM is its conceptual simplicity, which makes it easy to implement in both software and (commercially available) hardware. Our construction is based on recent ORAM constructions due to Shi, Chan, Stefanov, and Li (Asiacrypt 2011) and Stefanov and Shi (ArXiv 2012), but with some crucial modifications in the algorithm that simplifies the ORAM and enable our analysis. A central component in our analysis is reducing the analysis of our algorithm to a "supermarket" problem; of independent interest (and of importance to our analysis,) we provide an upper bound on the rate of "upset" customers in the "supermarket" problem.

Full work available at URL: https://arxiv.org/abs/1307.3699

Recommendations

• Oblivious RAM with worst-case logarithmic overhead
• Oblivious RAM with \textit{worst-case} logarithmic overhead
• Yes, there is an oblivious RAM lower bound!
• Perfectly secure oblivious RAM with sublinear bandwidth overhead
• Simple and efficient two-server ORAM

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60)

Cited In (17)

• Oblivious network RAM and leveraging parallelism to achieve obliviousness
• Succinct oblivious RAM
• Lower bound framework for differentially private and oblivious data structures
• OptORAMa: Optimal oblivious RAM
• Perfectly secure oblivious parallel RAM
• Oblivious parallel RAM and applications
• Oblivious parallel RAM: improved efficiency and generic constructions
• Parameter-hiding order revealing encryption
• Asymptotically tight bounds for composing ORAM with PIR
• Oblivious RAM with \textit{worst-case} logarithmic overhead
• Snapshot-oblivious RAMs: sub-logarithmic efficiency for short transcripts
• Optimizing ORAM and Using It Efficiently for Secure Computation
• Locality-preserving oblivious RAM
• Information-Theoretic Local Non-malleable Codes and Their Applications
• More is less: perfectly secure oblivious algorithms in the multi-server setting
• Oblivious RAM with worst-case logarithmic overhead
• Stronger lower bounds for online ORAM

This page was built for publication: Statistically-secure ORAM with \(\tilde{O}(\log^2 n)\) overhead

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2936600)