Forward Secure Lattice-Based Sequential Aggregate Signature Schemes in Stan-dard Model

doi:10.3778/j.issn.1673-9418.2104028

Abstract

Abstract:

In the forward secure sequential aggregate (FssAgg) signature scheme, the signer combines signatures generated in different intervals under different secret keys incrementally and sequentially in a layered “onion-like” fashion with the first signature innermost in the aggregate. In contrast with general (not forward-secure) aggregate signature schemes which aggregate signatures from multiple signers, a FssAgg signature scheme aggregates signatures of a single signer not the signatures of different signers, so the verifier uses a single public key to verify the entire aggregate. With the advantages of forward secure signature and the aggregate signature at the same time, the FssAgg signature scheme has been widely applied in logging systems and blockchain since it was proposed in 2007. Although there have been several FssAgg signature schemes, all of them are based on the classic number theory problem, which are no longer secure in the quantum era. So looking for the quantum-immune FssAgg signature is much urgent. Based on the small integer solution over lattice, a FssAgg signature in the standard model is proposed. In order to improve the efficiency, this paper uses the fixed-dimensional lattice basis delegation technique to update the keys, and the forward security is achieved. This paper uses the message addition technique and the pre-image sampling technique to embed the message and the small integer solution into the signature process, and the existentially unforgeability of the scheme is also guranteed in the standard model.

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

摘要：

在前向安全有序聚合（FssAgg）签名系统中，签名人以分层的“洋葱式”的方式，将不同时段不同密钥下的签名逐步有序地聚合成一个签名。其中，最内层的签名是第一个签名。另外，与普通的有序聚合签名相比，前向安全有序聚合签名是对同一个签名人不同签名的聚合，而非对不同签名人签名的聚合，因而签名验证者使用一个公钥即可完成对所有聚合过程的验证。前向安全的有序聚合签名兼具前向安全签名和聚合签名的优点，自2007年提出以来，已被广泛应用于日志系统、区块链等众多应用场景中。目前现存的几个前向安全的有序聚合签名都是基于传统数论问题的，而这一问题在后量子时代将会变得不再困难。因而，寻找量子计算环境下前向安全的有序聚合签名已迫在眉睫。基于格上的小整数解问题，构造了标准模型下前向安全的格基有序聚合签名方案。为达到高效率目的，方案借助于固定维数格基委派技术实现密钥更新，达到前向安全性；随后通过消息添加技术和原像采样算法分别将待签消息和格上困难问题嵌入到签名中，使得签名在标准模型下是不可伪造的。

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

