Paper 2024/2049

BBB Secure Large-Tweak TBC from Ideal Block Ciphers

Abstract

At FSE'15, Mennink introduced the concept of designing beyond-birthday bound secure tweakable block cipher from an ideal block cipher. They proposed two tweakable block ciphers $\widetilde{F}[1]$ and $\widetilde{F}[2]$ that accept $n$-bit tweaks using a block cipher with an $n$-bit key and $n$-bit data. Mennink proved that the constructions achieve security up to $2^{2n/3}$ and $2^n$ queries, respectively, assuming the underlying block cipher is ideal. Later, at ASIACRYPT'16, Wang et al. proposed a class of $32$ new tweakable block ciphers derived from $n$-bit ideal block ciphers that achieve optimal security, i.e., security up to $2^n$ queries. The proposed designs by both Mennink and Wang et al. admit only $n$-bit tweaks. In FSE'23, Shen and Standaert proposed a tweakable block cipher $\widetilde{G}2$ that accepts $2n$-bit tweaks and achieves security up to $2^n$ queries. Their construction uses three block cipher calls, which was shown to be optimal for beyond-birthday-bound secure tweakable block ciphers accepting $2n$-bit tweaks. In this paper, we extend this line of research by considering the design of tweakable block ciphers that support $3n$-bit tweaks from an ideal block cipher with affine mixing. 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 $\widetilde{\textsf{G}}3^*$, which leverages three block cipher calls with each key being dependent on the tweak. We demonstrate that $\widetilde{\textsf{G}}3^*$ achieve security up to $2^{2n/3}$ queries. Although primarily of theoretical interest, $\widetilde{\textsf{G}}3^*$ demonstrates that beyond-birthday-bound security for a $3n$-bit tweak can be achieved with only three block-cipher calls, thereby extending the known feasibility frontier for TBC design.Furthermore, we extend this result and propose an optimally secure construction, dubbed $\widetilde{\textsf{G}}3$, 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 $\widetilde{\textsf{G}}r$ that processes $rn$-bit tweaks using $(r+1)$ block cipher invocations with only one tweak-dependent block cipher key. Our experimental evaluation demonstrates that on platforms featuring AES-NI hardware acceleration, \tx{ZMAC} instantiated with $\widetilde{\textsf{G}}_3$ and $\widetilde{\textsf{G}}_4$ (i.e., $\widetilde{\textsf{G}}_r$ with $r=4$) outperforms all existing ideal-cipher-based TBC candidates.