More is less: perfectly secure oblivious algorithms in the multi-server setting

DOI10.1007/978-3-030-03332-3_7MaRDI QIDQ1710668zbMATH OpenOpenAlexFDO

Authors T.-H. Hubert Chan, Kartik Nayak, Antigoni Polychroniadou, Elaine Shi, Jonathan Katz

Publication date 23 January 2019

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

zbMATH Keywords

perfect securityoblivious RAM

Mathematics Subject Classification ID

Cryptography (94A60)

Abstract: The problem of Oblivious RAM (ORAM) has traditionally been studied in a single-server setting, but more recently the multi-server setting has also been considered. Yet it is still unclear whether the multi-server setting has any inherent advantages, e.g., whether the multi-server setting can be used to achieve stronger security goals or provably better efficiency than is possible in the single-server case. In this work, we construct a perfectly secure 3-server ORAM scheme that outperforms the best known single-server scheme by a logarithmic factor. In the process, we also show, for the first time, that there exist specific algorithms for which multiple servers can overcome known lower bounds in the single-server setting.

Recommendations

• Simple and efficient two-server ORAM
• Sub-logarithmic distributed oblivious RAM with small block size
• Multi-client Oblivious RAM Secure Against Malicious Servers
• Oblivious parallel RAM: improved efficiency and generic constructions
• Perfectly secure oblivious RAM without random oracles

Cites work

• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• Asymptotically tight bounds for composing ORAM with PIR
• Cache-oblivious and data-oblivious sorting and applications
• Circuit OPRAM: unifying statistically and computationally secure ORAMs and OPRAMs
• Distributed Oblivious RAM for Secure Two-Party Computation
• More is less: perfectly secure oblivious algorithms in the multi-server setting
• Oblivious RAM with \(O((\log N)^{3})\) worst-case cost
• Oblivious RAMs without cryptogarphic assumptions
• Oblivious hashing revisited, and applications to asymptotically efficient ORAM and OPRAM
• On the (in)security of hash-based oblivious RAM and a new balancing scheme
• Path ORAM
• Perfectly secure oblivious RAM with sublinear bandwidth overhead
• Perfectly secure oblivious RAM without random oracles
• Perfectly secure oblivious parallel RAM
• Privacy-preserving access of outsourced data via oblivious RAM simulation
• Searchable encryption with optimal locality: achieving sublogarithmic read efficiency
• Simple and efficient two-server ORAM
• Software protection and simulation on oblivious RAMs
• Statistically-secure ORAM with \(\tilde{O}(\log^2 n)\) overhead
• Sub-logarithmic distributed oblivious RAM with small block size

Cited in

(7)

• Two-server distributed ORAM with sublinear computation and constant rounds
• 3-party distributed ORAM from oblivious set membership
• Linear-time 2-party secure merge from additively homomorphic encryption
• Parameter-hiding order revealing encryption
• A note on the server problem and a benevolent adversary
• More is less: perfectly secure oblivious algorithms in the multi-server setting
• Privacy-preserving Dijkstra

This page was built for publication: More is less: perfectly secure oblivious algorithms in the multi-server setting

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