Cryptology ePrint Archive: Report 2018/484

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

Chun Guo and Olivier Pereira and Thomas Peters and Fran├žois-Xavier Standaert

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

Category / Keywords: secret-key cryptography / Authenticated encryption, leakage resilience, nonce robustness, leveled implementation.

Original Publication (with major differences): LATINCRYPT 2019 (to appear)

Date: received 21 May 2018, last revised 11 Jul 2019

Contact author: chun guo at uclouvain be

Available format(s): PDF | BibTeX Citation

Note: The extended version of the accepted paper.

Version: 20190711:105233 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]