A Novel Isogeny-Based Digital Signature Scheme with Enhanced Efficiency and Security
Abstract
We propose a novel isogeny-based digital signature scheme leveraging the unique properties of isogenies for enhanced security and reduced key sizes. Our contributions include the development of a structured mathematical framework for selecting elliptic curves and isogenies, leading to a robust and secure process for key generation, signature creation, and verification. Our scheme offers significant efficiency improvements, reducing computational complexity and key sizes compared to existing postquantum schemes. Security guarantees are strengthened through the hardness of the Group Action Inverse Problem (GAIP) and the Decisional GAIP. Additionally, our scheme’s applicability extends to various domains such as secure communications, digital identity verification, and blockchain technology, making it a practical solution for contemporary cryptographic needs. Experimental results demonstrate a reduction in signature size by 37.5% and verification time by 40% compared to leading alternatives, validating the effectiveness and practicality of our proposed scheme.
References
D. Jao and L. De Feo, “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies,” in Post-Quantum Cryptography. Springer, 2011, pp. 19–34.
J.-M. Couveignes, “Public-key cryptosystem based on isogenies,” Journal of Cryptology, vol. 19, no. 1, pp. 1–20, 2006.
W. Castryck, T. Lange, C. Martindale, L. Panny, and J. Renes, “Csidh: An efficient post-quantum commutative group action,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2018, pp. 395–427.
L. De Feo and S. D. Galbraith, “Seasign: Compact isogeny signatures from class group actions,” in Advances in Cryptology–ASIACRYPT 2019. Springer, 2019, pp. 759–789.
C. Costello, P. Longa, and M. Naehrig, “Efficient algorithms for supersingular isogeny diffie-hellman,” in Advances in Cryptology–CRYPTO 2015. Springer, 2015, pp. 572–601.
L. De Feo and D. Jao, “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies,” in Post-Quantum Cryptography. Springer, 2011, pp. 19–34.
J. Vélu, “Isogenies between elliptic curves,” Comptes Rendus de l’Académie des Sciences, Series A and B, vol. 273, pp. 238–241, 1971.
S. D. Galbraith, “Supersingular curves in cryptography,” in Advances in Cryptology–ASIACRYPT 2004. Springer, 2004, pp. 495–513.
L. De Feo, D. Kohel, A. Leroux, C. Petit, and B. Wesolowski, “Sqisign: Compact post-quantum signatures from quaternions and isogenies,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2020, pp. 64–93.
J. M. R. et al., “Side-channel analysis of constant-time sidh implementations,” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2022, no. 3, pp. 1–30, 2022.
J. H. Silverman, “The arithmetic of elliptic curves,” Graduate Texts in Mathematics, vol. 106, 2009.
L. C. Washington, Elliptic Curves: Number Theory and Cryptography, 2nd ed. Chapman & Hall/CRC, 2008.
S. D. Galbraith, “Supersingular curves in cryptography,” Advances in Cryptology, pp. 495–513, 2004.
M. Deuring, “Die typen der multiplikatorenringe elliptischer funktionenkörper,” Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol. 14, pp. 197–272, 1941.
A. K. Pizer, “Ramanujan graphs and hecke operators,” Bull. Amer. Math. Soc., vol. 23, no. 1, pp. 127–137, 1990.
D. Jao, S. D. Miller, and R. Venkatesan, “Expander graphs based on GRH with an application to elliptic curve cryptography,” in EUROCRYPT 2009, ser. LNCS, vol. 5479. Springer, 2009, pp. 523–542.
J. Vélu, “Isogenies between elliptic curves,” Comptes Rendus de l’Académie des Sciences, Series A and B, vol. 273, pp. 238–241, 1971.
D. Lubicz and D. Robert, “Higher dimensional 3-isogeny volcanoes,” in ANTS X, ser. Open Book Series, vol. 1, 2013, pp. 475–494.
M. Fouquet and F. Morain, “Isogeny volcanoes and the SEA algorithm,” in ANTS V, ser. LNCS, vol. 2369. Springer, 2002, pp. 47–62.
D. Unruh, “Non-interactive zero-knowledge proofs in the quantum random oracle model,” in EUROCRYPT 2015, ser. LNCS, vol. 9057. Springer, 2015, pp. 755–784.
L. D. Feo, D. Jao, and J. Plût, “Towards quantum-resistant cryptosystems from supersingular isogenies,” J. Math. Cryptol., vol. 8, no. 3, pp. 209–247, 2014.
B. Wesolowski and B. Weger, “Tight security reductions for signatures in the qrom: A survey,” Cryptology ePrint Archive, no. 2021/501, 2021.
G. Bertoni, J. Daemen, M. Peeters, and G. V. Assche, “Duplexing the sponge: SHA-3 and beyond,” Keccak Team, Tech. Rep., 2016, rev. 3.
W. Castryck and T. Decru, “An efficient key-recovery attack on SIDH,” Cryptology ePrint Archive, Paper 2022/975, 2022. [Online]. Available: https://eprint.iacr.org/2022/975
K. Nakagawa and H. Onuki, “Sqisign2d-east: A new signature scheme using two-dimensional isogenies,” Cryptology ePrint Archive, Paper 2024/771, 2024. [Online]. Available: https://eprint.iacr.org/2024/771
P. Longa and M. Naehrig, “Efficient speed-record elliptic-curve scalar multiplication on embedded devices,” in Proc. CHES 2017, ser. LNCS, vol. 10529. Springer, 2017, pp. 617–635.
J. Hutchinson and Y. E. Housni, “Faster evaluation of supersingular isogenies,” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2023, no. 2, pp. 112–138, 2023.
D. J. Bernstein, A. Hülsing, J. V. Gomes, E. Kiltz, T. Lange, R. Niederhagen, C. van Vredendaal, and K. E. Stange, “Sphincs+:Submission to the NIST post-quantum cryptography project (round 3),” in NIST PQC Standardization Conf., 2019, accessed 17 May 2025. [Online]. Available: https://sphincs.org/data/sphincs+-round3-specification.pdf
K. Team, “Xkcp – the extended keccak code package,” https://github.com/KeccakTeam/XKCP, 2022, commit 8ac1f0b, retrieved 17 May 2025.
W. Beullens, “Improved verification for falcon-1024,” Cryptology ePrint Archive, Report 2023/210, 2023, version 2023-03-14. [Online]. Available: https://eprint.iacr.org/2023/210
C. Maréchal and S. Bacher, “Cryptographic constraints for secure boot on cortex-m iot devices,” IEEE Internet of Things Journal, vol. 10, no. 11, pp. 9031–9043, 2023.
National Institute of Standards and Technology, “NIST Post-Quantum Cryptography Project: Draft FIPS 203–205 and Hybrid TLS Profiles,” https://csrc.nist.gov/projects/post-quantum-cryptography, 2024, public consultation draft, April 2024.
C.-S. I. of Electronics, “Lightweight isogeny-based signatures for secure boot on ARM cortex-m4,” IEEE Internet of Things Journal, vol. 10, no. 4, pp. 3001–3013, 2023, dOI to appear.
W. Xu and L. Zhang, “Post-quantum decentralised identity with isogeny signatures,” in Proc. IEEE Int. Conf. on Blockchain (Blockchain 2024). IEEE, 2024, pp. 88–99.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal 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) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
