摘要： 为确保签名算法的安全,现有基于格的数字签名方案在生成签名时存在较高的失败概率(接近2/3),因此需要运行签名算法3次才能生成一个合法签名。为此,提出一种基于格的可证明安全数字签名方案,将消息签名作为Ring-SIS问题,私钥作为Ring-SIS问题的一个解,使攻击者无法根据消息签名得到私钥。基于多项式环下的运算,在签名过程中引入两位随机数,并使用抗碰撞的哈希函数进行随机化,使最终签名分布与私钥分布无关。与现有方案相比,该方案解决了签名生成失败的问题,并且在保证签名算法安全性的同时对现有方案的计算复杂度无较大影响。

关键词: 格, 数字签名, 可证明安全, 多项式环, 哈希函数

Abstract: In order to ensure the security of signature algorithm,during the signing phase the signing algorithm may be executed multiple times(3 times expectedly) because there is high probability(approximately 2/3) of signing failure.This paper proposes a lattice-based provable secure digital signature scheme to overcome this problem.Ring-SIS is introduced into the new algorithm:the signature itself is regarded as the Ring-SIS problem and the private key is regarded as its solution.As a result of this,an attacker can not get the private key by using the signature.This algorithm whose operations are in the polynomial rings,introduces two random numbers and a hash function to achieve randomness to make the distribution of signature and private key independent of each other.Compared with the original scheme,this scheme has better security and efficiency,and more importantly,it eliminates the possibility of signing failures.

Key words: lattice, digital signature, provable security, polynomial ring, hash function

中图分类号: 

• TP309.7