Resource Estimation And Optimization Of Grover Algorithm In Symmetric Cryptanalysis

As we all know,once large-scale quantum computers are developed,quantum algorithms represented by Shor,Grover and Simon algorithm will seriously threaten the security of various existing cryptosystems.Although the scale of quantum computers is not enough to break through the current cryptographic primitives so far,with the development of technology,the above quantum algorithms are expected to be implemented in the near future.Thus,accurately estimating the actual arrival time of quantum threat is the key to ensuring the steady renewal of the cryptosystem.With the steady development of quantum computing hardware,evaluating the minimum quantum resources required to realize Shor,Grover,Simon and other cryptanalysis quantum algorithms has become one of the main factors affecting the actual arrival time of quantum threat.However,the current resource estimation for the implementation of cryptanalysis quantum algorithms is only a preliminary result,and the quantum resources required are very large,there is still much room for optimization.This dissertation is dedicated to estimate and optimize the quantum resources required for Grover algorithm attacks on AES,Camellia,and simplified SM4.In the implementation of Grover algorithm,the quantum circuit of symmetric cryptography is an important component and the focus of optimization.Therefore,the paper studies the optimization methods of AES,Camellia and simplified SM4 quantum circuits to reduce the quantum resources required for attacking them by Grover algorithm.Specifically,the research in this dissertation includes the following three aspects:1.From the perspective of number of qubits and T-depth(i.e.,T gate depth),the quantum circuit of AES is optimized.To reduce the number of qubits,with the help of automation tool LIGHTER-R,the quantum circuits of AES S-box for |a>|0>→|a>|S(a)>and |a>|b>→|a>|b⊕S(a))with 20 qubits instead of 22 in a previous study are given respectively.A new technique is introduced to reduce the number of qubits required by the Sbox circuit for |a>→ |S(a)>from 22 in the previous studies to 16.A straight-line method in the round function iteration of AES is presented,which requires 136 qubits instead of 256.As a result,compared with the previous quantum circuits where 400/640/768 qubits are required,our circuits of AES-128/-192/-256 only require 264/328/392 qubits.To reduce the T-depth,a new quantum circuit of AES S-box with a T-depth of 4 instead of 6 in a previous study is proposed.Accordingly,the T-depth required for the quantum circuit of AES-128/-192/-256 is reduced from 120/120/126 in a previous study to 80/80/84.2.Quantum circuit of implementing Camellia with lower costs.First,based on the quantum circuit for implementing the multiplication and multiplication inversion in F24,a new quantum circuit of Camellia S-box with lower costs is presented by using PLU decomposition and elimination methods.Compare with the previous study where 23 qubits,67 Toffoli gates,38 CNOT gates,13 NOT gate and a Toffoli depth of 53 are required,the Camellia S-box quantum circuit in this paper requires 20 qubits,54 Toffoli gates,196 CNOT gates,13 NOT gates and a Toffoli depth of 42.Then the quantum circuits for implementing the round function and key schedule of Camellia are constructed,thereby synthesizing the quantum circuit of implementing Camellia with lower costs.Compared with the previous study where 391 qubits,12048 Toffoli gates,62424 CNOT gates,2815 NOT gates and a Toffoli depth of 9332 are required,the Camellia quantum circuit in this paper requires 388 qubits,9760 Toffoli gates,42816 CNOT gates,3071 NOT gates and a Toffoli depth of 7396.3.Design of simplified SM4 and construction of corresponding quantum circuit.Under current technological conditions,the design of the simplified SM4 and the construction of its quantum circuit is crucial for the study of SM4 algorithm security against the attack of variational quantum algorithm.The paper presents a simplified SM4 that not only retains some characteristics of SM4,but can be implemented with 32 qubits.Specifically,simplified versions of non-linear transformations and linear transformations are given,and the corresponding quantum circuits for implementing them are constructed respectively.Besides,the block length and key length of SM4 are simplified from 128 bits to 16 bits respectively,and the number of iteration rounds is reduced from 32 to 2.After optimizing the quantum circuits of AES,Camellia and simplified SM4,the quantum resources required for attacking them by Grover algorithm are also reduced to a corresponding extent.The results in this paper are conducive to more accurate estimation of the actual arrival time of quantum threats,and can also provide reference for the design of post quantum cryptography.