Post-Quantum Digital Signatures over Finite Fields with Hidden Generators
Received: 9 July 2025 | Revised: 4 August 2025 | Accepted: 22 August 2025 | Online: 8 December 2025
Corresponding author: Ha Nguyen Hoang
Abstract
The advent of quantum computers poses a direct threat to the security of traditional digital signature schemes, which are based on the Rivest–Shamir–Adleman (RSA) and Elliptic Curve Cryptography (ECC) cryptosystems. Shor's algorithm allows solving the Discrete Logarithm Problem (DLP) in polynomial time, whereas Grover's algorithm significantly reduces the effort required for brute-force attacks on symmetric hash functions and ciphers. Although many post-quantum solutions have been proposed, such as lattice-based schemes (e.g., CRYSTALS-Dilithium, Falcon) or hash-based schemes (e.g., SPHINCS+), they still have some limitations to overcome, such as large public keys, bulky signatures, high computational costs, and difficulties in integrating into existing Public Key Infrastructures (PKIs). In this paper, we propose a new type of hard problem, defined over a finite prime field, in which the generator is kept secret to prevent any direct Shor attack and is only subject to a limited influence from Grover. Based on this newly proposed hard problem, we construct a post-quantum digital signature scheme that is both Shor-resistant and Grover-resistant, secure against classical attacks, and fully compatible with current PKI infrastructures. Compared with existing post-quantum digital signature schemes, our solution significantly optimizes the size of public keys and signatures while increasing the speed of signing and verification. The newly proposed hard problem cannot be solved by known classical or quantum algorithms, thus ensuring long-term security. Performance evaluation results show that the scheme provides an optimal balance between performance and security, opening up a cost-effective implementation path for the post-quantum cryptography era.
Keywords:
post-quantum digital signature, new hard problem, Shor's algorithm, Grover's algorithm, Public Key Infrastructure (PKI)Downloads
References
P. W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring," in Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 1994, pp. 124–134. DOI: https://doi.org/10.1109/SFCS.1994.365700
L. K. Grover, "A fast quantum mechanical algorithm for database search," in Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing, Philadelphia, PA, USA, 1996, pp. 212–219. DOI: https://doi.org/10.1145/237814.237866
L. Ducas et al., "CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme," IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2018, no. 1, pp. 238–268, Feb. 2018. DOI: https://doi.org/10.46586/tches.v2018.i1.238-268
P. Fouque et al., "Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU," Post-Quantum Cryptography Standard, Jan. 2020.
D. J. Bernstein, A. Hülsing, S. Kölbl, R. Niederhagen, J. Rijneveld, and P. Schwabe, "The SPHINCS+ Signature Framework," in Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, London, UK, 2019, pp. 2129–2146. DOI: https://doi.org/10.1145/3319535.3363229
J. Bos et al., "CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM," in 2018 IEEE European Symposium on Security and Privacy (EuroS&P), London, UK, 2018, pp. 353–367. DOI: https://doi.org/10.1109/EuroSP.2018.00032
A. Ali, M. a. H. Farquad, C. Atheeq, and C. Altaf, "A Quantum Encryption Algorithm based on the Rail Fence Mechanism to Provide Data Integrity," Engineering, Technology & Applied Science Research, vol. 14, no. 6, pp. 18818–18823, Dec. 2024. DOI: https://doi.org/10.48084/etasr.8993
D. Y. Guryanov, D. N. Moldovyan, and A. A. Moldovyan, "Post-quantum digital signature schemes: setting a hidden group with two-dimensional cyclicity," Informatization and communication, vol. 4, pp. 75–82, Nov. 2020. DOI: https://doi.org/10.34219/2078-8320-2020-11-4-75-82
A. A. Moldovyan, N. A. Moldovyan, D. N. Moldovyan, and A. A. Kostina, "A new approach to the development of digital signature algorithms based on the hidden discrete logarithm problem," Information Security Questions, no. 4 (135), pp. 45–49, 2021. DOI: https://doi.org/10.52190/2073-2600_2021_4_45
C. Battarbee, D. Kahrobaei, L. Perret, and S. F. Shahandashti, "SPDH-Sign: Towards Efficient, Post-quantum Group-Based Signatures," in Post-Quantum Cryptography: 14th International Workshop, PQCrypto 2023, College Park, MD, USA, 2023, pp. 113–138. DOI: https://doi.org/10.1007/978-3-031-40003-2_5
T. Elgamal, "A public key cryptosystem and a signature scheme based on discrete logarithms," IEEE Transactions on Information Theory, vol. 31, no. 4, pp. 469–472, Jul. 1985. DOI: https://doi.org/10.1109/TIT.1985.1057074
I. Blake, G. Seroussi, and N. Smart, Elliptic Curves in Cryptography. Cambridge, UK: Cambridge University Press, 1999. DOI: https://doi.org/10.1017/CBO9781107360211
G. Filippone, "On the Discrete Logarithm Problem for elliptic curves over local fields." arXiv, Apr. 27, 2023.
A. Abdullah, A. Mahalanobis, and V. M. Mallick, "A new method for solving the elliptic curve discrete logarithm problem," Journal of Groups, Complexity, Cryptology, vol. 12, no. 2, Feb. 2021, Art. no. 2. DOI: https://doi.org/10.46298/jgcc.2020.12.2.6649
K. T. Nguyen, H. N. Hoang, and D. H. Ngoc, "A New Security Enhancing Solution when Building Digital Signature Schemes," Engineering, Technology & Applied Science Research, vol. 15, no. 3, pp. 23613–23621, Jun. 2025. DOI: https://doi.org/10.48084/etasr.10370
Downloads
How to Cite
License
Copyright (c) 2025 Tuan Nguyen Kim, Luu Hong Dung, Hoang Duc Tho, Ha Nguyen Hoang
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
