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

Authors

DOI:

https://doi.org/10.26636/jtit.2024.2.1581

Keywords:

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

Abstract

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.

Downloads

Download data is not yet available.

References

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. DOI: https://doi.org/10.24425/ijet.2021.137868
View in Google Scholar

M. Bellare and S.K. Miner, "A Forward-Secure Digital Signature Scheme", Advances in Cryptology - CRYPTO ’99, vol. 1666, pp. 431-448, 1999. DOI: https://doi.org/10.1007/3-540-48405-1_28
View in Google Scholar

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. DOI: https://doi.org/10.1007/978-3-642-25405-5_8
View in Google Scholar

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. DOI: https://doi.org/10.46586/tches.v2018.i1.238-268
View in Google Scholar

V. Lyubashevsky, "Lattice Signatures without Trapdoors", Advances in Cryptology - EUROCRYPT 2012, pp. 738-755, 2012. DOI: https://doi.org/10.1007/978-3-642-29011-4_43
View in Google Scholar

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. DOI: https://doi.org/10.1007/s00145-011-9105-2
View in Google Scholar

P. Zhang et al., "A New Post-Quantum Blind Signature from Lattice Assumptions", IEEE Access, vol. 6, pp. 27251-27258, 2018. DOI: https://doi.org/10.1109/ACCESS.2018.2833103
View in Google Scholar

O. Goldreich, Foundations of Cryptography: Volume 1, Basic Tools, Cambridge University Press, 396 p., 2003 (ISBN: 9780521035361).
View in Google Scholar

D. Pointcheval and J. Stern, "Provably Secure Blind Signature Schemes", Advances in Cryptology - ASIACRYPT '96, pp. 252-265, 1996. DOI: https://doi.org/10.1007/BFb0034852
View in Google Scholar

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. DOI: https://doi.org/10.1145/1180405.1180453
View in Google Scholar

C. Peikert, A Decade of Lattice Cryptography, Now Foundations and Trends, 156 p., 2015. DOI: https://doi.org/10.1561/9781680831139
View in Google Scholar

D. Micciancio and S. Goldwasser, Complexity of Lattice Problems. A Cryptographic Perspective, Springer Science & Business Media, 220 p., 2002. DOI: https://doi.org/10.1007/978-1-4615-0897-7
View in Google Scholar

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.
View in Google Scholar

O. Regev, "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography", Journal of the ACM, vol. 56, no. 6, pp. 1-40, 2009. DOI: https://doi.org/10.1145/1568318.1568324
View in Google Scholar

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. DOI: https://doi.org/10.1007/11681878_8
View in Google Scholar

C. Peikert, "An Efficient and Parallel Gaussian Sampler for Lattices", Advances in Cryptology - CRYPT 2010, vol. 6223, pp. 80-97, 2010. DOI: https://doi.org/10.1007/978-3-642-14623-7_5
View in Google Scholar

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. DOI: https://doi.org/10.1145/1374376.1374407
View in Google Scholar

M. Ajtai, "Generating Hard Instances of Lattice Problems", Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 99-108, 1996. DOI: https://doi.org/10.1145/237814.237838
View in Google Scholar

J. Alwen and C. Peikert, "Generating Shorter Bases for Hard Random Lattices", Theory of Computing Systems, vol. 48, no. 3, pp. 535-553, 2011. DOI: https://doi.org/10.1007/s00224-010-9278-3
View in Google Scholar

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. DOI: https://doi.org/10.1007/978-3-642-13190-5_28
View in Google Scholar

N. Gama and P.Q. Nguyen, "Predicting Lattice Reduction", Advances in Cryptology - EUROCRYPT 2008, vol. 4965, pp. 31-51, 2008. DOI: https://doi.org/10.1007/978-3-540-78967-3_3
View in Google Scholar

Y. Chen and P.Q. Nguyen, "BKZ 2.0: Better Lattice Security Estimates", Advances in Cryptology - ASIACRYPT 2011, pp. 1-20, 2011. DOI: https://doi.org/10.1007/978-3-642-25385-0_1
View in Google Scholar

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. DOI: https://doi.org/10.1007/978-3-540-88702-7_5
View in Google Scholar

Downloads

Published

2024-06-10

Issue

Section

ARTICLES FROM THIS ISSUE

How to Cite

[1]
M. Jurkiewicz, “Quantum-Resistant Forward-Secure Digital Signature Scheme Based on q-ary Lattices”, JTIT, vol. 96, no. 2, pp. 90–103, Jun. 2024, doi: 10.26636/jtit.2024.2.1581.