Paper 2016/172

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

Yupeng Zhang, 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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Minor revision. USENIX security 2016
Keywords
seachable encryptionsymmetric key encryption
Contact author(s)
zhangyp @ umd edu
History
2016-06-29: last of 2 revisions
2016-02-22: received
See all versions
Short URL
https://ia.cr/2016/172
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/172,
      author = {Yupeng Zhang and Jonathan Katz and Charalampos Papamanthou},
      title = {All Your Queries Are Belong to Us: The Power of File-Injection Attacks on Searchable Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2016/172},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/172}},
      url = {https://eprint.iacr.org/2016/172}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.