Sub-logarithmic distributed oblivious RAM with small block size

DOI10.1007/978-3-030-17253-4_1MaRDI QIDQ2289203zbMATH OpenOpenAlexFDO

Authors Eyal Kushilevitz, Tamer Mour

Publication date 28 January 2020

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

zbMATH Keywords

multi-server settingoblivious RAMprivate storagesecure computation

Mathematics Subject Classification ID

Cryptography (94A60)

Abstract: Oblivious RAM (ORAM) is a cryptographic primitive that allows a client to securely execute RAM programs over data that is stored in an untrusted server. Distributed Oblivious RAM is a variant of ORAM, where the data is stored in $m>1$ servers. Extensive research over the last few decades have succeeded to reduce the bandwidth overhead of ORAM schemes, both in the single-server and the multi-server setting, from $O(sqrtN)$ to $O(1)$. However, all known protocols that achieve a sub-logarithmic overhead either require heavy server-side computation (e.g. homomorphic encryption), or a large block size of at least $Omega(lo{g}^{3}N)$. In this paper, we present a family of distributed ORAM constructions that follow the hierarchical approach of Goldreich and Ostrovsky [GO96]. We enhance known techniques, and develop new ones, to take better advantage of the existence of multiple servers. By plugging efficient known hashing schemes in our constructions, we get the following results: 1. For any $mgeq2$, we show an $m$-server ORAM scheme with $O(logN/loglogN)$ overhead, and block size $Omega(lo{g}^{2}N)$. This scheme is private even against an $(m-1)$-server collusion. 2. A 3-server ORAM construction with $O(omega(1)logN/loglogN)$ overhead and a block size almost logarithmic, i.e. $Omega(lo{g}^{1+epsilon}N)$. We also investigate a model where the servers are allowed to perform a linear amount of light local computations, and show that constant overhead is achievable in this model, through a simple four-server ORAM protocol.

Recommendations

• Two-server distributed ORAM with sublinear computation and constant rounds
• Perfectly secure oblivious RAM with sublinear bandwidth overhead
• Simple and efficient two-server ORAM
• Oblivious RAM with worst-case logarithmic overhead
• Oblivious RAM with \textit{worst-case} logarithmic overhead

Cited in

(20)

• Parameter-hiding order revealing encryption
• More is less: perfectly secure oblivious algorithms in the multi-server setting
• Alibi: a flaw in cuckoo-hashing based hierarchical ORAM schemes and a solution
• Two-server distributed ORAM with sublinear computation and constant rounds
• Efficient 3-party distributed ORAM
• Perfectly secure oblivious RAM with sublinear bandwidth overhead
• Multi-client oblivious RAM with poly-logarithmic communication
• Oblivious RAM with worst-case logarithmic overhead
• Onion ORAM: a constant bandwidth blowup oblivious RAM
• Distributed Oblivious RAM for Secure Two-Party Computation
• CacheShuffle: a family of oblivious shuffles
• CNF-FSS and its applications
• Asymptotically tight bounds for composing ORAM with PIR
• Is there an oblivious RAM lower bound for online reads?
• Is there an oblivious RAM lower bound for online reads?
• PrORAM
• 3-party distributed ORAM from oblivious set membership
• DORAM revisited: maliciously secure RAM-MPC with logarithmic overhead
• A logarithmic lower bound for oblivious RAM (for all parameters)
• Fast ORAM with server-aided preprocessing and pragmatic privacy-efficiency trade-off

This page was built for publication: Sub-logarithmic distributed oblivious RAM with small block size

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