Paper 2017/1060

Thwarting Leakage Abuse Attacks against Searchable Encryption -- A Formal Approach and Applications to Database Padding

Raphael Bost and Pierre-Alain Fouque

Abstract

After the development of practical searchable encryption constructions, allowing for secure searches over an encrypted dataset outsourced to an untrusted server, at the expense of leaking some information to the server, many new attacks have recently been developed, targeting this leakage in order to break the confidentiality of the dataset or of the queries, through leakage abuse attacks. These works helped to understand the importance of considering leakage when analyzing the security of searchable encryption schemes, but did not explain why these attacks were so powerful despite the existence of rigorous security definitions and proofs, or how they could be efficiently and provably mitigated. This work addresses these questions by first proposing an analysis of existing leakage abuse attacks and a way to capture them in new security definitions. These new definitions also help us to devise a way to thwart these attacks and we apply it to the padding of datasets, in order to hide the number of queries’ results, and to provide provable security of some schemes with specific leakage profile against some common classes of leakage abuse attacks. Finally, we give experimental evidence that our countermeasures can be implemented efficiently, and easily applied to existing searchable encryption schemes.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. MINOR revision.
Keywords
security definitionsearchable encryptionleakage abuse attacks
Contact author(s)
raphael_bost @ alumni brown edu
History
2017-10-31: received
Short URL
https://ia.cr/2017/1060
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1060,
      author = {Raphael Bost and Pierre-Alain Fouque},
      title = {Thwarting Leakage Abuse Attacks against Searchable Encryption --  A Formal Approach and Applications to Database Padding},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1060},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1060}},
      url = {https://eprint.iacr.org/2017/1060}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.