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

Abstract

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
PublisherSpringer
Publication date2020
Pages461-480
ISBN (Print)978-3-030-44222-4
DOIs
Publication statusPublished - 2020
EventEleventh International Conference on Post-Quantum Cryptography. - Jussieu Campus, Paris, France
Duration: 21 Sep 202023 Sep 2020

Conference

ConferenceEleventh International Conference on Post-Quantum Cryptography.
LocationJussieu Campus
CountryFrance
CityParis
Period21/09/202023/09/2020
SeriesLecture Notes in Computer Science
Volume12100
ISSN0302-9743

Keywords

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

Fingerprint 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