Research On Application Of Quantum Computing In Block Cipher Cryptanalysis

The block cipher algorithm is a kind of symmetric cipher algorithm that divides the input plaintext messages into fixed-length groups for encryption and decryption,and its security mainly depends on the same key held by both communication parties.The advantages of the block cipher algorithm are mainly reflected in fast encryption and decryption,easy standardization,easy software and hardware implementation,etc.The most famous block cipher algorithms include DES(Data Encryption Standard),IDEA(International Data Encryption Algorithm),AES(Advanced Encryption Standard),etc.The security analysis of the block cipher algorithm has always been the focus of international researchers in the field of cryptography.With the development of quantum computing,cryptography researchers also need to consider the security of the block cipher algorithm in quantum setting in order to take corresponding measures to design block cipher algorithms in the post-quantum era.Different from classical computing,quantum computing is a new computing paradigm based on the principles of quantum mechanics.The research results show that quantum computing has a huge speed advantage over classical computing when solving certain problems.Therefore,this dissertation is dedicated to researching on the application of quantum computing in block cipher cryptanalysis and designing cryptanalysis quantum algorithms with speedup compared with classical block cipher cryptanalysis algorithms.Specifically,the research content of this dissertation includes the following three aspects.1.By introducing the quantum collision search algorithm(i.e.,BHT algorithm)into the slide attack on 1K-AES and the related-key attack on PRINCE,the corresponding quantum attacks are presented.In the proposed quantum slide attack on 1K-AES,the BHT algorithm needs to be generalized to the situation where the number of marked items is unknown ahead of time.Moreover,an implementation scheme of classifier oracle based on quantum phase estimation algorithm in the presented quantum attack is given.In addition,the generalized BHT algorithm can also work on the related-key attack of PRINCE.Hence,the quantum related-key attack on PRINCE is proposed.Compared with the corresponding classical attacks,the proposed quantum attacks can achieve subquadratic speedup under the same success probability no matter on query complexity,time complexity or memory complexity.2.The quantum key-recovery attacks are proposed for two-round EvenMansour construction with independent permutations and different subkeys.Specifically,it is necessary to construct new functions based on encryption functions for two-round Even-Mansour constructions with different subkeys,so that the constructed functions are suitable for attacks using the Grover-meets-Simon algorithm and Offline Simon algorithm.The analysis results show that the query complexity of the quantum key-recovery attack proposed for two-round Even-Mansour construction with two alternating subkeys is less than Grover search by a factor of 2n/3 and 2n/2 in Q1 and Q2 model respectively,where n is the block size.And the query complexity of the quantum key-recovery attack proposed for two-round Even-Mansour construction with independent subkeys is better than Grover search by a factor of 25n/6 and 2n in Q1 and Q2 model.Besides,the query complexity of proposed quantum key-recovery attacks is reduced by a factor of 2n/3 and 2n/2 in Q1 and Q2 model compared with the quantum Meet-in-the-middle attack against two-round Even-Mansour construction with two alternating subkeys and two-round Even-Mansour construction with independent subkeys.Moreover,the classical memory complexity of presented quantum key-recovery attacks can attain exponential speedup compared with the quantum Meet-in-the-middle attack.Finally,the presented quantum key-recovery attacks are applied on specific block cipher cryptanalysis and the concrete resource estimation that allows deducing the most efficient attacks based on the trade-off of the number of qubits and Toffoli depth is presented.3.The quantum 3-XOR attack is proposed for two-round Even-Mansour construction with independent permutations and identical subkeys.Combined with the quantum k-XOR algorithm and the 3-XOR attack on two-round EvenMansour construction with identical subkeys,the quantum 3-XOR attack against the construction is proposed.The query complexity of the proposed quantum attack is O(2(n+1)/2),which is close to the Grover search.However,the advantage of the presented quantum 3-XOR attack is that it can be executed in Q1 model.That is,the adversaries of presented quantum attack only need to access the encryption oracle classically.But the adversaries of Grover search require quantum superposition queries on the encryption oracle.Moreover,the query complexity of the presented quantum 3-XOR attack is reduced by a factor of 2n/6 compared with the quantum Meet-in-the-middle attack against two-round Even-Mansour construction with independent permutations and identical subkeys.Here the query complexity means that the query of encryption oracle and public permutations are considered simultaneously.