Paper 2017/1237

A High-Security Searchable Encryption Framework for Privacy-Critical Cloud Storage Services

Thang Hoang, Attila A. Yavuz, and Jorge Guajardo


Searchable encryption has received a significant attention from the research community with various constructions being proposed, each achieving asymptotically optimal complexity for specific metrics (e.g., search, update). Despite their elegancy, the recent attacks and deployment efforts have shown that the optimal asymptotic complexity might not always imply practical performance, especially if the application demands a high privacy. Hence, there is a significant need for searchable encryption frameworks that capture the recent attacks with actual deployments on cloud infrastructures to assess the practicality under realistic settings. In this article, we introduce a new Dynamic Searchable Symmetric Encryption (DSSE) framework called Incidence Matrix (IM)-DSSE, which achieves a high level of privacy, efficient search/update, and low client storage with actual deployments on real cloud settings. We harness an incidence matrix along with two hash tables to create an encrypted index, on which both search and update operations can be performed effectively with minimal information leakage. This simple set of data structures surprisingly offers a high level of DSSE security while at the same time achieving practical performance. Specifically, IM-DSSE achieves forward privacy, backward privacy and size-obliviousness properties simultaneously. We also create several DSSE variants, each offering different trade-offs (e.g., security, computation) that are suitable for different cloud applications and infrastructures. Our framework was fully-implemented and its performance was rigorously evaluated on a real cloud system (Amazon EC2). Our experimental results confirm that IM-DSSE is highly practical even when deployed on mobile phones with a large outsourced dataset. Finally, we have released our IM-DSSE framework as an open-source library for a wide development and adaptation.

Note: The full implementation of this paper can be found at

Available format(s)
Cryptographic protocols
Publication info
Privacy-enhancing technologiesprivate cloud servicesdynamic searchable symmetric encryption
Contact author(s)
hoangmin @ oregonstate edu
2017-12-26: last of 2 revisions
2017-12-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thang Hoang and Attila A.  Yavuz and Jorge Guajardo},
      title = {A High-Security Searchable Encryption Framework for Privacy-Critical Cloud Storage Services},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1237},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.