Schnorr方案推广及其在格密码学中的应用

doi:10.3969/j.issn.1000-3428.2014.04.025

计算机工程

Schnorr方案推广及其在格密码学中的应用

巩博儒^1a，赵运磊^1b，Rudolf Fleischer ^1a,2,3，王晓阳^1a

(1. 复旦大学 a. 计算机科学技术学院；b. 软件学院，上海 201203； 2. 上海市智能信息处理重点实验室，上海 200433；3. 德国科技大学阿曼分校应用信息技术学院，阿曼马斯喀特 1816)

收稿日期:2013-05-10 出版日期:2014-04-15 发布日期:2014-04-14
作者简介:巩博儒(1982－)，男，硕士研究生，主研方向：计算复杂性理论，密码学；赵运磊，副教授、博士生导师；Rudolf Fleischer、王晓阳，教授、博士生导师。
基金项目:
国家自然科学基金资助项目(61070248, 61272012)；上海市教育委员会科研创新基金资助项目(12ZZ013)；上海市重点学科建设基金资助项目(B114)；上海科学技术委员会基金资助项目(08DZ2271800, 09DZ2272800)。

Generalization of Schnorr Scheme and Its Application in Lattice Cryptography

GONG Bo-ru ^1a, ZHAO Yun-lei ^1b, Rudolf Fleischer ^1a,2,3, WANG Xiao-yang^1a

(1a. School of Computer Science; 1b. Software School, Fudan University, Shanghai 201203, China; 2. Shanghai Key Laboratory of Intelligent Information Processing, Shanghai 200433, China; 3. Department of Applied Information Technology, German University of Technology in Oman, Muscat 1816, Oman)

Received:2013-05-10 Online:2014-04-15 Published:2014-04-14

摘要/Abstract

摘要： Schnorr身份认证方案是密码学中的经典方案，可以推广到很多其他数学问题(如离散对数问题)上，从而构造出在标准模式中安全的身份认证方案，并且可以通过Fiat-Shamir转换工具，将其转换为在随机谕示模式中安全的数字签名方案。但将上述转换方法用于基于格的密码学中时会出现一些特殊现象(如方案中止现象)。为此，通过矩阵表示方法分析Schnorr方案的构造方法，得出其构造方法成立的充要条件，从而使其可在更大范围内构造出安全的类Schnorr方案。根据类Schnorr方案，分析基于格的身份认证方案中的方案中止现象，并通过数学方法证明，对于某些身份认证方案(如∑-身份认证方案)，其中的方案中止现象不可避免，该结论为深入研究基于格的密码学提供了参考依据。

关键词: Schnorr签名方案, 身份认证方案, 数字签名, 基于格的密码学, Fiat-Shamir转换, 方案中止

Abstract: As one of classic identification schemes in cryptography, Schnorr’s scheme can be applied with respect to many underlying mathematical hard problems, as well as discrete logarithm problem. Moreover, it can apply the Fiat-Shamir transform to convert a secure Schnorr’s identification scheme in standard model into a secure digital signature scheme in the random oracle model. Aiming at the condition, this paper analyzes the features of Schnorr’s scheme, the necessary and sufficient conditions for a secure Schnorr’s scheme are derived, and hence it can construct the secure Schnorr-like scheme in a broader sense. Then, by using the concept of Schnorr-like scheme, it can prove rigorously that the existence of aborts in some lattice-based identification scheme, such as ∑-identity authentication scheme is inevitable, which sheds light on a better understanding of the lattice-based signature in the future.

Key words: Schnorr signature scheme, identity authentication scheme, digital signature, lattice-based cryptography, Fiat-Shamir transform, scheme abort

中图分类号:

TP391.4

