计算机工程 ›› 2014, Vol. 40 ›› Issue (12): 94-96,103.doi: 10.3969/j.issn.1000-3428.2014.12.017

• 安全技术 • 上一篇    下一篇

一种基于格的可证明安全数字签名方案

牟雁飞,赵一鸣   

  1. 复旦大学软件学院,上海 201203
  • 收稿日期:2013-12-06 修回日期:2014-02-11 出版日期:2014-12-15 发布日期:2015-01-16
  • 作者简介:牟雁飞(1988-),男,硕士研究生,主研方向:密码学,信息安全;赵一鸣,副教授。

A Lattice-based Provable Secure Digital Signature Scheme

MOU Yanfei,ZHAO Yiming   

  1. Software School,Fudan University,Shanghai 201203,China
  • Received:2013-12-06 Revised:2014-02-11 Online:2014-12-15 Published:2015-01-16

摘要: 为确保签名算法的安全,现有基于格的数字签名方案在生成签名时存在较高的失败概率(接近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

中图分类号: