A Post-Quantum Zero-Knowledge Identification Scheme

Document Type : Original Scientific Paper

Authors

Department of Pure Mathematics,‎ Faculty of Mathematical Sciences‎, ‎ ‎University of Kashan,‎Kashan‎, ‎I‎. ‎R‎. ‎Iran

10.22052/mir.2025.255716.1483

Abstract

‎In this paper‎, ‎we introduce a zero-knowledge identification protocol designed for authentication within the supersingular isogeny Diffie-Hellman (SIDH) key exchange framework‎. ‎The protocol allows both parties to participate as either the prover or the verifier‎, ‎with the goal of proving that they know their private information‎. ‎We show the completeness and soundness of the protocol by showing that the privacy of both the prover and the verifier depends on the difficulty of solving the extended isogeny logarithm problem‎. ‎A new authentication protocol for SIDH is presented in this paper‎, ‎that is secure against attacks from eavesdroppers‎.

Keywords

Main Subjects


[1] S. Goldwasser, S. Micali and C. Rackoff, The knowledge complexity of interactive proof-systems, SIAM J. Comput. 18 (1989) 186 - 208.
[2] M. Rezaei Kashi and M. Bahramian, Proof of knowing the prime factors of a number using zero-knowledge proof, Iran. J. Math. Sci. Inform. 15 (2020) 33 - 46 (in Persian).
[3] P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proc. 35th Annu. Symp. Found. Comput. Sci., IEEE (1994) 124 -134.
[4] D. X. Charles, K. E. Lauter and E. Z. Goren, Cryptographic hash functions from expander graphs, J. Cryptology 22 (2009) 93 - 113, https://doi.org/10.1007/s00145-007-9002-x.
[5] D. Jao and L. De Feo, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, In PQCrypto, Lecture Notes in Computer Science 7071 (2011) 19-34, https://eprint.iacr.org/2011/506/20110918:024142.
[6] X. Sun, H. Tian and Y. Wang, Toward quantum-resistant strong designated verifier signature from isogenies, in Proc. 4th Int. Conf. Intell. Netw. Collaborative Syst., Bucharest, Romania (2012) 292 - 296.
[7] L. De Feo, D. Jao and J. Plût, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, J. Math. Cryptol. 8 (2014) 209 - 247.
[8] M. El Baraka and S. Ezzouak, Proposal of a new isogeny-based cryptographic protocol formal analysis and comparison, Math. Interdisc. Res. 10 (2025) 111 - 132, https://doi.org/10.22052/MIR.2024.255405.1476.
[9] D. Jao and V. Soukharev, Isogeny-based quantum-resistant undeniable signatures, In Post-Quantum Cryptography, Michele Mosca (Ed.), Springer International Publishing, Cham (2014) 160 - 179.
[10] S. D. Galbraith, C. Petit and J. Silva, Identification protocols and signature schemes based on supersingular isogeny problems, Proceedings of Asiacrypt (1), Lecture Notes in Computer Science 10624, (2017) 3 - 33.
[11] Y. Yoo, R. Azarderakhsh, A. Jalali, D. Jao and V. Soukharev, A post-quantum digital signature scheme based on supersingular isogenies, Cryptology ePrint Archive, Report 2017/186, (2017), http://eprint.iacr.org/2017/186.
[12] M. S. Srinath and V. Chandrasekaran, Isogeny-based quantum-resistant undeniable blind signature scheme, IACR Cryptol. ePrint Arch. 20 (2018) 9-18, https://doi.org/10.6633/IJNS.201801.20(1).02.
[13] C. Peng, J. Chen, L. Zhou, K. K. R. Choo and D. He, CsiIBS: a post-quantum identity-based signature scheme based on isogenies, J. Inf. Secur. Appl. 54 (2020) #102504.
[14] K. Eslami and M. Bahramian, An isogeny-based quantumresistant secret sharing scheme, Filomat 36 (2022) 3249 - 3258, https://doi.org/10.2298/FIL2210249E.
[15] K. Dey, S. K. Debnath, P. Stanica and V. Srivastava, A post-quantum signcryption scheme using isogeny-based cryptography, J. Inf. Secur. Appl. 69 (2022) #103280, https://doi.org/10.1016/j.jisa.2022.103280.
[16] S. D. Galbraith, Mathematics of Public Key Cryptography, Cambridge University Press, Cambridge, 2012.
[17] L. C. Washington, Elliptic Curves: Number Theory and Cryptography, CRC Press, Boca Raton, 2008.
[18] J. H. Silverman, J. Pipher and J. Hoffstein, An Introduction to Mathematical Cryptography, Springer, New York, 2008.
[19] J. Silva Velón, Zero-Knowledge Proofs and Isogeny-Based Cryptosystems, Doctoral dissertation, Universitat Pompeu Fabra, 2021.
[20] L. Dewaghe, Remarks on the Schoof-Elkies-Atkin algorithm, Math. Comp. 67 (1998) 1247 - 1252.
[21] A. K. Pizer, Ramanujan graphs and Hecke operators, Bull. Amer. Math. Soc. (N.S.) 23 (1990) 127 - 137.