New Trapdoor And Preimage Sampling On NTRU Lattice

As a tool for designing cryptographic schemes based on lattice trapdoors,the preimage sampling algorithm is inefficient and hinders the application of cryptographic schemes.In order to improve the efficiency of cryptographic schemes based on lattice trapdoors,a series of improvement schemes have emerged in the past decade.The efficiency of the preimage sampling algorithm is increasing,but there is still room for improvement.This paper aims to study the trapdoor and preimage sampling algorithms on NTRU lattices,hoping to improve the spatial efficiency,security,and time efficiency of cryptographic schemes based on lattice trapdoors.1.In response to the incompatibility of the advantages of the two NTRU-SIS trapdoors proposed by Genise and Li in the sampling algorithm under the MP12 framework,this paper first proposes a new NTRU-SIS trapdoor based on the NTRU-Learning problem;Secondly,a preimage sampling algorithm on NTRU lattice was constructed based on this trapdoor;Finally,the correctness of the algorithm was proven.The newly designed trapdoor can be applied to any cyclotomic polynomial ring,and supports the parallel execution of perturbed sampling,which solves the incompatibility of the advantages of the original scheme in the sampling algorithm.2.Based on the newly designed trapdoor and preimage sampling algorithm,this paper first constructs a hash-and-sign digital signature algorithm;Secondly,a strong unforgeable security proof is provided under the random oracle model;Finally,a comparison is made between the new signature algorithm and the original signature algorithm.Theoretical analysis and experimental results show that the signature algorithm proposed in this paper has a shorter public key and signature size,while sacrificing the efficiency of key generation to a certain extent.It also has higher security,and due to the use of smaller modules,the computational efficiency has been improved to a certain extent.