Paper 2017/1158

Oblivious Dynamic Searchable Encryption via Distributed PIR and ORAM

Thang Hoang, Attila A. Yavuz, Betul F. Durak, and Jorge Guajardo


Dynamic Searchable Symmetric Encryption (DSSE) allows to delegate search/update operations over encrypted data via an encrypted index. However, DSSE is known to be vulnerable against statistical inference attacks, which exploits information leakages from access patterns on encrypted index and files. Although generic Oblivious Random Access Machine (ORAM) can hide access patterns, it has been shown to be extremely costly to be directly used in DSSE setting. We developed a series of Oblivious Distributed DSSE schemes that we refer to as \ODSE, which achieve oblivious access on the encrypted index with a high security and improved efficiency over the use of generic ORAM. Specifically, \ODSE schemes are 3-57 $\times$ faster than applying the state-of-the-art generic ORAMs on encrypted dictionary index in real network settings. One of the proposed \ODSE schemes offers desirable security guarantees such as information-theoretic security with robustness against malicious servers. These properties are achieved by exploiting some of the unique characteristics of searchable encryption and encrypted index, which permits us to harness the computation and communication efficiency of multi-server PIR and Write-Only ORAM simultaneously. We fully implemented \ODSE and conducted extensive experiments to assess the performance of our proposed schemes in a real cloud environment.

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

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.IFIP DBSec 2018 (extended version)
Privacy Enhancing TechnologiesSearchable EncryptionOblivious Random Access Machine (ORAM)Private Information Retrieval
Contact author(s)
hoangmin @ oregonstate edu
2018-08-04: last of 3 revisions
2017-11-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thang Hoang and Attila A.  Yavuz and Betul F.  Durak and Jorge Guajardo},
      title = {Oblivious Dynamic Searchable Encryption via Distributed PIR and ORAM},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1158},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.