Paper 2017/1060

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

Raphael Bost and Pierre-Alain Fouque


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.

Available format(s)
Publication info
Preprint. MINOR revision.
security definitionsearchable encryptionleakage abuse attacks
Contact author(s)
raphael_bost @ alumni brown edu
2017-10-31: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.