Cryptology ePrint Archive: Report 2016/062

Verifiable Dynamic Symmetric Searchable Encryption: Optimality and Forward Security

Raphael Bost and Pierre-Alain Fouque and David Pointcheval

Abstract: Symmetric Searchable Encryption (SSE) is a very efficient and practical way for data owners to out- source storage of a database to a server while providing privacy guarantees. Such SSE schemes enable clients to encrypt their database while still performing queries for retrieving documents matching some keyword. This functionality is interesting to secure cloud storage, and efficient schemes have been de- signed in the past. However, security against malicious servers has been overlooked in most previous constructions and these only addressed security against honest-but-curious servers. In this paper, we study and design the first efficient SSE schemes provably secure against mali- cious servers. First, we give lower bounds on the complexity of such verifiable SSE schemes. Then, we construct generic solutions matching these bounds using efficient verifiable data structures. Finally, we modify an existing SSE scheme that also provides forward secrecy of search queries, and make it prov- ably secure against active adversaries, without increasing the computational complexity of the original scheme.

Category / Keywords: cryptographic protocols / symmetric searchable encryption, provable security, secret-key cryptography

Date: received 24 Jan 2016, last revised 28 Jan 2016

Contact author: raphael_bost at alumni brown edu

Available format(s): PDF | BibTeX Citation

Version: 20160128:185817 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]