Paper 2021/425

Related-Key Analysis of Generalized Feistel Networks with Expanding Round Functions

Yuqing Zhao, Wenqi Yu, and Chun Guo

Abstract

We extend the prior provable related-key security analysis of (generalized) Feistel networks (Barbosa and Farshim, FSE 2014; Yu et al., Inscrypt 2020) to the setting of expanding round functions, i.e., n-bit to m-bit round functions with n < m. This includes Expanding Feistel Networks (EFNs) that purely rely on such expanding round functions, and Alternating Feistel Networks (AFNs) that alternate expanding and contracting round functions. We show that, when two independent keys $K_1,K_2$ are alternatively used in each round, (a) $2\lceil\frac{m}{n}\rceil+2$ rounds are sufficient for related-key security of EFNs, and (b) a constant number of 4 rounds are sufficient for related-key security of AFNs. Our results complete the picture of provable related-key security of GFNs, and provide additional theoretical support for the AFN-based NIST format preserving encryption standards FF1 and FF3.