Paper 2019/624

Nonces are Noticed: AEAD Revisited

Mihir Bellare, Ruth Ng, and Björn Tackmann


We draw attention to a gap between theory and usage of nonce-based symmetric encryption, under which the way the former treats nonces can result in violation of privacy in the latter. We bridge the gap with a new treatment of nonce-based symmetric encryption that modifies the syntax (decryption no longer takes a nonce), upgrades the security goal (asking that not just messages, but also nonces, be hidden) and gives simple, efficient schemes conforming to the new definitions. We investigate both basic security (holding when nonces are not reused) and advanced security (misuse resistance, providing best-possible guarantees when nonces are reused).

Note: Added credits and citations. Proofs overhauled and simplified. GCM result improved, dropping blockcipher assumption from strong PRP to PRF. Decomposition theorem generalized. Significant changes over prior full version.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2019
NonceAuthenticated EncryptionSymmetric EncryptionGCM
Contact author(s)
mihir @ eng ucsd edu
ring @ eng ucsd edu
bta @ zurich ibm com
2019-11-12: revised
2019-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Ruth Ng and Björn Tackmann},
      title = {Nonces are Noticed: AEAD Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2019/624},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.