Iterative Block Ciphers from Tweakable Block Ciphers with Long Tweaks

We consider a problem of constructing a secure block cipher from a tweakable block cipher (TBC) with long tweaks. Given a TBC with n-bit blocks and tau n-bit tweaks for tau >= 1, one of the constructions by Minematsu in DCC 2015 shows that a simple iteration of the TBC for 3d rounds yields a block cipher with do-bit blocks that is secure up to 2(dn/2) queries, where d = tau + 1. In this paper, we show three results. 1. Iteration of 3d - 2 rounds is enough for the security up to 2(dn/2) queries, i.e., the security remains the same even if we reduce the number of rounds by two. 2. When the number of queries is limited to 2(n), d + 1 rounds are enough, and with d + l rounds for 1 <= l <= d - 1, the security bound improves as l grows. 3. A d-round construction gives a block cipher secure up to 2(n/2) queries, i.e., it achieves the classical birthday-bound security. Our results show that a block cipher with beyond-birthday-bound (BBB) security (with respect to n) is obtained as low as d + 1 rounds, and we draw the security spectrum of d + l round version in the range of 1 <= l <= d - 1 and l = 2d - 2 for BBB security, and l = 0 for birthday-bound security.