eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2023/023

New Algorithm for Exhausting Optimal Permutations for Generalized Feistel Networks

Stéphanie Delaune, Institut de Recherche en Informatique et Systèmes Aléatoires, French National Centre for Scientific Research
Patrick Derbez, Institut de Recherche en Informatique et Systèmes Aléatoires
Arthur Gontier, Institut de Recherche en Informatique et Systèmes Aléatoires
Charles Prud'homme, Institut Mines-Télécom
Abstract

The Feistel construction is one of the most studied ways of building block ciphers. Several generalizations were proposed in the literature, leading to the Generalized Feistel Network (GFN) construction, in which the round function operates on each pair of blocks in parallel until all branches are permuted. At FSE'10, Suzaki and Minematsu studied the diffusion of such construction, raising the question of how many rounds are required so that each block of the ciphertext depends on all blocks of the plaintext. Exhausting all possible permutations up to 16 blocks, they observed that there were always optimal permutations mapping even-number input blocks to odd-number output blocks and vice versa. Recently, both Cauchois et al. and Derbez et al. proposed new algorithms to build optimal even-odd permutations for up to 36 blocks. In this paper, we present a new algorithm based on iterative path building to search for optimal Feistel permutation. This algorithm is much faster in exhausting optimal non-even-odd permutations than all the previous approaches. Our first result is a computational proof that no non-even-odd permutation reaches a better diffusion round than optimal even-odd permutations up to 32 blocks. Furthermore, it is well known that permutations with an optimal diffusion round do not always lead to optimal permutations against differential cryptanalysis. We investigate several new criteria to build permutations leading to more secure GFN.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. INDOCRYPT 2022
DOI
10.1007/978-3-031-22912-1_5
Keywords
Block cipherFeistel Networks
Contact author(s)
stephanie delaune @ irisa fr
patrick derbez @ irisa fr
arthur gontier @ irisa fr
charles prudhomme @ imt-atlantique fr
History
2023-01-09: approved
2023-01-06: received
See all versions
Short URL
https://ia.cr/2023/023
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/023,
      author = {Stéphanie Delaune and Patrick Derbez and Arthur Gontier and Charles Prud'homme},
      title = {New Algorithm for Exhausting Optimal Permutations for Generalized Feistel Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2023/023},
      year = {2023},
      doi = {10.1007/978-3-031-22912-1_5},
      note = {\url{https://eprint.iacr.org/2023/023}},
      url = {https://eprint.iacr.org/2023/023}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.