Quantum-Resistant Forward-Secure Digital Signature Scheme Based on q-ary Lattices

• Autorzy: Jurkiewicz Mariusz

Identyfikatory

DOI

10.26636/jtit.2024.2.1581

• Języki publikacji: EN

Abstrakty

EN

In this paper, we design and consider a new digital signature scheme with an evolving secret key, using random q-ary lattices as its domain. It is proved that, in addition to offering classic eu-cma security, the scheme is existentially forward unforgeable under an adaptive chosen message attack (fu-cma). We also prove that the secret keys are updated without revealing anything about any of the keys from the prior periods. Therefore, we design a polynomial-time reduction and use it to show that the ability to create a forgery leads to a feasible method of solving the well-known small integer solution (SIS) problem. Since the security of the scheme is based on computational hardness of a SIS problem, it turns out to be resistant to both classic and quantum methods. In addition, the scheme is based on the "Fiat-Shamir with aborts" approach that foils a transcript attack. As for the key-updating mechanism, it is based on selected properties of binary trees, with the number of leaves being the same as the number of time periods in the scheme. Forward security is gained under the assumption that one out of two hash functions is modeled as a random oracle.

Słowa kluczowe

EN

digital signature scheme; forward security; q-ary lattices; random-oracle model; SIS problem

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2024
• Tom: nr 2
• Strony: 90--103
• Opis fizyczny: Bibliogr. 23 poz., rys., tab.

Twórcy

autor

Jurkiewicz Mariusz

• Military University of Technology, Warsaw, Poland

• https://orcid.org/0000-0002-6314-4381

Bibliografia

• [1] M. Jurkiewicz, "Binary Tree Based Forward Secure Signature Scheme in the Random Oracle Model", International Journal of Electronics and Telecommunications, vol. 67, no. 4, pp. 717-726, 2021.
• [2] M. Bellare and S.K. Miner, "A Forward-Secure Digital Signature Scheme", Advances in Cryptology - CRYPTO ’99, vol. 1666, pp. 431-448, 1999.
• [3] J. Buchmann, E. Dahmen, and A. Hülsing, "XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions", Post-Quantum Cryptography, vol. 7071, pp. 117-129, 2010.
• [4] L. Ducas et al., "Crystals-dilithium: A Lattice-based Digital Signature Scheme", IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2018, pp. 238-268, 2018.
• [5] V. Lyubashevsky, "Lattice Signatures without Trapdoors", Advances in Cryptology - EUROCRYPT 2012, pp. 738-755, 2012.
• [6] D. Cash, D. Hofheinz, E. Kiltz, and C. Peikert, "Bonsai Trees, or How to Delegate a Lattice Basis", Advances in Cryptology - EUROCRYPT 2010, vol. 6110, pp. 601-639, 2012.
• [7] P. Zhang et al., "A New Post-Quantum Blind Signature from Lattice Assumptions", IEEE Access, vol. 6, pp. 27251-27258, 2018.
• [8] O. Goldreich, Foundations of Cryptography: Volume 1, Basic Tools, Cambridge University Press, 396 p., 2003 (ISBN: 9780521035361).
• [9] D. Pointcheval and J. Stern, "Provably Secure Blind Signature Schemes", Advances in Cryptology - ASIACRYPT '96, pp. 252-265, 1996.
• [10] M. Bellare and G. Neven, "Multi-signatures in the Plain Public-key Model and a General Forking Lemma", Proceedings of the 13th ACM Conference on Computer and Communications Security, pp. 390-399, 2006.
• [11] C. Peikert, A Decade of Lattice Cryptography, Now Foundations and Trends, 156 p., 2015.
• [12] D. Micciancio and S. Goldwasser, Complexity of Lattice Problems. A Cryptographic Perspective, Springer Science & Business Media, 220 p., 2002.
• [13] D. Micciancio and O. Regev, "Worst-Case to Average-Case Reductions Based on Gaussian Measures", 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004.
• [14] O. Regev, "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography", Journal of the ACM, vol. 56, no. 6, pp. 1-40, 2009.
• [15] C. Peikert and A. Rosen, "Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices", Theory of Cryptography, vol. 3876, pp. 145-166, 2006.
• [16] C. Peikert, "An Efficient and Parallel Gaussian Sampler for Lattices", Advances in Cryptology - CRYPT 2010, vol. 6223, pp. 80-97, 2010.
• [17] C. Gentry, C. Peikert, and V. Vaikuntanathan, "Trapdoors for Hard Lattices and New Cryptographic Constructions", Proceedings of the fortieth Annual ACM Symposium on Theory of Computing, pp. 197-206, 2008.
• [18] M. Ajtai, "Generating Hard Instances of Lattice Problems", Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 99-108, 1996.
• [19] J. Alwen and C. Peikert, "Generating Shorter Bases for Hard Random Lattices", Theory of Computing Systems, vol. 48, no. 3, pp. 535-553, 2011.
• [20] S. Agrawal, D. Boneh, and X. Boyen, "Efficient Lattice (H)IBE in the Standard Model", Advances in Cryptology - EUROCRYPT 2010, vol. 6110, pp. 553-572, 2010.
• [21] N. Gama and P.Q. Nguyen, "Predicting Lattice Reduction", Advances in Cryptology - EUROCRYPT 2008, vol. 4965, pp. 31-51, 2008.
• [22] Y. Chen and P.Q. Nguyen, "BKZ 2.0: Better Lattice Security Estimates", Advances in Cryptology - ASIACRYPT 2011, pp. 1-20, 2011.
• [23] D. Micciancio and O. Regev, "Lattice-based Cryptography", in: Post-Quantum Cryptography, ed. D.J. Bernstein, J. Buchmann, E. Dahmen, pp. 147-191, Springer, 2009.