Cryptology ePrint Archive: Report 2020/785

The Memory-Tightness of Authenticated Encryption

Ashrujit Ghoshal and 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.

Category / Keywords: secret-key cryptography / provable security, time-memory trade-offs, memory-tightness

Original Publication (with major differences): IACR-CRYPTO-2020

Date: received 24 Jun 2020

Contact author: ashrujit at cs washington edu

Available format(s): PDF | BibTeX Citation

Version: 20200627:184807 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]