Paper 2016/062

Verifiable Dynamic Symmetric Searchable Encryption: Optimality and Forward Security

Raphael Bost, Pierre-Alain Fouque, and David Pointcheval


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
symmetric searchable encryptionprovable securitysecret-key cryptography
Contact author(s)
raphael_bost @ alumni brown edu
2016-01-28: revised
2016-01-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Raphael Bost and Pierre-Alain Fouque and David Pointcheval},
      title = {Verifiable Dynamic Symmetric Searchable Encryption: Optimality and Forward Security},
      howpublished = {Cryptology ePrint Archive, Paper 2016/062},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.