Cryptology ePrint Archive: Report 2016/172

All Your Queries Are Belong to Us: The Power of File-Injection Attacks on Searchable Encryption

Yupeng Zhang and Jonathan Katz and Charalampos Papamanthou

Abstract: The goal of searchable encryption (SE) is to enable a client to execute searches over encrypted files stored on an untrusted server while ensuring some measure of privacy for both the encrypted files and the search queries. Research has focused on developing efficient SE schemes at the expense of allowing some small, well-characterized "(information) leakage" to the server about the files and/or the queries. The practical impact of this leakage, however, remains unclear.

We thoroughly study file-injection attacks--in which the server sends files to the client that the client then encrypts and stores--on the query privacy of single-keyword and conjunctive SE schemes. We show such attacks can reveal the client's queries in their entirety using very few injected files, even for SE schemes having low leakage. We also demonstrate that natural countermeasures for preventing file-injection attacks can be easily circumvented. Our attacks outperform prior work significantly in terms of their effectiveness as well as in terms of their assumptions about the attacker's prior knowledge.

Category / Keywords: applications / seachable encryption, symmetric key encryption

Original Publication (with minor differences): USENIX security 2016

Date: received 19 Feb 2016, last revised 28 Jun 2016

Contact author: zhangyp at umd edu

Available format(s): PDF | BibTeX Citation

Version: 20190217:224315 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]