Research On Hash Functions And Boolean Functions Based On Quantum Computing

With the continuous development of quantum computing,the computational advantage of quantum algorithm poses a threat to traditional cryptography.At present,asymmetric ciphers designed based on difficult mathematical problems can be cracked in polynomial time by Shor algorithm.In the case of symmetric cryptography,its security is also threatened by quantum algorithms such as Grover and Simon.Therefore,the quantum algorithms used in cryptography are studied in this thesis,and the quantum collision attack of Hash function SHA-2 and quantum learning algorithm for the algebraic normal form(ANF)of Boolean functions of Boolean function are given.(1)Based on quantum counting and Simon and other quantum algorithms,the quantum collision attack of Hash function is proposed.Firstly,through the analysis of quantum counting algorithm,it can be used to determine whether there is collision in Hash function and the number of collisions.Second,consider the collision message pair as a special period of the Hash function’s existence.Furthermore,the attacked algorithm satisfies Simon’s promissory condition.Therefore,the collision lookup of the Hash function is converted to the periodic lookup of the function.On this basis,an improved Simon algorithm with single coset and multiple periods is used to find the period of the Hash function.The corresponding period of the Hash function is obtained,that is,the quantum collision attack on SHA-2 series algorithms is successfully carried out.The time complexity required to implement this attack is O(MN/+tn)where M is the number of cycles,N is the number of all possibilities,n equation group is to build a solution cycle when the number of times,t is Simon algorithm run times,is approximately equal to the M value of the error.(2)Based on the difference relationship between Bernstein-Vazirani(BV)algorithm and Boolean function,a cubic Boolean algebraic normal quantum learning algorithm is proposed.Firstly,the influence of variables in cubic Boolean functions is analyzed,and the probability that variables can be obtained by running BV algorithm once on Boolean functions is determined.Secondly,the quantization of variable inverse and zero operation is realized.Furthermore,Boolean function difference is realized in quantum environment.Then,we group the variables in the cubic Boolean function,and prove that the probability of obtaining the variables in different groups is independent,which makes it easier to obtain the required variables.On this basis,three quantum algorithms for learning algebraic normal forms of cubic Boolean functions are proposed.The time complexity of the optimal quantum learning algorithm for algebraic normal forms of cubic Boolean functions is O(t ~2)where t is the number of non-degenerate variables of the Boolean functions.The time complexity of classical algorithms to learn the ANF of Boolean functions is O(n2~n)where n is the number of all variables in the Boolean functions.