Research On Hash Functions With Provable Security

With the rapid development of quantum computers,the design of cryptographic functions that can resist quantum computing attacks has become a hot topic in cryptography.As a key work in cryptography,it is especially important to design a secure hash function.The commonly used hash functions are mostly iterative hash functions and their advantage is high speed,and the disadvantage is that security requires a long time attack test.This thesis focuses on anti-quantum-computing attack,and provably security lattice-based hash functions."Provable security"refers to the security of a function based on hard problems in lattices.The main work is as follows:Firstly,the efficiency of the SWIFFT compression function is analyzed in detail.We point out that when implementing the SWIFFT function with 8-input Fast Fourier Transform?FFT?,4032 additions/subtractions,1664 multiplications,and 256 memory elements in Z⁸₂₅₇are required.When using the 16-input FFT to implement the SWIFFT function,it requires 17344 additions/subtractions,5376 multiplications,and storage of 16 elements in Z¹⁶₂₅₇.When the SWIFFT function is implemented,the value of?in the FFT flow graph where the multiplication can be replaced by a least bit shift is a suitable value,and we provide a method for calculating a suitable value?.Secondly,a compression function based on the Small Integer Solution problem in module lattices?M-SIS?is designed.Based on the hard problem in module lattices,we increase the security parameters of the SWIFFT compression function from n to N?28?dn,and construct the M-SWIFFT compression function.This function uses FFT to implement parallel operations,which is less efficient than the SWIFFT function,but is more secure than the SWIFFT function.The newly designed M-SWIFFT compression function has provable security.Finding collisions or pre-images in the function is at least as hard as finding non-zero short vectors in module lattices in the worst-case.Thirdly,a hash function based on lattice hard problem is designed.Taking SWIFFT and M-SWIFFT as the important part,the M-SWIFFTX hash function is constructed.The hash function takes the HAIFA?HAsh Iterative FrAmework?as an iterative structure and adds S-boxes and byte conversions to make the hash function pseudo-random.The newly designed hash function has high parallelism,provable security,and resistance to quantum computing attacks.Compared with the SWIFFTX hash function,the M-SWIFFTX hash function is relatively low-efficiency,but it is more secure.Moreover,it is a new application of the cryptographic functions based on M-SIS hard problem.