International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Yusai Wu
Liqing Yu
Zhenfu Cao
Xiaolei Dong
Download:
DOI: 10.1007/978-3-030-64837-4_22
Search ePrint
Search Google
Abstract: The tight security bound of the KAC (Key-Alternating Cipher) 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 Θ(23n4) 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 rKACSP. Technically, we abstract a type of problems capturing the intrinsic randomness of rKACSP construction, and then propose a high-level framework to handle such problems. Furthermore, our proof techniques show some evidence that for any r, rKACSP has the same security level as the classic r-round KAC in random permutation model.
Video from ASIACRYPT 2020
BibTeX
@article{asiacrypt-2020-30676,
  title={Tight Security Analysis of 3-Round Key-Alternating Cipher with A Single Permutation},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  publisher={Springer},
  doi={10.1007/978-3-030-64837-4_22},
  author={Yusai Wu and Liqing Yu and Zhenfu Cao and Xiaolei Dong},
  year=2020
}