Cryptology ePrint Archive: Report 2017/400

A Leakage-Abuse Attack Against Multi-User Searchable Encryption

Cédric Van Rompay and 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.

Category / Keywords: searchable encryption, attack, cryptanalysis

Original Publication (with minor differences): PoPETs Volume 2017, Number 3

Date: received 9 May 2017, last revised 11 May 2017

Contact author: vanrompa at eurecom fr

Available format(s): PDF | BibTeX Citation

Note: Some figures imported as PDF rather than PNG.

Also, removed some LaTeX markup in the eprint abstract

Version: 20170511:085959 (All versions of this report)

Short URL: ia.cr/2017/400

Discussion forum: Show discussion | Start new discussion