Study On Quantum Algorithms Applied To Symmetric Cryptanalysis

Quantum computing has been received extensive attention since it has incomparable advantages over classical computing,and thus its development has threatened the security of current cryptography.As is well known,Shor’s algorithm could break many public-key cryptographic schemes(e.g.,RSA and ECC)in polynomial time.In the past few years,some quantum algorithms applied to symmetric cryptanalysis have been studied,such as Grover’s algorithm,Simon’s algorithm,the Bernstein-Vazirani(BV)algorithm and their derivative algorithms.In this thesis,we mainly study two kinds of quantum algorithms applied to symmetric cryptanalysis: quantum period finding algorithms and quantum algorithms for learning the algebraic normal form of Boolean functions.Quantum period finding algorithms have been used to analyze symmetric cryptography.For instance,the 3-round Feistel construction and the Even-Mansour construction could be broken in polynomial time by using quantum period finding algorithms.In this paper,we firstly provide a new algorithm for finding the nonzero period of a vectorial function with O(n)quantum queries,which uses the BernsteinVazirani algorithm as one step of the subroutine.Afterwards,we compare our algorithm with Simon’s algorithm.When applied in some scenarios,such as the Even-Mansour construction and the function satisfying Simon’s promise,etc,our algorithm is more efficient than Simon’s algorithm with respect to the tradeoff between quantum memory and time.On the other hand,we combine our algorithm with Grover’s algorithm for the key-recovery attack on the FX construction.Compared with the Grover-Meets-Simon algorithm proposed by Leander and May at Asiacrypt 2017,the new algorithm could save the quantum memory.The algebraic normal form(ANF)of a linear Boolean function can be recovered by using the Bernstein-Vazirani algorithm.Little research has been carried out on quantum algorithms for learning the ANF of general Boolean functions.In this paper,quantum algorithms for learning the ANF of quadratic Boolean functions are studied.We draw a conclusion about the influences of variables on quadratic functions,so that the BV algorithm can be run on them.We study the functions obtained by inversion and zero-setting of some variables in the quadratic function,and show the construction of their quantum oracle.We introduce the concept named "club" to group variables that appear in quadratic terms,and study the properties of clubs.In addition,we give a method of checking degenerate variables in a particular situation via entanglement measures.Furthermore,we propose a bunch of algorithms of learning the full ANF of quadratic Boolean functions.Specially,The most efficient algorithm,among those we propose,provides an O(n)speedup over the classical one,and the number of queries are independent of the degenerate variables.