Cryptology ePrint Archive: Report 2017/749

Searchable Encryption with Optimal Locality: Achieving Sublogarithmic Read Efficiency

Ioannis Demertzis and Dimitrios Papadopoulos and 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.

Category / Keywords: foundations / Searchable Encryption, Locality, Read Efficiency

Date: received 2 Aug 2017, last revised 3 Nov 2017

Contact author: cpap at umd edu

Available format(s): PDF | BibTeX Citation

Version: 20171103:155509 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]