Paper 2020/1073

Tight Security Analysis of 3-Round Key-Alternating Cipher with A Single Permutation

Yusai Wu, Liqing Yu, Zhenfu Cao, and Xiaolei Dong

Abstract

The tight security bound of the Key-Alternating Cipher (KAC) construction whose round permutations are independent from each other has been well studied. Then a natural question is how the security bound will change when we use fewer permutations in a KAC construction. In CRYPTO 2014, Chen et al. proved that 2-round KAC with a single permutation (2KACSP) has the same security level as the classic one (i.e., 2-round KAC). But we still know little about the security bound of incompletely-independent KAC constructions with more than 2 rounds. In this paper,we will show that a similar result also holds for 3-round case. More concretely, we prove that 3-round KAC with a single permutation (3KACSP) is secure up to $\varTheta(2^{\frac{3n}{4}})$ queries, which also caps the security of 3-round KAC. To avoid the cumbersome graphical illustration used in Chen et al.'s work, a new representation is introduced to characterize the underlying combinatorial problem. Benefited from it, we can handle the knotty dependence in a modular way, and also show a plausible way to study the security of $r$KACSP. Technically, we abstract a type of problems capturing the intrinsic randomness of $r$KACSP construction, and then propose a high-level framework to handle such problems. Furthermore, our proof techniques show some evidence that for any $r$, $r$KACSP has the same security level as the classic $r$-round KAC in random permutation model.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2020
Keywords
KACKACSPDependenceProvable SecurityIndistinguishabilityRandom Permutation Model
Contact author(s)
yusaiwu @ 126 com
lqyups @ 126 com
zfcao @ sei ecnu edu cn
dong-xl @ sei ecnu edu cn
History
2020-11-30: last of 4 revisions
2020-09-09: received
See all versions
Short URL
https://ia.cr/2020/1073
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1073,
      author = {Yusai Wu and Liqing Yu and Zhenfu Cao and Xiaolei Dong},
      title = {Tight Security Analysis of 3-Round Key-Alternating Cipher with A Single Permutation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1073},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1073}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.