International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Searchable Encryption with Optimal Locality: Achieving Sublogarithmic Read Efficiency

Authors:
Ioannis Demertzis
Dimitrios Papadopoulos
Charalampos Papamanthou
Download:
DOI: 10.1007/978-3-319-96884-1_13 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2018
Abstract: We propose the first linear-space searchable encryption scheme with constant locality and sublogarithmic read efficiency, strictly improving the previously best known read efficiency bound (Asharov et al., STOC 2016) from $$\varTheta (\log N \log \log N)$$Θ(logNloglogN) to $$O(\log ^{\gamma } N)$$O(logγN) where $$\gamma =\frac{2}{3}+\delta $$γ=23+δ for any fixed $$\delta >0$$δ>0 and where N is the number of keyword-document pairs. 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})$$O~(n1/3) bandwidth overhead and zero failure probability, both of which can be of independent interest.
Video from CRYPTO 2018
BibTeX
@inproceedings{crypto-2018-28845,
  title={Searchable Encryption with Optimal Locality: Achieving Sublogarithmic Read Efficiency},
  booktitle={Advances in Cryptology – CRYPTO 2018},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={10991},
  pages={371-406},
  doi={10.1007/978-3-319-96884-1_13},
  author={Ioannis Demertzis and Dimitrios Papadopoulos and Charalampos Papamanthou},
  year=2018
}