Type-2 Generalized Feistel Structures Based on Tweakable Block Ciphers, Reconsidered

Generalized Feistel structures (GFSs) generalize a Feistel structure to have more flexible input length. Among them, Zheng et al. originally introduced type-2 GFS (CRYPTO '89) from pseudorandom functions (PRFs). This can be naturally instantiated with tweakable block ciphers (TBCs), which was analyzed by Nakaya and Iwata (ToSC 2022/FSE 2023). For a d -line TBC-based construction, they gave a security proof to show that a d -round construction is birthday-bound secure against chosen ciphertext attacks (CCAs). In this paper, we first show a counterexample to their proof by presenting a distinguishing attack against the d -round construction with O ( 1 ) queries. The attack implies that the proof by Nakaya and Iwata is incorrect, making the provable security of the construction open. We next show that the d -line construction with d rounds is provably secure against chosen plaintext attacks (CPAs) up to the birthday bound. The proof is first given for the case d = 4 , and we then extend this recursively to cover arbitrary values of d . Based on the result against CPAs, we also show that the construction is provably secure against CCAs with d + 1 rounds.