Circuit Research Of Quantum Algorithms For Cryptographic Problems

With the continuous development of quantum computing,its application scenarios are becoming more and more diversified,and its application in cryptography is one of the most worthy of study.In the environment of quantum computation,the security performance of different cryptographic algorithms needs to be evaluated,and the quantum circuit model is an important tool to make it.The quantum circuit model equivalent to the quantum Turing machine model can clearly and intuitively simulate the processing of quantum information,and has a good guiding role for the design of quantum computing devices and new quantum algorithms;quantum algorithms are usually represented by quantum circuits and designing good quantum circuits means better implementation of quantum algorithms.At present,there are three indicators to measure the quality of quantum circuits-the number of qubits,the number of Toffoli gates/T gates,and the depth of Toffoli gates/T gates.The RSA,Elliptic Curve Cryptograph on prime Galois Fields and binary extension Galois Fields,and AES are several typical cryptosystems.Reasonable design of the quantum circuits of these cryptographic algorithms to optimize the number of qubits,the number of Toffoli gates/T gates,and the depth of Toffoli gates/T gates will help to further evaluate the security performance of cryptographic systems in the new era.Focusing on the theme of quantum circuit optimizations of cryptographic algorithms,the approximate encoded permutation,the windowed look-up table operation,improved quantum Karatsuba multiplication and the reduction of the approximate minimum Steiner tree problem have been used in this paper,which enrich the theoretical basis and technical support for the quantum analysis of cryptographic algorithms.The main work is as follows:1.In order to achieve a good trade-off performance between the time and space resources required by the quantum circuit of the Shor’s integer factorization algorithm in a noisy environment,the coset representation technology of modular integers and the windowing technology are used to optimize the quantum circuit of order-finding for integer factorization.In this work,the coset representation technique of modular integers achieves a trade-off between the time and space resources by adding approximation errors;the windowed look-up table operation can greatly reduce the number of Toffoli gates required in quantum circuits.The results show that the error caused by the approximation can be reduced exponentially with the increase of the number of padding bits in the coset representation of modular integers;windowed the look-up that retrieves data from a classical table addressed by a quantum register can reduce the number of multiplication operations and addition operations.2.Aiming at the quantum circuit optimization problem of elliptic curve discrete logarithm solving on prime Galois Fields,the number of quantum gates and the depth of the quantum circuit have been improved in the modular addition part,and the quantum circuit of elliptic curve discrete logarithm problem on prime Galois Fields has been optimized by using the method of approximate encoded permutation combined with windowing method.Furthermore,the number of T gates and the depth of T gates required for the modular multiplication,modular square,and modular inverse parts have been optimized on the condition that the number of qubits has been increased with logarithmic scale.In this work,with the help of windowing technique and the coset representation of modular integers,the overall optimization and resource estimation of the quantum circuits for solving discrete logarithm problems in elliptic curve groups has been given based on the approximate encoded representation of addition,which effectively reduces the number of T gates and the depth of T gates.Besides,the quantum resource of the designed quantum circuit has been estimated.Numerical results show that both the number of T gates and the depth of T gates can be reduced by choosing appropriate window parameters after increasing the logarithmic scale of qubits.3.For the quantum circuit optimization problem of elliptic curve discrete logarithm solving on binary extension Galois Fields,by analyzing the resource expenditure of quantum circuits such as addition,binary shift,multiplication,squaring,and inversion required by point addition operations under a constrained connectivity,the number of CNOT gates in inversion and division are optimized with the help of minimum Steiner tree problem reduction and space-efficient quantum Karatsuba multiplication.Considering topology,the performance of the quantum algorithm for solving the elliptic curve discrete logarithm problems on binary extension Galois Fields has been evaluated.In this work,based on the inversion algorithm of Fermat’s little theorem(Itoh-Tsujii algorithm)and the reduction of the minimum Steiner tree problem,the number of CNOT gates of the sub-circuit included in the point addition has been optimized with considering limited connectivity.The numerical simulation results show that the number of CNOT gates in the division circuit can be optimized by using the minimum Steiner tree problem reduction and quantum Karatsuba multiplication.4.Aiming at the optimization implementation of S-box transformation in AES-128,an index to measure the trade-off between time resource cost and space resource cost has been introduced-the product of the number of qubits and the depth of the T gate.The quantum resources required to compute the multiplicative inverse and realize the S-box have been further optimized with the help of windowed quantum look-up table method and the quantum Karatsuba multiplication.In this work,a comprehensive comparison of quantum resource cost of three multiplicative quantum circuits has been made,and the optimal multiplicative inverse circuit of them has been selected in terms of the trade-off between the time resource cost and the space cost of the quantum circuit for multiplicative inversion in S-box;The windowed look-up table method further reduces the number of quantum multiplications.The results show that with the help of the windowed look-up table technique,all of the number of Toffoli gates,the number of qubits and the product of the number of qubits and the depth of T gates are better when the quantum Karatsuba multiplication is used.