Paper 2020/785

The Memory-Tightness of Authenticated Encryption

Ashrujit Ghoshal, Joseph Jaeger, and Stefano Tessaro


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.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2020
provable securitytime-memory trade-offsmemory-tightness
Contact author(s)
ashrujit @ cs washington edu
2020-06-27: received
Short URL
Creative Commons Attribution


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