Open AccessQuantum Algorithm to Construct Linear Approximation of an S-Box
Author(s) -
Ashwini Kumar Malviya,
Namita Tiwari
Publication year - 2019
Publication title -
international journal of recent technology and engineering
Language(s) - English
Resource type - Journals
ISSN - 2277-3878
DOI - 10.35940/ijrte.d4608.118419
Subject(s) - linear cryptanalysis , s box , block cipher , algorithm , correctness , cipher , mathematics , computer science , differential cryptanalysis , quantum algorithm for linear systems of equations , cryptography , quantum , encryption , quantum mechanics , physics , quantum process , quantum dynamics , operating system
Linear cryptanalysis, a Known-Plaintext Attack, for symmetric block cipher works by constructing linear approximations of the non-linear components of the cipher. The only component which introduces non-linearity in the symmetric block cipher is an S-box. Using classical computing algorithms, the best known solution to find a linear approximation of a non-linear function, in this case an S-box, requires ( ) queries to the S-box and ( +) time-complexity, where is the input size of the S-box and is the output size. In this paper, a quantum algorithm is presented which can produce best linear approximations of a non-linear S-box using only ( ) queries to S-box with ( ) time-complexity. The proposed algorithm shows a significant improvement over the classical algorithm. Correctness proof of the proposed quantum algorithm is presented along with an example.