Paper 2020/288

Secure Key-Alternating Feistel Ciphers Without Key Schedule

Yaobin Shen, Hailun Yan, Lei Wang, and Xuejia Lai

Abstract

Light key schedule has found many applications in lightweight blockciphers, e.g. LED, PRINTcipher and LBlock. In this paper, we study an interesting question of how to design a as light as possible key schedule from the view of provable security and revisit the four-round key-alternating Feistel cipher by Guo and Wang in Asiacrypt 18. We optimize the construction by Guo and Wang and propose a four-round key-alternating Feistel cipher with an ultra-light (in fact non-existent) key schedule. We prove our construction retain the same security level as that of Guo and Wang's construction. To the best of our knowledge, this is the first provably secure key-alternating Feistel cipher using identical round function and one n-bit master key but with ultra-light (non-existent) key schedule. We also investigate whether the same refinement works for the three-round key-alternating Feistel cipher. This time we show a distinguishing attack on such three-round construction with only four encryption queries. On the positive side, we prove that three-round key-alternating Feistel cipher with a suitable key schedule is a pseudorandom permutation. This is also the first provable-security result for three-round key-alternating Feistel cipher.