Certificateless threshold signature from lattice

Abstract

Threshold signature has been widely used in electronic wills, electronic elections, cloud computing, secure multi-party computation and other fields. Until now, certificateless threshold signature schemes are all based on traditional mathematic theory, so they cannot resist quantum computing attacks. In view of this, we combine the advantages of lattice-based cryptosystem and certificateless cryptosystem to construct a certificateless threshold signature from lattice (LCLTS) that is efficient and resistant to quantum algorithm attacks. LCLTS has the threshold characteristics and can resist the quantum computing attacks, and the analysis shows that it is unforgeable against the adaptive Chosen-Message Attacks (UF-CMA) with the difficulty of Inhomogeneous Small Integer Solution (ISIS) problem. In addition, LCLTS solves the problems of the certificate management through key escrow.

Keywords

Lattice / Threshold signature / Inhomogeneous small integer solution / Certificateless public key / Lattice sampling technique

References

[1] W. Diffie, M. Hellman, New directions in cryptography, IEEE Trans. Inf. Theor. 22 (6) (1976) 644-654.

[2] Y. Desmedt, Y. Frankel, Threshold cryptosystems, in: Conference on the Theory and Application of Cryptology, Springer, 1989, pp. 307-315.

[3] L. Harn,Group-oriented (t,n) threshold digital signature scheme and digital multisignature, IEE Proc. Comput. Digit. Tech. 141 (5) (1994) 307-313.

[4] B. Wang, J. Li, (t,n) threshold signature scheme without a trusted party, Chin. J. Comput. Chin. Ed 26 (11) (2003) 1581-1584.

[5] X. Qi, Y. Xiu-Yuan, A new (t,n) threshold signature scheme withstanding the conspiracy attack, Wuhan Univ. J. Nat. Sci. 10 (1) (2005) 107-110.

[6] G. Wang, S. Qing, M. Wang, Improvement of shoup's threshold rsa signature scheme, Comput. Res. Dev. 39 (9) (2002) 1046-1050.

[7] X. Fu, Proactive threshold rsa signature scheme based on polynomial secret sharing, J. Electron. Inf. Technol. 38 (9) (2016) 2280-2286.

[8] Y. Harchol, I. Abraham, B. Pinkas, Distributed ssh key management with proactive rsa threshold signatures, in: International Conference on Applied Cryptography and Network Security, Springer, 2018, pp. 22-43.

[9] V. Shoup, Practical threshold signatures, in: International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 2000, pp. 207-220.

[10] Q.-L. Xu, T.-S. Chen, An efficient threshold rsa digital signature scheme, Appl. Math. Comput. 166 (1) (2005) 25-34.

[11] P.W. Shor, Algorithms for quantum computation: discrete logarithms and factoring,in:Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994, pp. 124-134.

[12] M. Ajtai, Generating hard instances of the short basis problem, in:International Colloquium on Automata, Languages, and Programming, Springer, 1999, pp. 1-9.

[13] R. Bendlin, S. Krehbiel, C. Peikert, How to share a lattice trapdoor: threshold protocols for signatures and (h) ibe,in: International Conference on Applied Cryptography and Network Security, Springer, 2013, pp. 218-236.

[14] D. Micciancio, C. Peikert, Trapdoors for lattices: simpler, tighter, faster, smaller,in: Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 2012, pp. 700-718.

[15] D. Boneh, R. Gennaro, S. Goldfeder, S. Kim, A lattice-based universal thresholdizer for cryptographic systems, IACR Cryptol. ePrint Arch. 2017 (2017) 251.

[16] P.-L. Cayrel, R. Lindner, M. Rückert, R. Silva, A lattice-based threshold ring signature scheme, in: International Conference on Cryptology and Information Security in Latin America, Springer, 2010, pp. 255-272.

[17] S. Bettaieb, J. Schrek, Improved lattice-based threshold ring signature scheme, in: International Workshop on Post-Quantum Cryptography, Springer, 2013, pp. 34-51.

[18] S. Agrawal, X. Boyen, V. Vaikuntanathan, P. Voulgaris, H. Wee, Fuzzy identity based encryption from lattices, IACR Cryptol. ePrint Arch. 2011 (2011) 414.

[19] A. Shamir, How to share a secret, Commun. ACM 22 (11) (1979) 612-613.

[20] C. Gentry, C. Peikert, V. Vaikuntanathan,Trapdoors for hard lattices and new cryptographic constructions, in:Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, 2008, pp. 197-206.

[21] S. Agrawal, D. Boneh, X. Boyen, Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical ibe, in: Annual Cryptology Conference, Springer, 2010, pp. 98-115.

[22] B. Yang, Modern Cryptography, Tsinghua University Press, 2017.

[23] T.-T. Tsai, Y.-M. Tseng, Revocable certificateless public key encryption, IEEE Syst. J. 9 (3) (2013) 824-833.

[24] C.J. Zhuang L S, W.Q. Y, Lattice-based linkable threshold ring signature in e-voting, J. Cryptologic Res. 8 (3) (2020) 402-416.

[25] H. Pilaram, T. Eghlidos, R. Toluee, An efficient lattice-based threshold signature scheme using multi-stage secret sharing, IET Inf. Secur. 15 (1) (2021) 98-106.