Using dynamic Searchable Symmetric Encryption, a user with limited storage resources can securely outsource a database to an untrusted server, so that the database can still be searched and updated efficiently. For such dynamic schemes, it would be desirable that updates do not reveal any information a priori on the modifications, and that deleted results remain unaccessible to the server a posteriori. If the first property, called forward privacy, has been the main motivation of recent works, the second one, the 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 of different flavors of backward privacy, we present several schemes achieving both forward and backward privacy, with different efficiency tradeoffs.

To design these schemes, we used constrained pseudo-random functions and puncturable encryption. These evolved cryptographic primitives allows for a finer-grained control of the power of the adversary, preventing him from evaluating functions on some inputs, or from decrypting some ciphertexts. For example, we present a framework to construct forward private schemes from range-constrained pseudo-random functions.

Finally, we implemented these schemes and we study their practical efficiency.