On Quantum Distinguishers for Type-3 Generalized Feistel Network Based on Separability

Samir Hodžić*, Lars Knudsen Ramkilde, Andreas Brasen Kidmose

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


In this work, we derive a method for constructing quantum distinguishers for GFNs (Generalized Feistel-like schemes with invertible inner functions and XORs), where for simplicity 4 branches are considered. The construction technique is demonstrated on Type-3 GFN, where some other cyclically inequivalent GFNs are considered as examples. Introducing the property of separability, we observe that finding a suitable partition of input blocks implies that some branches can be represented as a sum of functions with almost disjoint variables, which simplifies the application of Simon’s algorithm. However, higher number of rounds in most of the cases have branches which do not satisfy the previous property, and in order to derive a quantum distinguisher for these branches, we employ Simon’s and Grover’s algorithm in combination with a suitable system of equations given in terms of input blocks and inner functions involved in the round function. As a result, we are able to construct a 5-round quantum distinguisher for Type-3 GFNs using only a quantum encryption oracle with query complexity 2N/4 Ö(N/4), where N size of the input block.
Original languageEnglish
Title of host publicationPost-Quantum Cryptography
Publication date2020
ISBN (Print)978-3-030-44222-4
Publication statusPublished - 2020
Event11th International Conference on Post-Quantum Cryptography - Jussieu Campus, Paris, France
Duration: 21 Sep 202023 Sep 2020
Conference number: 11


Conference11th International Conference on Post-Quantum Cryptography
LocationJussieu Campus
Internet address
SeriesLecture Notes in Computer Science


  • Simon’s algorithm
  • Grover’s algorithm
  • Generalized Feistel network
  • Quantum cryptanalysis


Dive into the research topics of 'On Quantum Distinguishers for Type-3 Generalized Feistel Network Based on Separability'. Together they form a unique fingerprint.

Cite this