Cryptanalysis For Keccak-based Authenticated Encryption Ciphers And NTRU Cryptographic Algorithms

With the development of information technology,we have entered the age of information.Information exchange has become increasingly common and frequent.As the process of informatization continues to advance,ensuring information security has become a widely concerned focus of society.Information security,also known as network security,is the foundation of the information society,and information security issues are significant fundamental,strategic,and global issues for the country and society in the construction of informationization.Cryptography provides a theoretical foundation for information security and can be called the theoretical cornerstone of information security.Cryptographic algorithms can be simply divided into symmetric cryptogra.phic algorithms and asymmetric cryptographic algorithms(also known as public key cryptography).This thesis focuses on the study of the authenticated encryption algorithm based on the Keccak permutation function and the NTRU cryptographic algorithm,where the encryption algorithm based on the Keccak permutation function is a symmetric encryption algorithm,and the NTRU cryptographic algorithm is an asymmetric encryption algorithm.We propose a more accurate cube-attack-like cryptanalysis model and a new auxiliary variable selection method.So far,the cube-attack-like cryptanalysis proposed in this thesis for Ketje-Jr-vl,Ketje-Jr-v2,and Keccak-MAC-512 are still the optimal cube-attack-like cryptanalysis.Furthermore,this thesis analyzes the variant lattices of the NTRU lattice,specifically the IN-lattice,and discovers the potential for further reducing the dimension of the variant IN-lattice,thereby decreasing the computational time of variant lattice attacks.Additionally,this thesis examines q-ary lattices for NTRU and LWE-type problems,studying their measurements and simulations,which can contribute to the improvement of lattice-based cryptographic algorithm evaluations.1:Improved cube-attack-like cryptanalysis on Keccak keyed modesThe Keccak algorithm is based on the Sponge structure,and its internal permutation function is called the Keccak-f function.At the 2018 FSE conference,Song and Guo addressed the reduced-round Keccak algorithm and removed the CP-kernel constraint on cube variables previously proposed by Bi et al.,thereby increasing the freedom of cube variables.They first considered the preprocessing stage and online stage together in a mixed integer linear programming(MILP)model and achieved some impressive improvements.However,as they pointed out,the related key bits involved are not entirely independent,and calculating the independence of these related key bits is beyond the scope of the MILP model.Therefore,other methods need to be explored to further improve the results of cube-attack-like cryptanalysis.This thesis proposes a novel approach to improve the complexity of the cubeattack-like cryptanalysis.The approach involves two important steps:constructing an MILP(Mixed-Integer Linear Programming)model and selecting auxiliary variables.In the first step,this thesis obtains precise algebraic expressions for each bit using a round function and applies corresponding constraints to these variables,transforming them into an MILP model.The proposed MILP model in this thesis mitigates the issue of error propagation caused by repetitive computations in previous models,thus improving accuracy.In the second step,a more sophisticated and innovative method for selecting auxiliary variables is employed,removing the constraint of satisfying the CP-core property,and expanding the degree of freedom in the selection process,thereby allowing for better choices.With the assistance of these two steps,the time and space complexity of the cube-like attack are reduced accordingly.2:Analyze the certain variants IN-lattice and relevant q-ary lattice of NTRUSo far,several studies have found sufficiently short vectors in certain variants of the NTRU lattice,which can be used to analyze the security of NTRU systems.These variant lattices are modifications of the standard NTRU lattice that utilize the properties of the NTRU cryptosystem.These related variants include the Zero-Run lattice of dimension 2N,the Zero-Forced lattice of dimension 2(N-r),and the IN lattice of dimension N(where r<N).We review these related variant lattices and develop techniques to further reduce the dimension of the IN lattice,which significantly reduces the expected time.Our experimental results show that our method is superior to previous methods.During the study of the NTRU variant lattices,we notice that the BKZ algorithm has become one of the most important tools for analyzing and evaluating lattice cryptography.Yu et al.conducted a good measurement analysis of the second-order statistical behavior of the BKZ algorithm on random lattices and used the results to evaluate simulators.Several simulators have emerged that accurately predict the shape of random lattice profiles,but the situation is not so clear for q-ary lattices.Albrecht and Ducas raised the question of how to simulate or predict the behavior of the BKZ algorithm on q-ary lattices as an open problem in 2021.Our experiments reveal more features of q-ary lattices.Based on some results of the distribution of short vector lengths,we propose a new extended q-ary lattice simulator.We further study the second-order statistical behavior of the BKZ algorithm on q-ary lattices,compared it with random lattices,and briefly analyze the similarities and differences between them.