Welcome to the resource topic for 2017/749
Title:
Searchable Encryption with Optimal Locality: Achieving Sublogarithmic Read Efficiency
Authors: Ioannis Demertzis, Dimitrios Papadopoulos, Charalampos Papamanthou
Abstract:We propose the first linear-space searchable encryption scheme with constant locality and \emph{sublogarithmic} read efficiency, strictly improving the previously best known read efficiency bound (Asharov et al., STOC 2016) from \Theta(\log N \log \log N) to O(\log ^{\gamma} N) where \gamma=\frac{2}{3}+\delta for any fixed \delta>0. Our scheme employs four different allocation algorithms for storing the keyword lists, depending on the size of the list considered each time. For our construction we develop (i) new probability bounds for the offline two-choice allocation problem; (ii) and a new I/O-efficient oblivious RAM with \tilde{O}(n^{1/3}) bandwidth overhead and zero failure probability, both of which can be of independent interest.
ePrint: https://eprint.iacr.org/2017/749
Talk: https://www.youtube.com/watch?v=EH2LoulNnw4
Slides: https://crypto.iacr.org/2018/slides/28845.pdf
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 .