作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (17): 126-128. doi: 10.3969/j.issn.1000-3428.2012.17.035

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

基于高斯抽样算法的NTRU类数字签名方案

张建航1,2,胡予濮1,来齐齐1   

  1. (1. 西安电子科技大学计算机网络与信息安全教育部重点实验室,西安 710071;2. 西安通信学院,西安 710106)
  • 收稿日期:2011-10-20 修回日期:2011-12-18 出版日期:2012-09-05 发布日期:2012-09-03
  • 作者简介:张建航(1979-),男,讲师、硕士研究生,主研方向:格公钥密码设计与分析;胡予濮,教授、博士生导师;来齐齐,博士研究生
  • 基金资助:
    国家自然科学基金资助项目(61173151);国家“973”计划基金资助项目(2007CB311201)

NTRU-class Digital Signature Scheme Based on Gaussian Sampling Algorithm

ZHANG Jian-hang 1,2, HU Yu-pu 1, LAI Qi-qi 1   

  1. (1. Key Laboratory of Computer Networks and Information Security, Ministry of Education, Xidian University, Xi’an 710071, China; 2. Xi’an Communication Institute, Xi’an 710106, China)
  • Received:2011-10-20 Revised:2011-12-18 Online:2012-09-05 Published:2012-09-03

摘要: 针对NTRU类数字签名方案的签名值会泄露私钥的部分信息等问题,提出一种NTRU类数字签名方案。该方案通过私钥生成循环格,采用格上高斯抽样算法在此循环格上找出与杂凑后消息最近的向量作为消息的签名值。与现有的方案相比,该方案在保持签名和验证过程效率的同时,安全性方面具有2个新的性质:(1)由公钥伪造签名的困难性是基于循环格上的最近向量问题;(2)由新方案生成的大量签名值在空间分布呈球形,不泄露私钥的任何信息。

关键词: 格, 量子计算机攻击, 数字签名, 循环格, 最近向量问题, 高斯抽样算法

Abstract: NTRU-class digital signature schemes have a common weakness that signature value leaks some information on the private key. Aiming at this weakness problem, a novel NTRU-class digital signature scheme is created. In the new scheme, a cyclic lattice is generated by using private key, the signature value of the message hashed is the closest vector in the cyclic lattice by using the Gaussian sampling algorithm. Compared with the exiting schemes, the new scheme remains the efficiency of the signature and the verification. This paper obtains following two new results about the novel scheme: (1)The hardness of forging a signature is based on the hardness of the closest vector problem over the cyclic lattice; (2)The distribution of the signature values by using the Gaussian sampling algorithm in the novel scheme is spherical in the space and leaks no information about the private key.

Key words: lattice, quantum computer attack, digital signature, cyclic lattice, closest vector problem, Gaussian sampling algorithm

中图分类号: