Paper 2026/1057

Computer-Aided Proof for Extended Generalized Feistel Networks

, School of Cyber Science and Technology, Shandong University, Qingdao, China, State Key Laboratory of Cryptography and Digital Economy Security, Shandong University, Qingdao, 266237, China, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China

Chun Guo, School of Cyber Science and Technology, Shandong University, Qingdao, China, State Key Laboratory of Cryptography and Digital Economy Security, Shandong University, Qingdao, 266237, China, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China

Muzhou Li, School of Cryptologic Science and Engineering, Shandong University, Jinan, China, State Key Laboratory of Cryptography and Digital Economy Security, Shandong University, Qingdao, 266237, China, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China, Quancheng Laboratory, Jinan, 250103, China

Shuo Peng, School of Cyber Science and Technology, Shandong University, Qingdao, China, State Key Laboratory of Cryptography and Digital Economy Security, Shandong University, Qingdao, 266237, China, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China

Hao Lei, School of Cyber Science and Technology, Shandong University, Qingdao, China, State Key Laboratory of Cryptography and Digital Economy Security, Shandong University, Qingdao, 266237, China, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China

Guang Zeng, Huawei technologies, Beijing, China

Meiqin Wang, School of Cyber Science and Technology, Shandong University, Qingdao, China, State Key Laboratory of Cryptography and Digital Economy Security, Shandong University, Qingdao, 266237, China, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China, Quancheng Laboratory, Jinan, 250103, China

Abstract

(Multi-branch) Generalized Feistel Network~(GFN) enables the construction of block ciphers from non-linear components with small domains, and has been adopted in various block ciphers. Berger et al. (SAC 2013) introduced the Extended Generalized Feistel Network~(EGFN), which unified and extended existing Feistel-like structures by using a matrix representation. Given an arbitrary matrix, it is typically difficult to determine how many EGFN rounds are sufficient for pseudorandom permutation (PRP) and strong PRP (SPRP) security. Remarkably, security proofs for structures with a larger number of branches have to analyze a huge amount of collision events, which is overly complicated and prone to errors. To remedy this situation, we present AutoEGFN, a computer-aided proof tool that determines the number of rounds sufficient for PRP and SPRP security for various variants of EGFN. The tool operates by calculating three parameters: $r_1$, $r_2$, and $r_3$. The validity and soundness of AutoEGFN are formally established by a detailed security proof. To demonstrate the effectiveness of AutoEGFN, we have applied it to multiple structures such as Type-1/2 GFN (Zheng et al., CRYPTO 1989), YI11's Type-1 GFN (Yanagihara and Iwata, CANS 2011), DFLM19's GFN (Derbez et al., FSE 2019), DDGP22's GFN (Delaune et al., INDOCRYPT 2022), Type-1.x GFN (Yanagihara and Iwata, IEICE 2014), SH/TH GFN (Yanagihara and Iwata, CANS 2011), Nyberg's GFN (Nyberg, ASIACRYPT 1996), SM's GFN (Suzaki and Minematsu, FSE 2010), and BMT's EGFN (Berger et al., SAC 2013). As a result, we provide a systematic analysis of the (S)PRP security for Type-1 and Type-2 structures for different numbers of branches. Our tool efficiently determines the concrete number of rounds required to ensure PRP and SPRP security for EGFNs with different branch numbers. For comparison, previous work only proved the (S)PRP security for 8- and 16-branch BMT's EGFN. Our tool completes the proof within several minutes, even for variants with $32$ branches. Meanwhile, for the other structures, we provide the first concrete (S)PRP security proofs without any restrictions on their permutation layers. Furthermore, AutoEGFN will significantly contribute to the enhancement of EGFN designs and implementations in various cryptographic applications.