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: ia.cr/2016/062
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]