Paper 2020/785

The Memory-Tightness of Authenticated Encryption

Ashrujit Ghoshal, Joseph Jaeger, and Stefano Tessaro

Abstract

This paper initiates the study of the provable security of authenticated encryption (AE) in the memory-bounded setting. Recent works – Tessaro and Thiruvengadam (TCC '18), Jaeger and Tessaro (EUROCRYPT '19), and Dinur (EUROCRYPT '20) – focus on confidentiality, and look at schemes for which trade-offs between the attacker's memory and its data complexity are inherent. Here, we ask whether these results and techniques can be lifted to the full AE setting, which additionally asks for integrity. We show both positive and negative results. On the positive side, we provide tight memory-sensitive bounds for the security of GCM and its generalization, CAU (Bellare and Tackmann, CRYPTO '16). Our bounds apply to a restricted case of AE security which abstracts the deployment within protocols like TLS, and rely on a new memory-tight reduction to corresponding restricted notions of confidentiality and integrity. In particular, our reduction uses an amount of memory which linearly depends on that of the given adversary, as opposed to only imposing a constant memory overhead as in earlier works (Auerbach et al., CRYPTO '17). On the negative side, we show that a large class of black-box reductions cannot generically lift confidentiality and integrity security to a joint definition of AE security in a memory-tight way.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2020
Keywords
provable securitytime-memory trade-offsmemory-tightness
Contact author(s)
ashrujit @ cs washington edu
History
2020-06-27: received
Short URL
https://ia.cr/2020/785
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/785,
      author = {Ashrujit Ghoshal and Joseph Jaeger and Stefano Tessaro},
      title = {The Memory-Tightness of Authenticated Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2020/785},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/785}},
      url = {https://eprint.iacr.org/2020/785}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.