Paper 2018/484

Authenticated Encryption with Nonce Misuse and Physical Leakages: Definitions, Separation Results, and Leveled Constructions

Chun Guo, Olivier Pereira, Thomas Peters, and François-Xavier Standaert


We propose definitions and constructions of authenticated encryption (AE) schemes that offer security guarantees even in the presence of nonce misuse and side-channel leakages. This is part of an important ongoing effort to make AE more robust, while preserving appealing efficiency properties. Our definitions consider an adversary enhanced with the leakages of all the computations of an AE scheme, together with the possibility to misuse nonces, be it during all queries (in the spirit of misuse-resistance), or only during training queries (in the spirit of misuse-resilience recently introduced by Ashur et al.). These new definitions offer various insights on the effect of leakages in the security landscape. In particular, we show that, in contrast with the black-box setting, leaking variants of INT-CTXT and IND-CPA security do not imply a leaking variant IND-CCA security, and that leaking variants of INT-PTXT and IND-CCA do not imply a leaking variant of INT-CTXT. Eventually, we propose first instances of modes of operations that satisfy our definitions. In order to optimize their efficiency, we aim at modes that support "leveled implementations" such that the encryption and decryption operations require the use of a small constant number of evaluations of an expensive and heavily protected component, while the bulk of the computations can be performed by cheap and weakly protected block cipher implementations.

Note: The extended version of the accepted paper.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. MAJOR revision.LATINCRYPT 2019 (to appear)
Authenticated encryptionleakage resiliencenonce robustnessleveled implementation.
Contact author(s)
chun guo @ uclouvain be
2019-07-11: last of 2 revisions
2018-05-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chun Guo and Olivier Pereira and Thomas Peters and François-Xavier Standaert},
      title = {Authenticated Encryption with Nonce Misuse and Physical Leakages: Definitions, Separation Results, and Leveled Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/484},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.