CTET+: A Beyond-Birthday-Bound Secure Tweakable Enciphering Scheme Using a Single Pseudorandom Permutation

Abstract

In this work, we propose a construction of 2-round tweakable substitutionpermutation networks using a single secret S-box. This construction is based on non-linear permutation layers using independent round keys, and achieves security beyond the birthday bound in the random permutation model. When instantiated with an n-bit block cipher with ωn-bit keys, the resulting tweakable block cipher, dubbed CTET⁺, can be viewed as a tweakable enciphering scheme that encrypts ωκ-bit messages for any integer ω ≥ 2 using 5n + κ-bit keys and n-bit tweaks, providing 2n/3-bit security.
Compared to the 2-round non-linear SPN analyzed in [CDK⁺18], we both minimize it by requiring a single permutation, and weaken the requirements on the middle linear layer, allowing better performance. As a result, CTET⁺ becomes the first tweakable enciphering scheme that provides beyond-birthday-bound security using a single permutation, while its efficiency is still comparable to existing schemes including AES-XTS, EME, XCB and TET. Furthermore, we propose a new tweakable enciphering scheme, dubbed AES₆-CTET⁺, which is an actual instantiation of CTET⁺ using a reduced round AES block cipher as the underlying secret S-box. Extensive
cryptanalysis of this algorithm allows us to claim 127 bits of security.
Such tweakable enciphering schemes with huge block sizes become desirable in the context of disk encryption, since processing a whole sector as a single block significantly worsens the granularity for attackers when compared to, for example, AES-XTS, which treats every 16-byte block on the disk independently. Besides, as a huge amount of data is being stored and encrypted at rest under many different keys in clouds, beyond-birthday-bound security will most likely become necessary in the short term.