Chinese Journal of Computers   Full Text
Title	A Novel NTRU-Class Digital Signature Scheme
Authors	HU Yu-Pu
Address	(The Ministry of Education Key Laboratory of Computer Networks & Information Security, Xidian University, Xi‘an 710071)
Year	2008
Issue	No.9(1661—1666)
Abstract &   Background	Abstract NTRU-class digital signature schemes have a common weakness that signature value will leak information on the private key. According to this weakness, several effective attacks were proposed against these signature schemes. This paper presents a novel NTRU-class digital signature scheme. The new signature scheme has a similar structure to R-NSS, but with several novel designs. This paper has obtained following three results about the new scheme: (1) The hardness of recovering the private key from the public key is based on the hardness of the shortest vector problems(SVP) of several lattices; (2) The hardness of forging a signature is equivalent to the hardness of the closest vector problem(CVP) of some lattice; (3) Each signature will leak information on the private key, but the final shape of the unlimited leakage is just a group of complicated non-linear equations. Keywords NTRU； digital signature； the Shortest Vector Problem of lattice(SVP)； the Closest Vector Problem of lattice(CVP) Background NTRU is one of the fastest public-key-ciphers known. The security of NTRU is based on the hardness of the shortest vector problem (SVP) of some lattice, called NTRU lattice or CS lattice (named by D.Coppersmith and A.Shamir). Unfortunately, from the point of the security, digital signature schemes following the NTRU design have not been successful enough. Most of them have been broken. The reasons why such attacks are effective are the follow. Reason 1.Each signature value is a multiple of a single private key (without the protection by the modular operations), with the secret combination coefficients. So that the GCD method can be used to recover the private key. Reason 2.Each signature value is a linear combination of the private keys (without the protection by the modular operations), with the secret combination coefficients. The combination coefficients have a public distribution (for example, uniform distribution). By a large number of signatures, the attacker can filter off the combination coefficients, and obtain the value of some simple function of the private keys. Such function can be taken as the function of real number variables. Those methods of the continuous mathematics (for example, the optimization method) can be used for computing the private keys. Although the digital signature schemes following the NTRU design have so many security weaknesses, they may be the candidates in the future computation environment, because RSA and DSA have been broken in the quantum computation environment. So that it is worth to take an advanced research for the digital signature schemes following the NTRU design.