一个新型的NTRU类数字签名方案

A Novel NTRU-Class Digital Signature Scheme

NTRU类数字签名方案的一个共同缺陷是签名值会泄露私钥的一些信息.针对这个缺陷,当前已经有若干有效攻击.该文提出一个新型的NTRU类数字签名方案.新方案具有与R-NSS相似的结构,但有若干新颖的设计.文中给出新方案的3个结果:(1)由公钥恢复出私钥的困难性基于若干格上的最小向量问题(SVP);(2)由公钥伪造签名的困难性等价于某个格上的最近向量问题(CVP);(3)每个签名值仍然会泄露私钥的一些信息,但无限制泄露的最终形式只是关于私钥的一组复杂的非线性方程.

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 pro- posed 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.