Cryptology ePrint Archive: Report 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.
Category / Keywords: secret-key cryptography / authenticated encryption, tweakable block cipher, nonce-misuse resistance, beyond-birthday-bound security, CAESAR competition
Original Publication (with major differences): IACR-CRYPTO-2016
Date: received 28 Oct 2015, last revised 27 May 2016
Contact author: yannick seurin at m4x org
Available format(s): PDF | BibTeX Citation
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].
Version: 20160527:150609 (All versions of this report)
Short URL: ia.cr/2015/1049
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]