基于理想格的可证明安全数字签名方案

doi:10.3969/j.issn.1000-3428.2017.05.017

摘要/Abstract

摘要： 为确保签名算法在量子攻击下的安全性,现有的基于格的签名方案大部分都采用标准格结构下的困难性假设问题,而不是理想格,造成方案效率较低。为此,提出一种新的基于理想格上PLWE问题的数字签名方案。通过归约到PLWE问题,证明攻击者即使获取多个已有的消息和对应的签名,也无法对一个新的消息伪造出合法的签名。分析结果表明,与现有的基于标准格上陷门的数字签名方案相比,该方案的签名长度和公私钥长度均减少了约O(n)。

关键词: 格, 数字签名, 陷门, 多项式环, 安全性分析

Abstract: In order to guarantee the security of signature scheme under quantum attack,most of the existing lattice-based signature schemes are based on the difficulty hypothesis under general lattice rather than ideal lattice,and it caused lower efficiency of these schemes.To overcome the problem,a new digital signature scheme based on ideal lattice is proposed.By reducing the problem to the PLWE,it is proved that an attacker can not forge a legitimate signature for a new message even if he gets multiple existing messages and the corresponding signature.Analysis result shows that the signature length and the key length of the scheme are reduced by O(n),compared with the existing digital signature scheme based on general lattice.

Key words: lattice, digital signature, trapdoor, polynomial ring, security analysis

中图分类号:

TP393

