New Related-Tweakey Boomerang Attacks and Distinguishers on Deoxys-BC

Deoxys-BC is the primitive tweakable block cipher of the Deoxys family of authenticated encryption schemes. Based on existing related-tweakey boomerang distinguishers, this paper improves the boomerang attacks on 11-round Deoxys-BC-256 and 13-round Deoxys-BC-384 by the optimized key guessing and the precomputation technique. It transfers a part of subtweakey guess in the key-recovery phase to the precomputation resulting in a significant reduction of the overall time complexity. For 11-round Deoxys-BC-256, we give a related-tweakey boomerang attack with time/data/memory complexities of 2^218.6/2^125.7/2^125.7, and give another attack with the less time complexity of 2^215.8 and memory complexity of 2^120 when the adversary has access to the full codebook. For 13-round Deoxys-BC-384, we give a related-tweakey boomerang attack with time/data/memory complexities of 2^k-96+2^157.5/2^120.4/2^113. For the key size k=256, it reduces the time complexity by a factor of 2^31 compared with the previous 13-round boomerang attack. In addition, we present two new related-tweakey boomerang distinguishers on 11-round Deoxys-BC-384 with the same probability as the best previous distinguisher.