Paper 2013/163

Search Pattern Leakage in Searchable Encryption: Attacks and New Construction

Chang Liu, Liehuang Zhu, Mingzhong Wang, and Yu-an Tan

Abstract

Searching on remote encrypted data (commonly known as \textit{searchable encryption}) has become an important issue in secure data outsourcing, since it allows users to outsource encrypted data to an untrusted third party while maintains the capability of keyword search on the data. Searchable encryption can be achieved using the classical method called oblivious RAM, but the resultant schemes are too inefficient to be applied in the real-world scenarios (e.g., cloud computing). Recently, a number of efficient searchable encryption schemes have been proposed under weaker security guarantees. Such schemes, however, still leak statistical information about the users' search pattern. In this paper, we first present two concrete attack methods to show that the search pattern leakage will result in such a situation: an adversary who has some auxiliary knowledge can uncover the underlying keywords of user queries. To address this issue, we then develop a grouping-based construction (GBC) to transform an existing searchable encryption scheme to a new scheme hiding the search pattern. Finally, experiments based on the real-world dataset demonstrate the effectiveness of our attack methods and the feasibility of our construction.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Information Sciences
DOI
10.1016/j.ins.2013.11.021
Keywords
search patternsearchable encryptioncloud computingfake querygrouping-based construction
Contact author(s)
changliu bit @ gmail com
History
2013-12-04: revised
2013-03-26: received
See all versions
Short URL
https://ia.cr/2013/163
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/163,
      author = {Chang Liu and Liehuang Zhu and Mingzhong Wang and Yu-an Tan},
      title = {Search Pattern Leakage in Searchable Encryption: Attacks and New Construction},
      howpublished = {Cryptology ePrint Archive, Paper 2013/163},
      year = {2013},
      doi = {10.1016/j.ins.2013.11.021},
      note = {\url{https://eprint.iacr.org/2013/163}},
      url = {https://eprint.iacr.org/2013/163}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.