Cryptology ePrint Archive: Report 2019/1495

Tight Security of Cascaded LRW2

Ashwin Jha and Mridul Nandi

Abstract: At CRYPTO '12, Landecker et al. introduced the cascaded LRW2 (or CLRW2) construction, and proved that it is a secure tweakable block cipher up to roughly $ 2^{2n/3} $ queries. Recently, Mennink presented a distinguishing attack on CLRW2 in $ 2n^{1/2}2^{3n/4} $ queries. In the same paper, he discussed some non-trivial bottlenecks in proving tight security bound, i.e. security up to $ 2^{3n/4} $ queries. Subsequently, he proved security up to $ 2^{3n/4} $ queries for a variant of CLRW2 using $ 4 $-wise independent AXU assumption and the restriction that each tweak value occurs at most $ 2^{n/4} $ times. Moreover, his proof relies on a version of mirror theory which is yet to be publicly verified. In this paper, we resolve the bottlenecks in Mennink's approach and prove that the original CLRW2 is indeed a secure tweakable block cipher up to roughly $ 2^{3n/4} $ queries. To do so, we develop two new tools: First, we give a probabilistic result that provides improved bound on the joint probability of some special collision events; Second, we present a variant of Patarin's mirror theory in tweakable permutation settings with a self-contained and concrete proof. Both these results are of generic nature, and can be of independent interests. To demonstrate the applicability of these tools, we also prove tight security up to roughly $ 2^{3n/4} $ queries for a variant of DbHtS, called DbHtS-p, that uses two independent universal hash functions.

Category / Keywords: secret-key cryptography / LRW2, CLRW2, tweakable block cipher, mirror theory

Original Publication (with minor differences): IACR-JOC-2020
DOI:
10.1007/s00145-020-09347-y

Date: received 29 Dec 2019, last revised 14 May 2020

Contact author: ashwin jha1991 at gmail com

Available format(s): PDF | BibTeX Citation

Note: Added a reference to a concurrent work that proves tight security of PMAC+ and LightMAC+.

Version: 20200515:045823 (All versions of this report)

Short URL: ia.cr/2019/1495


[ Cryptology ePrint archive ]