Paper 2018/195

Breach-Resistant Structured Encryption

Ghous Amjad, Seny Kamara, and Tarik Moataz

Abstract

Motivated by the problem of data breaches, we formalize a notion of security for dynamic structured encryption (STE) schemes that guarantees security against a snapshot adversary; that is, an adversary that receives a copy of the encrypted structure at various times but does not see the transcripts related to any queries. In particular, we focus on the construction of dynamic encrypted multi-maps which are used to build efficient searchable symmetric encryption schemes, graph encryption schemes and encrypted relational databases. Interestingly, we show that a form of snapshot security we refer to as breach resistance implies previously-studied notions such as a (weaker version) of history independence and write-only obliviousness. Moreover, we initiate the study of dual-secure dynamic STE constructions: schemes that are forward-private against a persistent adversary and breach-resistant against a snapshot adversary. The notion of forward privacy guarantees that updates to the encrypted structure do not reveal their association to any query made in the past. As a concrete instantiation, we propose a new dual-secure dynamic multi-map encryption scheme that outperforms all existing constructions; including schemes that are not dual-secure. Our construction has query complexity that grows with the selectivity of the query and the number of deletes since the client executed a linear-time rebuild protocol which can be de-amortized. We implemented our scheme (with the de-amortized rebuild protocol) and evaluated its concrete efficiency empirically. Our experiments show that it is highly efficient with queries taking less than 1 microsecond per label/value pair.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Searchable EncryptionStructured EncryptionSnapshot SecurityForward Privacy
Contact author(s)
ghous_amjad @ alumni brown edu
History
2022-05-10: revised
2018-02-22: received
See all versions
Short URL
https://ia.cr/2018/195
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/195,
      author = {Ghous Amjad and Seny Kamara and Tarik Moataz},
      title = {Breach-Resistant Structured Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2018/195},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/195}},
      url = {https://eprint.iacr.org/2018/195}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.