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

DOI10.1007/978-3-662-45608-8_4MaRDI QIDQ2936600zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(17)

• Stronger lower bounds for online ORAM
• 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
• Parameter-hiding order revealing encryption
• Oblivious parallel RAM and applications
• Oblivious parallel RAM: improved efficiency and generic constructions
• Oblivious RAM with \textit{worst-case} logarithmic overhead
• Asymptotically tight bounds for composing ORAM with PIR
• 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

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)