Paper 2023/1242

Cascading Four Round LRW1 is Beyond Birthday Bound Secure

Abstract

In CRYPTO'02, Liskov et al. have introduced a new symmetric key primitive called tweakable block cipher. They have proposed two constructions of designing a tweakable block cipher from block ciphers. The first proposed construction is called $$ and the second proposed construction is called $$. Although, $$ has been extended in later works to provide beyond birthday bound security (e.g., cascaded $$ in CRYPTO'12 by Landecker et al.), but extension of the $$ has received no attention until the work of Bao et al. in EUROCRYPT'20, where the authors have shown that one round extension of $$, i.e., masking the output of $$ with the given tweak and then re-encrypting it with the same block cipher, gives security up to $$ queries. Recently, Khairallah has shown a birthday bound distinguishing attack on the construction and hence invalidated the security claim of Bao et al. This has led to the open research question, that {\em how many round are required for cascading $$ to achieve beyond birthday bound security ?} In this paper, we have shown that cascading $$ up to four rounds is sufficient for ensuring beyond the birthday bound security. In particular, we have shown that $$ provides security up to $$ queries. Security analysis of our construction is based on the recent development of the mirror theory technique for tweakable random permutations under the framework of the Expectation Method.

Note: The previous version of this work provides $$-bit security of $$. In this version, we have improved the security up to $$-bit.