Quantum Algorithm to Construct Linear Approximation of an S-Box
Ashwini Kumar Malviya1, Namita Tiwari2
1Ashwini Kumar Malviya, Department of Computer Science and Engineering, Maulana Azad National Institute of Technology, Bhopal, India.
2Namita Tiwari, Department of Computer Science and Engineering, Maulana Azad National Institute of Technology, Bhopal, India.
Manuscript received on November 15, 2019. | Revised Manuscript received on November 28, 2019. | Manuscript published on 30 November, 2019. | PP: 9096-9099 | Volume-8 Issue-4, November 2019. | Retrieval Number: D4608118419/2019©BEIESP | DOI: 10.35940/ijrte.D4608.118419
Open Access | Ethics and Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: 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.
Keywords: Linear Cryptanalysis, Linear Approximation, Quantum Computing, Quantum Linear Approximation.
Scope of the Article: Pervasive Computing.