Quantum generic attacks on key-alternating Feistel ciphers for shorter keys

Key-alternating Feistel (KAF) cipher, refer to Feistel scheme with round functions of the form F(x circle plus k), where k is the round-key and F is a public random function. This model roughly captures the structures of many famous Feistel ciphers, and the most prominent instance is DES. In order to analyze how KAF cipher can achieve security under simpler and more realistic assumptions from the view of provable security, a kind of KAF cipher is widely studied, which is called KAF cipher for shorter keys. Existing KAF ciphers for shorter keys (SCIS 2021, ASIACRYPT 2018 and ACNS 2020) have been proved to be super pseudorandom permutations (SPRPs) and can achieve birthday bound security. In this paper, we focus on the quantum security of the KAF ciphers for shorter keys. We show that the KAF ciphers for shorter keys are insecure against quantum chosen-plaintext attacks (qCPA). According to our study, the KAF ciphers for shorter keys can be distinguished from random permutation based on Simon's algorithm in polynomial time. We also show that the KAF ciphers for shorter keys with arbitrary rounds are insecure in the qCPA setting. In addition, we propose quantum multi-user distinguishing attacks on the KAF ciphers for shorter keys. The results show that the KAF ciphers for shorter keys can be distinguished from random permutation in polynomial time in the qCPA setting even if either the round function or the number of rounds is unknown.