Paper 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.

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

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in JOC 2020
DOI
10.1007/s00145-020-09347-y
Keywords
LRW2CLRW2tweakable block ciphermirror theory
Contact author(s)
ashwin jha1991 @ gmail com
History
2020-05-15: revised
2019-12-30: received
See all versions
Short URL
https://ia.cr/2019/1495
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1495,
      author = {Ashwin Jha and Mridul Nandi},
      title = {Tight Security of Cascaded LRW2},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1495},
      year = {2019},
      doi = {10.1007/s00145-020-09347-y},
      note = {\url{https://eprint.iacr.org/2019/1495}},
      url = {https://eprint.iacr.org/2019/1495}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.