### Security-Efficiency Tradeoffs in Searchable Encryption -- Lower Bounds and Optimal Constructions

Raphael Bost and Pierre-Alain Fouque

##### Abstract

Besides their security, the efficiency of searchable encryption schemes is a major criteria when it comes to their adoption: in order to replace an unencrypted database by a more secure construction, it must scale to the systems which rely on it. Unfortunately, the relationship between the efficiency and the security of searchable encryption has not been widely studied, and the minimum cost of some crucial security properties is still unclear. In this paper, we present new lower bounds on the tradeoffs between the size of the client state, the efficiency and the security for searchable encryption schemes. These lower bounds target two kinds of schemes: schemes hiding the repetition of search queries, and forward-private dynamic schemes, for which updates are oblivious. We also show that these lower bounds are tight, by either constructing schemes matching them, or by showing that even a small increase in the amount of leaked information allows for constructing schemes breaking the lower bounds.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. MINOR revision.PoPETS 2019
DOI
10.2478/popets-2019-0062
Keywords
searchable encryptionlower bound
Contact author(s)
raphael_bost @ alumni brown edu
History
2019-08-02: revised
See all versions
Short URL
https://ia.cr/2019/693

CC BY

BibTeX

@misc{cryptoeprint:2019/693,
author = {Raphael Bost and Pierre-Alain Fouque},
title = {Security-Efficiency Tradeoffs in Searchable Encryption -- Lower Bounds and Optimal Constructions},
howpublished = {Cryptology ePrint Archive, Paper 2019/693},
year = {2019},
doi = {10.2478/popets-2019-0062},
note = {\url{https://eprint.iacr.org/2019/693}},
url = {https://eprint.iacr.org/2019/693}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.