Cryptology ePrint Archive: Report 2017/805

Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives

Raphael Bost and Brice Minaud and Olga Ohrimenko

Abstract: Using dynamic Searchable Symmetric Encryption, a user with limited storage resources can securely outsource a database to an untrusted server, in such a way that the database can still be searched and updated efficiently. For these schemes, it would be desirable that updates do not reveal any information a priori about the modifications they carry out, and that deleted results remain inaccessible to the server a posteriori. If the first property, called forward privacy, has been the main motivation of recent works, the second one, backward privacy, has been overlooked. In this paper, we study for the first time the notion of backward privacy for searchable encryption. After giving formal definitions for different flavors of backward privacy, we present several schemes achieving both forward and backward privacy, with various efficiency trade-offs. Our constructions crucially rely on primitives such as constrained pseudo-random functions and puncturable encryption schemes. Using these advanced cryptographic primitives allows for a fine-grained control of the power of the adversary, preventing her from evaluating functions on selected inputs, or decrypting specific ciphertexts. In turn, this high degree of control allows our SSE constructions to achieve the stronger forms of privacy outlined above. As an example, we present a framework to construct forward-private schemes from range-constrained pseudo-random functions. Finally, we provide experimental results for implementations of our schemes, and study their practical efficiency.

Category / Keywords: applications / symmetric searchable encryption, provable security, implementation

Original Publication (in the same form): 24th ACM Conference on Computer and Communications Security (CCS), 2017

Date: received 27 Aug 2017, last revised 27 Aug 2017

Contact author: raphael_bost at alumni brown edu

Available format(s): PDF | BibTeX Citation

Version: 20170828:151339 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]