Paper 2024/2049

BBB Secure Arbitrary Length Tweak TBC from n-bit Block Ciphers

Abstract

At FSE'15, Mennink introduced the concept of designing beyond-the-birthday bound secure tweakable block cipher from an ideal block cipher. They proposed two tweakable block ciphers $$ and $$ that accepts $$-bit tweak using a block cipher of $$-bit key and $$-bit data. Mennink proved that the constructions achieve security up to $$ and $$ queries, respectively, assuming the underlying block cipher is ideal. Later, at ASIACRYPT'16, Wang et al. proposed a class of $$ new tweakable block ciphers derived from $$-bit ideal block ciphers that achieve optimal security, i.e., security up to $$ queries. The proposed designs by both Mennink and Wang et al. admit only $$-bit tweaks. In FSE'23, Shen and Standaert proposed a tweakable block cipher $$ that accepts $$-bit tweaks and achieves security up to $$ queries. Their construction uses three block cipher calls, which was shown to be optimal for beyond-birthday-bound secure tweakable block ciphers accepting $$-bit tweaks. In this paper, we extend this line of research and consider designing tweakable block cipher supporting $$-bit tweaks from ideal block cipher. First, we show that there is a generic birthday-bound distinguishing attack on any such design with three block cipher calls if any of the block cipher keys are tweak-independent. We then propose a tweakable block cipher $$, which leverages three block cipher calls with each key being dependent on tweak. We demonstrate that $$ achieve security up to $$ queries. Furthermore, we extend this result and propose an optimally secure construction, dubbed $$, that uses four ideal block cipher calls with only one tweak-dependent key. Finally, we generalize this and propose an optimally secure tweakable block cipher $$ that processes $$-bit tweaks using $$ block cipher invocations with only one tweak-dependent block cipher key. Our experimental evaluation asserts that ZMAC instantiated with $$ and $$ (i.e., $$ with $$) performs better than all the existing ideal cipher based TBC candidates.