Paper 2017/400

A Leakage-Abuse Attack Against Multi-User Searchable Encryption

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

Abstract

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

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. PoPETs Volume 2017, Number 3
Keywords
searchable encryptionattackcryptanalysis
Contact author(s)
vanrompa @ eurecom fr
History
2017-05-11: revised
2017-05-11: received
See all versions
Short URL
https://ia.cr/2017/400
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/400,
      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{https://eprint.iacr.org/2017/400}},
      url = {https://eprint.iacr.org/2017/400}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.