Paper 2022/1680

Authenticated Encryption with Key Identification

Julia Len, Cornell Tech
Paul Grubbs, University of Michigan
Thomas Ristenpart, Cornell Tech

Authenticated encryption with associated data (AEAD) forms the core of much of symmetric cryptography, yet the standard techniques for modeling AEAD assume recipients have no ambiguity about what secret key to use for decryption. This is divorced from what occurs in practice, such as in key management services, where a message recipient can store numerous keys and must identify the correct key before decrypting. To date there has been no formal investigation of their security properties or efficacy, and the ad hoc solutions for identifying the intended key deployed in practice can be inefficient and, in some cases, vulnerable to practical attacks. We provide the first formalization of nonce-based AEAD that supports key identification (AEAD-KI). Decryption now takes in a vector of secret keys and a ciphertext and must both identify the correct secret key and decrypt the ciphertext. We provide new formal security definitions, including new key robustness definitions and indistinguishability security notions. Finally, we show several different approaches for AEAD-KI and prove their security.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
key identification authenticated encryption key commitment key robustness
Contact author(s)
jlen @ cs cornell edu
paulgrub @ umich edu
ristenpart @ cornell edu
2022-12-03: approved
2022-12-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Julia Len and Paul Grubbs and Thomas Ristenpart},
      title = {Authenticated Encryption with Key Identification},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1680},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.