冯超逸,赵一鸣. 基于理想格的可证明安全数字签名方案[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2017.05.017.

FENG Chaoyi,ZHAO Yiming. Ideal Lattice Based Justifiable Secure Digital Signature Scheme[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2017.05.017.

http://www.ecice06.com/CN/Y2017/V43/I5/103

参考文献

参考文献［1］Diffie W,Hellman M E.New Directions in Cryptography［J］.IEEE Transactions on Information Theory,1976,22(6):644-654. ［2］贺卫红,曹毅.RSA公钥密码体制在数字签名中的应用［J］.微机发展,2003,13(9):49-50. ［3］陈泽文,张龙军,王育民,等.一种基于中国剩余定理的群签名方案［J］.电子学报,2004,32(7):1062-1065. ［4］杨君辉,张玉峰,戴宗铎.一个基于两个数学难题的签名方案的分析［J］.信息安全与通信保密,1999(4):42-43. ［5］Shor P W.Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer［J］.SIAM Review,1999,41(2):303-332. ［6］Ajtai M.Generating Hard Instances of Lattice Pro-blems［C］//Proceedings of the 28th Annual ACM Symposium on Theory of Computing.New York,USA:ACM Press,1996:99-108. ［7］Goldreich O,Goldwasser S,Halevi S.Public-key Cryptosystems from Lattice Reduction Problems［C］//Proceedings of Annual International Cryptology Conference.Berlin,Germany:Springer-Verlag,1997:112-131. ［8］Gentry C,Peikert C,Vaikuntanathan V.Trapdoors for Hard Lattices and New Cryptographic Construc-tions［C］//Proceedings of the 14th Annual ACM Symposium on Theory of Computing.New York,USA:ACM Press,2008:197-206. ［9］Agrawal S,Boneh D,Boyen X.Efficient Lattice(H) IBE in the Standard Model［C］//Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,Germany:Springer-Verlag,2010:553-572. ［10］杨晓元,吴立强,张敏情,等.基于 R-LWE 的公钥加密方案［J］.通信学报,2013,34(2):23-30. ［11］杨丹婷,许春根,徐磊,等.理想格上基于身份的签名方案［J］.密码学报,2015,2(4):306-316. ［12］Micciancio D,Peikert C.Trapdoors for Lattices:Simpler,Tighter,Faster,Smaller［C］//Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,Germany:Springer-Verlag,2012:700-718. ［13］Lai R W F,Cheung H K F,Chow S S M.Trapdoors for Ideal Lattices with Applications［C］//Proceedings of Information Security and Cryptology.Berlin,Germany:Springer-Verlag,2014:239-256. ［14］Lyubashevsky V,Peikert C,Regev O.On Ideal Lattices and Learning with Errors over Rings［C］//Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,Germany:Springer-Verlag,2010:1-23. ［15］Regev O.On Lattices,Learning with Errors,Random Linear Codes,and Cryptography［J］.Journal of the ACM,2009,56(6):34. ［16］Lyubashevsky V,Peikert C,Regev O.A Toolkit for Ring-LWE Cryptography［C］//Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,Germany:Springer-Verlag,2013:35-54. ［17］Brakerski Z,Vaikuntanathan V.Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages［C］//Proceedings of Annual Cryptology Conference.Berlin,Germany:Springer-Verlag,2011:505-524. ［18］Goldwasser S,Micali S,Rivest R L.A Digital Signature Scheme Secure Against Adaptive Chosen-message Attacks［J］.SIAM Journal on Computing,1988,17(2):281-308. 编辑刘冰

[1]	陈治旭, 靳雁霞, 芦烨, 杨晶, 刘亚变, 史志儒. 基于子图卷积神经网络的多精度服装建模方法[J]. 计算机工程, 2023, 49(4): 174-181.
[2]	朱晓强, 陈琦. 基于可控卷积曲面的三维神经元建模[J]. 计算机工程, 2023, 49(3): 231-237.
[3]	蔡瑞初, 吴思宇, 乔杰. 面向故障间格兰杰因果发现的霍克斯过程研究[J]. 计算机工程, 2023, 49(1): 65-72.
[4]	谢柏林, 黎琦, 魏娜, 邝建. 基于用户行为的社交网络人格特质识别方法[J]. 计算机工程, 2023, 49(1): 279-286,294.
[5]	梁登玉, 刘大明. 融合多粒度信息与外部知识的短文本匹配模型[J]. 计算机工程, 2022, 48(8): 129-135,143.
[6]	刘振国, 李钊, 宋滕滕, 何益智. 结合可变形卷积与双边网格的立体匹配网络[J]. 计算机工程, 2022, 48(12): 241-247,254.
[7]	许乐, 安虹, 陈俊仕, 张鹏飞, 武铮. 基于神威·太湖之光的非结构网格计算加速算法[J]. 计算机工程, 2022, 48(12): 45-53.
[8]	王斌, 王忠民, 张荣. 基于多通道脑电信号的因果网络情绪识别[J]. 计算机工程, 2022, 48(1): 69-74.
[9]	叶青, 赵楠楠, 赵宗渠, 秦攀科, 闫玺玺, 汤永利. 格上高效的完全动态群签名方案[J]. 计算机工程, 2021, 47(2): 160-167,175.
[10]	陈志鹏, 郑文秀, 黄琼丹. 基于Sobel滤波器的图像风格转换算法[J]. 计算机工程, 2021, 47(12): 274-277,284.
[11]	陈佳, 董学良, 梁金星, 何儒汉. 基于注意力机制的CycleGAN服装局部风格迁移研究[J]. 计算机工程, 2021, 47(11): 305-312.
[12]	刘期烈, 陈澄. 基于区块链的V2G匿名身份认证方案[J]. 计算机工程, 2021, 47(11): 22-28.
[13]	邓志辉, 王少辉, 王平. 基于合数阶双线性对的可搜索加密方案分析与改进[J]. 计算机工程, 2020, 46(9): 123-128,135.
[14]	卢嘉嘉, 杜育松. 整数上离散高斯取样的常数时间实现方法[J]. 计算机工程, 2020, 46(8): 119-123.
[15]	赵宗渠, 黄鹂娟, 范涛, 马少提. 格上基于KEM的认证密钥交换协议[J]. 计算机工程, 2020, 46(7): 122-128.

选择文件类型/文献管理软件名称

选择包含的内容