Paper 2017/400

A Leakage-Abuse Attack Against Multi-User Searchable Encryption

Cédric Van Rompay, Refik Molva, and Melek Önen


Searchable Encryption (SE) allows a user to upload data to the cloud and to search it in a remote fashion while preserving the privacy of both the data and the queries. Recent research results describe attacks on SE schemes using the access pattern, denoting the ids of documents matching search queries, which most SE schemes reveal during query processing. However SE schemes usually leak more than just the access pattern, and this extra leakage can lead to attacks (much) more harmful than the ones using basic access pattern leakage only. We remark that in the special case of Multi-User Searchable Encryption (MUSE), where many users upload and search data in a cloud-based infrastructure, a large number of existing solutions have a common leakage in addition to the well-studied access pattern leakage. We show that this seemingly small extra leakage allows a very simple yet powerful attack, and that the privacy degree of the affected schemes have been overestimated. We also show that this new vulnerability affects existing software. Finally we formalize the newly identified leakage profile and show how it relates to previously defined ones.

Note: Some figures imported as PDF rather than PNG. Also, removed some LaTeX markup in the eprint abstract

Available format(s)
Publication info
Published elsewhere. MINOR revision.PoPETs Volume 2017, Number 3
searchable encryptionattackcryptanalysis
Contact author(s)
vanrompa @ eurecom fr
2017-05-11: revised
2017-05-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Cédric Van Rompay and Refik Molva and Melek Önen},
      title = {A Leakage-Abuse Attack Against Multi-User Searchable Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2017/400},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.