Welcome to the resource topic for 2021/1123
Title:
Oblivious RAM with Worst-Case Logarithmic Overhead
Authors: Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Elaine Shi
Abstract:We present the first Oblivious RAM (ORAM) construction that for N memory blocks supports accesses with worst-case O(\log N) overhead for any block size \Omega(\log N) while requiring a client memory of only a constant number of memory blocks. We rely on the existence of one-way functions and guarantee computational security. Our result closes a long line of research on fundamental feasibility results for ORAM constructions as logarithmic overhead is necessary. The previous best logarithmic overhead construction only guarantees it in an amortized sense, i.e., logarithmic overhead is achieved only for long enough access sequences, where some of the individual accesses incur \Theta(N) overhead. The previously best ORAM in terms of worst-case overhead achieves O(\log ^2 N/\log\log N) overhead. Technically, we design a novel de-amortization framework for modern ORAM constructions that use the ``shuffled inputs’’ assumption. Our framework significantly departs from all previous de-amortization frameworks, originating from Ostrovsky and Shoup (STOC '97), that seem to be fundamentally too weak to be applied on modern ORAM constructions.
ePrint: https://eprint.iacr.org/2021/1123
Talk: https://www.youtube.com/watch?v=20C0loX3MnM
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .