Research On Several Applications Of Quantum Computing In Symmetric Cryptanalysis

Modern cryptography relies on the concept of computational security,and the level of security provided by a cryptographic system can be expressed as the amount of computing resources required to break it.However,based on the assumption of computational complexity,it is difficult for people to break existing cryptographic algorithms within a limited time under the current computing power.This is the cornerstone of the security of the classical cryptosystem.However,due to the existence of quantum algorithms,the security of this cryptographic system has been dramatically affected.For example,Shor’s algorithm will greatly impact the currently widely used RSA cryptographic systems,and Grover’s algorithm provides quadratic acceleration for exhaustive key search(the key length is reduced by half).Therefore,it is of great significance to the development of cryptography to evaluate the specific threats of quantum computing to various cryptographic systems and provide a reference for the design and analysis of cryptographic algorithms that can resist quantum attacks.This thesis researches this hot issue and proposes new and efficient cryptanalytic quantum algorithms for several important classical cryptographic structures.The specific research includes the following three aspects.1.Finding the linear structure of a vector function is an important task in cryptography.In this thesis,we give a new quantum linear structure finding algorithm based on the Bernstein-Vazirani(BV)algorithm.It needs only O(n)quantum queries.Our result realizes a quadratic speedup compared with the previous algorithm(with complexity O(n~2)).Besides,we find two new applications for this kind of BV-based attack,i.e.,related-key attacks on iterated Even-Mansour ciphers and i-round Feistel ciphers with independent round keys.Also,both attack instances realize an exponential speedup compared with their classical versions.2.Message authentication code(MAC)is a fundamental symmetric-key primitive,which can ensure the integrity and reliability of messages,and is widely used in various information systems.In this thesis,we investigate the security of several recent MAC constructions with provable security beyond the birthday bound(BBB MAC)in the quantum setting.On the one hand,we give periodic functions corresponding to targeted MACs(including PMACX,PMAC with parity,HPxHP,and HPxNP),and we can recover period using Simon’s algorithm,leading to forgery attacks with complexity O(n).This implies our results realize an exponential speedup compared with the classical algorithm.Note that,our attacks are more efficient than some related results,i.e.,they exponentially improve previous quantum attacks(Grover-meets-Simon’s attack with complexity O(2n/2)on mPMAC+-f,mPMAC+-p1,and mPMAC+-p2 from the viewpoint of quantum query complexity.On the other hand,we construct new hidden periodic functions based on SUM-ECBC-like MACs:SUM-ECBC,PolyMAC,GCM-SIV2,and 2K-ECBC_Plus,where periods reveal the information of the secret key.Then,by applying the Grover-meets-Simon algorithm to specially constructed functions,we can recover full keys with O(2~n/~2n)or O(2~m/~2n)quantum queries,where n is the message block size and m is the length of the key.Our key-recovery attacks achieve a quadratic speedup considering the previous best quantum attack.3.The generalized Feistel scheme(GFS)is an extremely important and extensively researched cryptographic scheme.In this thesis,we investigate the security of Type-1 GFS in quantum circumstances.On the one hand,based on the Simon algorithm,we give a new quantum polynomial-time distinguisher on(d~2-1)-round Type-1 GFS,which extends the previous results by(d-2)rounds.This leads to a more efficient analysis of Type-1 GFS,that is,the complexity of some previous key-recovery attacks is reduced by a factor of 2(d-2)k/2,where k is the key length of the internal round function.On the other hand,for CAST-256,we give a 17-round polynomial-time quantum distinguisher,which extends the previous results by 3 rounds.