The quantum-resistant digital signature schemes based on new hard problems
DOI:
https://doi.org/10.54939/1859-1043.j.mst.107.2025.114-125Keywords:
Digital signature; Quantum-resistant; Post-quantum; Discrete logarithm; Novel hard problems.Abstract
In this paper, we propose a family of quantum-resistant digital signature schemes built on novel hard problems defined over finite fields. These problems are, to the best of current knowledge, computationally intractable and therefore not susceptible to Shor’s quantum algorithm. Based on these problems, we present three concrete signature schemes with standard key-generation, signing, and verification procedures. We prove the correctness of each scheme and analyze its security against secret-key recovery and forgery attacks. Performance comparisons with representative post-quantum candidates illustrate that the proposed schemes achieve competitive key and signature sizes and efficient signing/verification times, making them attractive for practical deployment.
References
[1]. Luu Hong Dung, Nguyen Kim Tuan, Nong Phuong Trang, Pham Van Quoc, “A solution for constructing quantum-resistant digital signature schems”, Journal of Military Science and Technology, ISSN 1859–1043, pp. 108–118, (2024), DOI: 10.54939/1859-1043.j.mst.CSCE8.2024.108-118.
[2]. P. W. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring”, Proceedings of the 35th Symposium on Foundations of Computer Science, pp. 124–134, (1994).
[3]. P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM Journal of Computing, vol. 26, no. 5, pp. 1484–1509, (1997).
[4]. M. Eker, “Modifying Shor's algorithm to compute short discrete logarithms”, IACR ePrint Archive, Report 2016/1128, (2016).
[5]. L. C. Washington, “Elliptic Curves. Number Theory and Cryptography”, Chapman & Hall/CRC, (2008).
[6]. Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, “An Introduction to Mathematical Cryptography”, Springer-Verlag, ISBN 978-0-387-77993-5, (2008).
[7]. J. Talbot, D. Welsh, “Complexity and Cryptography: An Introduction”, Cambridge University Press, (2006).
[8]. I. Shparlinski, “Cryptographic Applications of Analytic Number Theory. Complexity Lower Bounds and Pseudorandomness”, Birkhäuser, (2003).
[9]. S. S. Wagstaff, “Cryptanalysis of Number Theoretic Ciphers”, Chapman & Hall/CRC, (2003).
[10]. ISO/IEC 14888-3, “Information technology – Security techniques – Digital signatures with appendix”, (2006).
[11]. National Institute of Standards and Technology, “NIST FIPS PUB 186-4. Digital Signature Standard”, U.S. Department of Commerce, (2013).
[12]. GOST R 34.10-94, “Russian Federation Standard. Information Technology. Cryptographic Data Security”, Government Committee for Standards, (1994).
[13]. Federal Information Processing Standards Publication 180-4 (FIPS PUB 180-4), “Secure Hash Standard (SHS)”, (2015).
[14]. ISO/IEC 15946, “Information technology – Security techniques – Cryptographic Techniques Based on Elliptic Curves”, (1999).
[15]. ANSI X9.62, “Public Key Cryptography for the Financial Services Industry: Elliptic Curve Digital Signature Algorithm (ECDSA)”, (1999).
[16]. National Institute of Standards and Technology, “NIST FIPS PUB 186-4. Digital Signature Standard”, (2013).
[17]. GOST R34.10–2012, “Russian Federation Standard Information Technology”, Government Committee for Standards, (2012).
[18]. L. Ducas et al., “CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme”, NIST PQC Round 3 Submission, (2020), https://pq-crystals.org/dilithium/.
[19]. P. A. Fouque et al., “Falcon: Fast-Fourier Lattice-Based Compact Signatures Over NTRU”, NIST PQC Round 3 Submission, (2020), https://falcon-sign.info/.
[20]. A. Hülsing et al., “SPHINCS+: Submission to the NIST Post-Quantum Project”, (2020), https://sphincs.org/.