巩博儒，赵运磊，Rudolf Fleischer，王晓阳. Schnorr方案推广及其在格密码学中的应用[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2014.04.025.

GONG Bo-ru, ZHAO Yun-lei, Rudolf Fleischer, WANG Xiao-yang. Generalization of Schnorr Scheme and Its Application in Lattice Cryptography[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2014.04.025.

参考文献

(上接第135页) 参考文献 [1] Schnorr C P. Efficient Identification and Signatures for Smart Cards[C]//Proceedings of CRYPTO’89. New York, USA: Springer-Verlag, 1989: 239-252. [2] Ajtai M. Generating Hard Instances of Lattice Problems (Extended Abstract)[C]//Proceedings of the 28th Annual ACM Symposium on Theory of Computing. Philadephia, USA: ACM Press, 1996: 99-108. [3] Lyubashevsky V. Lattice-based Identification Schemes Secure Under Active Attacks[C]//Proceedings of 11th International Workshop on Practice and Theory in Public-Key Cryptography. Barcelona, Spain: [s. n.], 2008: 162-179. [4] Lyubashevsky V. Fiat-Shamir with Aborts: Applications to lattice and Factoring-based Signatures[C]//Proceedings of ASIACRYPT’09. Tokyo, Japan: ACM Press, 2009: 598-616. [5] Lyubashevsky V, Palacio A. Public-key Cryptographic Primi- tives Provably As Secure As Subset Sum[C]//Proceedings of TCC’10. Zurich, Switzerland: [s. n.], 2010: 382-400. [6] Abdalla M, Fouque P A, Lyubashevsky V. Tightly-secure Signatures from Lossy Identification Schemes[C]// Proceedings of the 31st Annual International Conference on Theory and Applications of Cryptographic Techniques. Cambridge, UK: ACM Press, 2012: 572-590. [7] Katz J. Digital Signature[M]. [S. l.]: Springer, 2010. [8] Katz J. Introduction to Modern Cryptography: Principles and Protocols[M]. [S. l.]: Chapman & Hall/CRC Press, 2007. [9] Goldreich O. Foundations of Cryptography: Volume 1, Basic Tools[M]. [S. l.]: Cambridge University Press, 2007. [10] Alfred J. Menezes: Handbook of Applied Cryptography (Discrete Mathematics and Its Applications)[M]. [S. l.]: CRC Press, 1996. [11] Micciancio D, Goldwasser S. Complexity of Lattice Problems: A Cryptographic Perspective[M]. [S. l.]: Springer, 2002. [12] 王小云. 公钥密码学的数学基础[M]. 北京: 科学出版社, 2013. [13] Micciancio D, Regev O. Worst-case to Average-case Reductions Based on Gaussian Measure[J]. SIAM Journal on Computing, 2007, 37(1): 267-302. 编辑陆燕菲

[1]	赵宗渠, 黄鹂娟, 范涛, 马少提. 格上基于KEM的认证密钥交换协议[J]. 计算机工程, 2020, 46(7): 122-128.
[2]	廖方圆, 甘植旺. Android系统签名的漏洞分析与检测[J]. 计算机工程, 2019, 45(8): 25-30.
[3]	左黎明,周庆,陈兰兰. 一种可证安全高效无证书短签名方案[J]. 计算机工程, 2019, 45(6): 193-198.
[4]	左黎明, 夏萍萍, 陈祚松. 一种可证安全的短盲签名方案[J]. 计算机工程, 2019, 45(12): 114-118.
[5]	冯超逸,赵一鸣. 基于理想格的可证明安全数字签名方案[J]. 计算机工程, 2017, 43(5): 103-107.
[6]	刘雨阳,赵一鸣. 白盒可追踪的属性签名方案[J]. 计算机工程, 2017, 43(4): 126-132,140.
[7]	简春福,谢吉华,金钧华. 云端数字签名技术的研究与应用[J]. 计算机工程, 2017, 43(12): 1-5.
[8]	黄彬,刘广钟,徐明. 基于簇的无线传感器网络安全节点认证协议[J]. 计算机工程, 2016, 42(7): 117-122,128.
[9]	徐海峰,洪璇. 可证明安全的单向可变门限代理重签名方案[J]. 计算机工程, 2016, 42(4): 143-146,154.
[10]	汤永利,王菲菲,闫玺玺,李子臣. 高效可证明安全的无证书签名方案[J]. 计算机工程, 2016, 42(3): 156-160.
[11]	冯泽宇,巩博儒,赵运磊. 基于离散对数的数字签名标准对比研究[J]. 计算机工程, 2016, 42(1): 145-149.
[12]	党佳莉,俞惠芳. 使用中国剩余定理的群签名方案[J]. 计算机工程, 2015, 41(2): 113-116.
[13]	黄茹芬，农强，黄振杰. 可证安全的基于证书部分盲签名方案[J]. 计算机工程, 2014, 40(6): 109-114.
[14]	程文娟，董莹莹，韩俊光. 一种简单高效的密封式电子拍卖方案[J]. 计算机工程, 2014, 40(3): 171-174.
[15]	牟雁飞,赵一鸣. 一种基于格的可证明安全数字签名方案[J]. 计算机工程, 2014, 40(12): 94-96,103.

Schnorr方案推广及其在格密码学中的应用

Generalization of Schnorr Scheme and Its Application in Lattice Cryptography

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10