Zero-knowledge Proof Over Lattices

With the popularity and rapid development of quantum computing,post-quantum cryptographic algorithms and cryptographic protocols have also become research hotspots.Among them,the lattice-based zero-knowledge proof scheme is faster and resist quantum algorithm cryptanalysis,which can make the cryptography scheme simple and efficient,and is a research hotspot of public key cryptography.Compared with the classical ZK(Zero Knowledge)scheme,the ZK scheme based on lattice difficult problems has a more solid security foundation and higher computational efficiency.The current proof scheme based on SIS(Small Integer Solution)is more secure than the Stern-type scheme,and soundness error is also reduced,but it lacks an accurate proof that requires only one iteration;the NIZK(Non interactive Zero Knowledge)scheme based on LWE(Learning with errors)which is compared to the J.Groth's proof based the classical model has improved the computational efficiency,but it lacks the NIZK accurate proof that satisfies the safety based the lattice assumption.In this paper,the zero-knowledge proofs based on lattice are researched.First,it deeply studies and analyzes the proof scheme based on SIS,and proposes an improved proof scheme;then designs a NIZK construction scheme based on LWE for general NP language.The main work of the thesis is summarized as follows:Firstly,the implementation process if proof scheme based on SIS is analyzed and improved in detail.An algebraic proof technique and multiple proofs are applied as subroutines.Combining the advantages of several schemes,an improved proof scheme is proposed.It mainly includes the optimization of the rejection sampling lemma and the challenge space,and the expansion of the provable relationship into a more general equation relationship,so that the scheme is an accurate proof of ZK,and the soundness error is reduced tol/qC,where q and C is the size of two challenge spaces respectively.When the size of C is selected 2256,the proof protocol only needs to be executed once.Secondly,a NIZK construction scheme based on LWE for general NP language is proposed.After analyzing and summarizing the zero-knowledge proof scheme under the classical model,this paper uses a transformation technique to transform the proof of the general NP language into a proof of an equivalence relationship,and the equation relationship that originally to be proved is converted into a calculation function for homomorphic encryption,and uses homomorphic commitment to solve the difficulty of exposing part of the information when encountering decryption,uses homomorphic commitment to realize the proof scheme,and finally gives a specific protocol construction based on LWE encryption,and carries out the safety analysis.