Forward Secure Sequential Aggregate Signature Schemes on Lattice

doi:10.3778/j.issn.1673-9418.2102004

Abstract

Abstract:

The forward secure sequential aggregate (Fss-Agg) signature has the advantages of forward secure signature and the sequential aggregate signature at the same time. Since its proposal in 2007, it has been widely applied in many application scenarios, such as logging systems, e-business, e-government, blockchain, etc. Although there have been several Fss-Agg signature schemes, all of them are based on the classic number theory problem, which are no longer secure in the quantum era when the general quantum computers become reality. So looking for the quantum-immune Fss-Agg signature is much urgent. In this paper, the definition of Fss-Agg signature scheme is described, and the forward security and the existential unforgeability under the chosen message attack are combined to define the existential unforgeability of Fss-Agg signature aganist chosen message attack. Based on the small integer solution assumption on lattice, using the pre-image sampling and the lattice basis delegation techniques, the quantum-immune Fss-Agg signature is proposed, which is the first lattice-based Fss-Agg signature scheme. It is proven to be correct, forward secure and existentially unforgeable in the random oracle model.

Key words: lattice, sequential aggregate signature, forward secure, unforgeability, quantum-immune, small integer solution

摘要：

前向安全的有序聚合（Fss-Agg）签名兼顾前向安全签名和有序聚合签名的优势。自2007年提出以来，前向安全的有序聚合签名已被广泛应用于日志系统、电子商务、电子政务、区块链等众多应用场景中。目前现存的几个前向安全的有序聚合签名都是基于传统数论问题，而这些问题随着量子计算机逐渐成为现实，将会变得不再困难。因而，寻找量子计算环境下前向安全的有序聚合签名已迫在眉睫。给出了前向安全有序聚合签名方案的定义，并将前向安全性和存在性不可伪造性两个特性结合，定义了选择消息攻击下有序聚合签名的前向安全的存在性不可伪造性；基于格上的小整数解问题，利用原像采样算法和格基委派技术构造了抗量子攻击的前向安全有序聚合签名方案，即格上首个前向安全的有序聚合签名方案，方案在随机预言机模型下满足正确性和前向安全的存在性不可伪造性。

关键词: 格, 有序聚合签名, 前向安全, 不可伪造性, 抗量子攻击, 小整数解

XIE Jia, HU Yupu, GAO Juntao, WANG Baocang, JIANG Mingming. Forward Secure Sequential Aggregate Signature Schemes on Lattice[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(9): 1658-1666.

谢佳, 胡予濮, 高军涛, 王保仓, 江明明. 格上前向安全的有序聚合签名[J]. 计算机科学与探索, 2021, 15(9): 1658-1666.

References

[1] ANDERSON R. Two remarks on public key cryptology[C]// Proceedings of the 4th ACM Conference on Computer and Communications Security, Zurich, Apr 1-4, 1997. New York: ACM, 1997.
[2] BONEH D, GENTRY C, LYNN B, et al. Aggregate and verifiably encrypted signatures from bilinear maps[C]//LNCS 2656: Proceedings of the 2003 International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, May 4-8, 2003. Berlin, Heidelberg: Springer, 2003: 416-432.
[3] LYSYANSKAYA A, MICALI S, REYZIN L, et al. Sequential aggregate signatures from trapdoor permutations[C]//LNCS 3027: Proceedings of the 2004 International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, May 2-6, 2004. Berlin, Heidelberg: Springer, 2004: 74-90.
[4] MA D, TSUDIK G. Extended abstract: forward-secure sequential aggregate authentication[C]//Proceedings of the 2007 IEEE Symposium on Security and Privacy, Oakland, May 20-23, 2007. Piscataway: IEEE, 2007: 86-91.
[5] BONEH D, LYNN B, SHACHAM H. Short signatures from the weil pairing[C]//LNCS 2248: Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Dec 9-13, 2001. Berlin, Heidelberg: Springer, 2001: 514-532.
[6] MA D. Practical forward secure sequential aggregate signatures[C]//Proceedings of the 2008 ACM Symposium on Information, Computer and Communications Security, Tokyo, Mar 18-20, 2008. New York: ACM, 2008: 341-352.
[7] WEI X J, ZHANG J H, LIU Z F, et al. Identity based aggregate signature scheme with forward security[J]. Computer Science, 2018, 45(S1): 387-391.
韦性佳, 张京花, 刘增芳, 等. 具有前向安全性质的基于身份的聚合签名方案[J]. 计算机科学, 2018, 45(S1): 387-391.
[8] WEI X J. Research on aggregate signature scheme with forward security[D]. Xining: Qinghai Normal University, 2018.
韦性佳. 具有前向安全性质的聚合签名方案研究[D]. 西宁: 青海师范大学, 2018.
[9] KIM J, OH H. FAS: forward secure sequential aggregate signatures for secure logging[J]. Information Sciences, 2019, 471: 115-131.
[10] SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal of Computing, 1997, 26(5): 1484-1509.
[11] El BANSARKHANI R, BUCHMANN J. Towards lattice based aggregate signatures[C]//LNCS 8469: Proceedings of the 7th International Conference on Cryptology in Africa, Marrakesh, May 28-30, 2014. Cham: Springer, 2014: 336-355.
[12] ZHANG Y H, HU Y P, JIANG M M, et al. Lattice-based sequential aggregate signatures with lazy verification[J]. The Journal of China Universities of Posts and Telecommunications, 2015, 22(6): 36-44.
[13] LU X, YIN W, WEN Q, et al. A lattice-based unordered agg-regate signature scheme based on the intersection method[J]. IEEE Access, 2018, 6: 33986-33994.
[14] WANG Z P, WU Q H. A practical lattice-based sequential aggregate signature[C]//LNCS 11821: Proceedings of the 13th International Conference on Provable Security, Cairns, Oct 1-4, 2019. Cham: Springer, 2019: 94-109.
[15] GENTRY C, PEIKERT C, VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions[C]//Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, May 17-20, 2008. New York: ACM, 2008: 197-206.
[16] AGRAWAL S, BONEH D, BOYEN X. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE[C]//LNCS 6223: Proceedings of the 30th Annual Cryptology Conference, Santa Barbara, Aug 15-19, 2010. Berlin, Heidelberg: Springer, 2010: 98-115.
[17] ALWENY J, PEIKERTZ C. Generating shorter bases for hard random lattices[J]. Theory of Computing Systems, 2011, 48(3): 535-553.
[18] BOYEN X. Lattice mixing and vanishing trapdoors: a framework for fully secure short signature and more[C]//LNCS 6056: Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, May 26-28, 2010. Berlin, Heidelberg: Springer, 2010: 499-517.
[19] MICCIANCIO D, REGEV O. Worst-case to average-case reductions based on Gaussian measures[J]. SIAM Journal on Computing, 2007, 37(1): 267-302.
[20] EBRI N A, BEAK J, SHOUFAN A. Forward-secure identity-based signature: new generic constructions and their applications[J]. Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications, 2013, 4(1): 32-54.
[21] NEVEN G. Efficient sequential aggregate signed data[C]//LNCS 4965: Proceedings of the 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Apr 13-17, 2008. Berlin, Heidelberg: Springer, 2008: 52-69.
[22] STEHLé D, STEINFELD R. Making NTRU as secure as worst-case problems over ideal lattices[C]//LNCS 6632: Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, May 15-19, 2011. Berlin, Heidelberg: Springer, 2011: 27-47.