Paper 2015/1049

Counter-in-Tweak: Authenticated Encryption Modes for Tweakable Block Ciphers

Thomas Peyrin and Yannick Seurin

Abstract

We propose the Synthetic Counter-in-Tweak (SCT) mode, which turns a tweakable block cipher into a nonce-based authenticated encryption scheme (with associated data). The SCT mode combines in a SIV-like manner a Wegman-Carter MAC inspired from PMAC for the authentication part and a new counter-like mode for the encryption part, with the unusual property that the counter is applied on the tweak input of the underlying tweakable block cipher rather than on the plaintext input. Unlike many previous authenticated encryption modes, SCT enjoys provable security beyond the birthday bound (and even up to roughly $2^n$ tweakable block cipher calls, where $n$ is the block length, when the tweak length is sufficiently large) in the nonce-respecting scenario where nonces are never repeated. In addition, SCT ensures security up to the birthday bound even when nonces are reused, in the strong nonce-misuse resistance sense (MRAE) of Rogaway and Shrimpton (EUROCRYPT 2006). To the best of our knowledge, this is the first authenticated encryption mode that provides at the same time close-to-optimal security in the nonce-respecting scenario and birthday-bound security for the nonce-misuse scenario. While two passes are necessary to achieve MRAE-security, our mode enjoys a number of desirable features: it is simple, parallelizable, it requires the encryption direction only, it is particularly efficient for small messages compared to other nonce-misuse resistant schemes (no precomputation is required) and it allows incremental update of associated data.

Note: An abridged version appears in the proceedings of CRYPTO 2016. This is the full version. The revised version of May 24, 2016 contains an improved version of Theorem 1 and some minor editorial changes. The revised version of May 27, 2016 contains the additional reference [ST13]. The revised version of May 22, 2017 contains a simpler proof for Lemma 4 leading to a better bound in Theorem 1.