Isogeny-Based Certificateless Identification Scheme

Document Type : Research Paper


1 Department of mathematical science, University of Kashan, Kashan, Iran

2 Department of mathematical sciences, University of Kashan, Kashan, Iran.



In this paper, we propose a new certificateless identification scheme based on isogenies between elliptic curves that is a candidate for quantum-resistant problems.  The proposed scheme has the batch verification property which allows verifying more than one identity by executing only a single challenge-response protocol.


[1] S. S Al-Riyami and K. G Paterson. Certi cateless public key cryptography. Asiacrypt, 2894, (2003), 452-
[2] M. Bellare, Ch. Namprempre, and G. Neven, Security proofs for identity-based identi cation and signature
schemes. Journal of Cryptology, 22(1),(2009),1-61.
[3] J.F. Biasse, D. Jao, and A. Sankar, A quantum algorithm for computing isogenies between supersingular
elliptic curves. International Conference in Cryptology in India, (2014), 428-442.
[4] A. Childs, D. Jao, and V. Soukharev, Constructing elliptic curve isogenies in quantum subexponential
time. Journal of Mathematical Cryptology, 8(1),(2014),1-29.
[5] J.J. Chin, R.C-W Phan, R. Behnia, and S.H. Heng, An ecient and provably secure certi cateless identi-
cation scheme. Security and Cryptography (SECRYPT), 2013 International Conference on, (2013), 1-8.
[6] J.J. Chin, S.Y. Tan, S.H. Heng, R.C-W Phan, and R. Behnia, A provable secure pairing-free certi cateless
identi cation scheme. International Journal of Computer Mathematics, 92(8),(2015),1520-1535.
[7] Ch. Delfs and S.D. Galbraith, Computing isogenies between supersingular elliptic curves over Fp Designs,
Codes and Cryptography, 78(2),(2016), 425-440.
[8] M. Deuring. Die typen der multiplikatorenringe elliptischer funktionenkrper. Abhandlungen aus dem math-
ematischen Seminar der Universitt Hamburg, 14, (1941), 197-272.
[9] D. Feo, Luca, Jao, David and Plt, Jrme Towards quantum-resistant cryptosystems from supersingular
elliptic curve isogenies J. Math. Cryptology, 8(3), (2011), 209-247.
[10] S. Galbraith and A. Stolbunov, Improved algorithm for the isogeny problem for ordinary elliptic curves.
Applicable Algebra in Engineering, Communication and Computing, 24(2), (2013), 107-131.
[11] D.R. Kohel, Endomorphism rings of elliptic curves over nite elds. Thesis, 1996.
[12] K. Kurosawa and S.H. Heng, From digital signature to id-based identi cation/signature. International
Workshop on Public Key Cryptography, (2004), 248-261.
[13] R.L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryp-
tosystems. Communications of the ACM, 26(1), (1983), 96-99.
[14] A. Shamir, Identity-based cryptosystems and signature schemes. Crypto, 84, (1984), 47-53.
[15] J.H. Silverman, The arithmetic of elliptic curves, volume 106. Springer Science & Business Media, 2009.
[16] W.A. Stein, and D. Joyner, SAGE: System for Algebra and Geometry Experimentation, Comm. Computer
Algebra 39 (2005), 61{64.
[17] W.A. Stein, SAGE: Software for Algebra and Geometry Experimentation,
[18] J. Tate, Endomorphisms of abelian varieties over nite elds. Inventiones mathematicae, 2(2), (1966),
[19] J. Vlu, Isognies entre courbes elliptiques. Comptes-Rendus de l'Acadmie des Sciences, 273, (1971),238-241.
[20] L.C. Washington, Elliptic curves: number theory and cryptography. CRC press, 2008.
[21] Ch. Wittmann, Group structure of elliptic curves over nite elds. Journal of Number Theory, 88(2),
(2001), 335-344.