International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Authenticated Encryption with Key Identification

Julia Len , Cornell Tech
Paul Grubbs , University of Michigan
Thomas Ristenpart , Cornell Tech
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
Abstract: 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. Ad hoc solutions for identifying the intended key are deployed in practice, but these techniques can be inefficient and, in some cases, have even led to practical attacks. Notably, to date there has been no formal investigation of their security properties or efficacy. We fill this gap by providing 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.
Video from ASIACRYPT 2022
  title={Authenticated Encryption with Key Identification},
  author={Julia Len and Paul Grubbs and Thomas Ristenpart},