TY - GEN

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

AU - Hodžić, Samir

AU - Knudsen Ramkilde, Lars

AU - Kidmose, Andreas Brasen

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Simon’s algorithm

KW - Grover’s algorithm

KW - Generalized Feistel network

KW - Quantum cryptanalysis

U2 - 10.1007/978-3-030-44223-1_25

DO - 10.1007/978-3-030-44223-1_25

M3 - Article in proceedings

SN - 978-3-030-44222-4

T3 - Lecture Notes in Computer Science

SP - 461

EP - 480

BT - Post-Quantum Cryptography

PB - Springer

T2 - Eleventh International Conference on Post-Quantum Cryptography.

Y2 - 21 September 2020 through 23 September 2020

ER -