XIE Jia, HU Yupu, GAO Juntao, WANG Baocang, JIANG Mingming. Forward Secure Lattice-Based Sequential Aggregate Signature Schemes in Stan-dard Model[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(10): 1912-1920.

谢佳, 胡予濮, 高军涛, 王保仓, 江明明. 标准模型下前向安全的格基有序聚合签名[J]. 计算机科学与探索, 2021, 15(10): 1912-1920.

References

[1] ANDERSON R. Two remarks on public key cryptology-invited lecture[C]//Proceedings of the 4th ACM Conference on Computer and Communications Security, Zurich, Apr 1-4, 1997. New York: ACM, 1997.
[2] LYSYANSKAYA A, MICALI S, REYZIN L, et al. Sequential aggregate signatures from trapdoor permutations[C]//LNCS 3027: Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, In-terlaken, May 2-6, 2004. Berlin, Heidelberg: Springer, 2004: 74-90.
[3] MA D, TSUDIK G. Extended abstract: forward-secure sequ-ential aggregate authentication[C]//Proceedings of the 2007 IEEE Symposium on Security and Privacy, Oakland, May 20-23, 2007. Piscataway: IEEE, 2007: 86-91.
[4] MA D. Practical forward secure sequential aggregate signa-tures[C]//Proceedings of the 2008 ACM Symposium on In-formation, Computer and Communications Security, Tokyo, Mar 18-20, 2008. New York: ACM, 2008: 341-352.
[5] WEI X J, ZHANG J H, LIU Z F, et al. Identity based aggre-gate signature scheme with forward security[J]. Computer Science, 2018, 45(6A): 387-391.
韦性佳, 张京花, 刘增芳, 等. 具有前向安全性质的基于身份的聚合签名方案[J]. 计算机科学, 2018, 45(6A): 387-391.
[6] WEI X J. Research on aggregate signature scheme with for-ward security[D]. Xining: Qinghai Normal University, 2018.
韦性佳. 具有前向安全性质的聚合签名方案研究[D]. 西宁: 青海师范大学, 2018.
[7] KIM J, OH H. FAS: forward secure sequential aggregate signatures for secure logging[J]. Information Sciences, 2019, 471: 115-131.
[8] WEI X J, LU D J. Forward secure aggregated signature scheme based on Chinese remainder theorem[J]. Computer Technology and Development, 2021, 31(4): 137-141.
韦性佳, 芦殿军. 基于中国剩余定理的前向安全的聚合签名方案[J]. 计算机技术与发展, 2021, 31(4): 137-141.
[9] LIAO X P. Security analysis and improvement of a forward security proxy blind signature scheme[J]. Microcomputer Applications, 2019, 35(3): 35-37.
廖小平. 一个前向安全代理盲签名的安全性分析与改进[J]. 微型电脑应用, 2019, 35(3): 35-37.
[10] ZHANG P, LI Y M. Forward secure elliptic curve digital signature scheme[J]. Computer Engineering and Applications, 2020, 56(1): 115-120.
张平, 栗亚敏. 前向安全的椭圆曲线数字签名方案[J]. 计算机工程与应用, 2020, 56(1): 115-120.
[11] HONG X, ZHANG X X. Forward secure group signature scheme based on Chinese remainder theorem[J]. Applica-tion Research of Computers, 2020, 37(9): 2806-2810.
洪璇, 张绪霞. 基于中国剩余定理的前向安全群签名方案[J]. 计算机应用研究, 2020, 37(9): 2806-2810.
[12] XIE J, HU Y P, JIANG M M. Lattice-based forward secure proxy signatures[J]. Journal of Computer Research and De-velopment, 2021, 58(3): 583-597.
谢佳, 胡予濮, 江明明. 前向安全的格基代理签名[J]. 计算机研究与发展, 2021, 58(3): 583-597.
[13] SHOR P W. Polynomial-time algorithms for prime factori-zation and discrete logarithms on a quantum computer[J]. SIAM Journal of Computing, 1997, 26(5): 1484-1509.
[14] 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.
[15] 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 Telecommunica-tions, 2015, 22(6): 36-44.
[16] 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.
[17] 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.
[18] GENTRY C, PEIKERT C, VAIKUNTANATHAN V. Trap-doors 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.
[19] AGRAWAL S, BONEH D, BOYEN X. Lattice basis delega-tion in fixed dimension and shorter-ciphertext hierarchical IBE[C]//LNCS 6223: Proceedings of the 30th Annual Cryp-tology Conference, Santa Barbara, Aug 15-19, 2010. Berlin, Heidelberg: Springer, 2010: 98-115.
[20] ALWENY J, PEIKERTZ C. Generating shorter bases for hard random lattices[J]. Theory of Computing Systems, 2011, 48(3): 535-553.
[21] BOYEN X. Lattice mixing and vanishing trapdoors: a frame-work 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.
[22] MICCIANCIO D, REGEV O. Worst-case to average-case reductions based on Gaussian measures[J]. SIAM Journal on Computing, 2007, 37(1): 267-302.
[23] EBRI N A, BEAK J, SHOUFAN A. Forward-secure identity-based signature: new generic constructions and their appli-cations[J]. Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications, 2013, 4(1): 32-54.
[24] NEVEN G. Efficient sequential aggregate signed data[C]//LNCS 4965: Proceedings of the 27th Annual International Conference on the Theory and Applications of Cryptogra-phic Techniques, Istanbul, Apr 13-17, 2008. Berlin, Heidel-berg: Springer, 2008: 52-69.