Cryptology ePrint Archive: Report 2019/624

Nonces are Noticed: AEAD Revisited

Mihir Bellare and Ruth Ng and Björn Tackmann

Abstract: 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).

Category / Keywords: secret-key cryptography / Nonce, Authenticated Encryption, Symmetric Encryption, GCM

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

Date: received 1 Jun 2019, last revised 11 Nov 2019

Contact author: mihir at eng ucsd edu, ring at eng ucsd edu, bta at zurich ibm com

Available format(s): PDF | BibTeX Citation

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.

Version: 20191112:023542 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]