Research In Lattice-Based Digital Signature And Identification Protocols

Digital signature and identification are two very important applications of Public Key Cryptography in our daily life. Almost the security of all digital signa-ture and identification protocols are based on the hardness of integer factorization and discrete logarithm problem since they were proposed. In 1994, Shor gave algo-rithms that could be used to solve the integer factorization and discrete logarithm problems in quantum computers, which draws great attentions to cryptography in quantum computers. As a result of this, apart from the integer factorization and discrete logarithm problems, other complexity assumptions must be come up with to secure cryptography both in normal computers and in quantum comput-ers. Lattice based cryptography becomes a hot research area in post quantum cryptography because of its worst-case complexity assumptions, computational efficiency and rich intractability assumptions. Many lattice based digital signa-ture and identification schemes have been proposed, but few of them can compete with those based on integer factorization and discrete logarithm problem both in efficiency and security, which will restrict the practical application of lattice based cryptography.By analyzing the most recent research in lattice based digital signature and identification protocols, this paper first present a provably secure lattice based digital signature scheme in the random oracle model. The key size and compu-tational complexity are almost linear(O(nlogn)). Its security is based on the intractability of Ring - SIS problem in the random oracle model. Moreover, this scheme satisfies the notion of strong unforgeablity and the signing algorithm will never fail. Next, this paper proposes a provably secure lattice based identifica-tion scheme with perfect completeness. The identification scheme is much like the Schnorr scheme and is secure under the hardness of the SIS problem. Finally, Ideal Lattice is used to reduce the space complexity from mn logp to mlogp and time complexity from O(mn) to O(mlogn).