Research On Lattice-based Designated Verifier Digital Signature Schemes And Identification Protocol

With the development of cloud computing,big data and Internet technology,we have rapidly entered the information society.Our work,study and life have been in-separable from the information network.Information security is the basic needs of our society,and cryptography technology is the core and support of it,which plays a key role in the normal society.In the network information system,the current mainstream public key cryptosystems are based on the difficulties of decomposing large integer or solving discrete logarithm,however,in the 1990s professor Peter Shor of MIT has pro-vided a quantum algorithm called Shor algorithm,which can solve the large integer decomposition problem and the discrete logarithm problem in polynomial time.Be-cause of the low level of quantum computing and quantum computer technology,it was not taken seriously at that time.But,once the Shor algorithm can really be run,the large integer decomposition problem and the discrete logarithm problem are no longer difficult,then the existing public key cryptosystems are no longer safe.In recent years,with the development of quantum computing and quantum com-puter technology,Shor algorithm gradually poses a real threat to the current public key cryptosystems,and the design of post-quantum cryptosystems are imminent.In 2016,NIST started to solicit post-quantum cryptographic algorithms standard promoting the research of post-quantum cryptography algorithm.Among the post-quantum cryptog-raphy algorithms,lattice-based cryptography is widely regarded as the most promising standard algorithm.In the public key cryptosystems,digital signature algorithm is a very important algorithm,which can be used not only for the establishment of public key cryptosystem but also for the authentication of messages.The identification protocol is the basic guarantee of the security of all kinds of information systems.In this paper,we focus on the design methods of strong designated verifier signa-ture schemes under Fiat-Shamir lattice-based signature framework and the identification protocol of Stern type.While ensuring security,the efficiency and practicability of pro-tocols should be emphasized.For convenience,we give a simple explanation for below parameters:m and n are dimension and rank of the lattice respectively,and lattice point comes from Zq where q is a prime.This paper contains the following three research results:1.Under FSwA framework,we give an efficient strong designated verifier signature based on R-SIS assumption.The existing strong designated verifier signature schemes we study are based on the hash-and-sign framework,which can bring three disadvantages inevitably.First,in order to ensure the security of schemes,the hash-and-sign lattice-based framework uses trap door basis generation algorithm and pre-image sampling function,which need to satisfy the dimension condition m≥5n.log q.Compared with m≥n log q for SIS problem itself,the increase of dimension inevitably leads to the increase the size of public key A∈Zq n×m.Second,Gaussian sampling is used to implement pre-image sampling function in their schemes,which is unusual to resist side-channel attack.Once more,the existing schemes utilize Bonsai tree algorithm to make use of extended trap door basis to finish the signature,causing z having a increased dimension from m to 2m in(r,z,t).In order to increase the efficiency and practicability of signature schemes,we change the framework of existing strong designated verifier signature schemes and use Fiat-Shamir with aborting technology to design them.Specifically,we use uniform sampling and lattice-based SISq,n,m,a problem to de-sign our scheme(here,d is the infinite norms of SIS solution)where the dimension satisfies m≥2n.,hence the public key is smaller than existing schemes with the same n.In addition,we use Fiat-Shamir signature framework with aborting to get signature(r,z,t),where r∈Zq m,z∈Zq,t∈Zqm without dimension increasing.The final signa-ture size of our scheme is 1/100 than that of the existing scheme in random oracle.As for the repeat time,we adopt a calculation method similar to the lattice-based general signature Dilithium scheme which also uses uniform sampling.Under 256 bit security condition,our result is e2048β/γ≈1.28.In addition to the above advantages,our scheme can resist side-channel attacks.2.We propose an efficient ID-based strong designated verifier signature based on R-SIS.Similarly,the existing scheme is constructed based on hash-and-sign framework,the signature form is(z,t),where z∈Zq2m,t∈Zqm,and the shortest signature size we know is 3m.log q.The signature size of our scheme approximately equals 2m log q+m(q>>2)using Fiat-Shamir signature framework,which is better than existing shortest result.Furthermore,it is quite natural that our scheme can resist side-channel attacks with uniform sampling.At the same time,the key extraction and signature algorithm-s in the existing schemes are both because the person who owns the private key can choose corresponding lattice points,and the trapdoor basis is not directly involved in the calculation.Therefore,the scheme does not prove anonymity according to the for-mal definition.In our scheme,the private key is directly used according to the SIS problem,hence we prove the anonymity formally.3.We design a lattice-based low resource consumption zero-knowledge iden-tification protocol.The Stern type identification protocols use 3 commitments and the verifier opens two of the commitments each time to verify the correctness for each challenge.This structure has two disadvantages:(1)2/3 soundness error is relatively large.(2)It has much computation cost and communication cost because of computing and transferring 3 commitments.In 2010,considering reducing the soundness error,Cayrel,Lindner et al.provided a 5 round interaction protocol of Stern type in the fourth international conference on provable security for proving the knowledge of SIS(CLRS scheme).Its soundness error was about 1/2 where the verifier only needed to open one commit for each challenge.Under the same soundness error approximate 1/2,in 2011,Silva,Cayrel et al.reduced the communication cost of CLRS scheme by generating random vectors from two seeds(SCL scheme).However,they still keep the original three commtment values of the Stern type,then the verifier opens two of them at a time.In this paper,we focus on this 5 round interaction protocol of Stern type to con-struct scheme with less computation cost and less communication cost.We find the two commitment values in the first commitment step have the same role in SCL scheme,then we use one commitment in the first commitment step and reserve the third one.Then there are a total of two commitment values.In addition,according to our frame-work with two commitment values,the values r2 and u don’t need to be computed for prover.With the same soundness with SCL,their communication cost is(m/2)log q+2 log κ+m/2+1025,ours is 2 log κ+m/2+833 reducing the amount of verifier and verifier computation and communication cost.