Abstract
In AsiaCrypt 2017, Galbraith-Petit-Silva proposed a digital signature scheme based on the problem of computing the endomorphism ring of a supersingular elliptic curve. This problem is more standard than that of the De Feo-Jao-Plût SIDH scheme, since it lacks the auxiliary points which lead to the adaptive active attack of Galbraith-Petit-Shani-Ti. The GPS signature scheme applies the Fiat-Shamir or Unruh transformation to the raw identification protocol obtained from the endomorphism ring problem, and makes use of the Kohel-Lauter-Petit-Tignol quaternion isogeny path algorithm to find a new ideal. However, the GPS signature scheme is not very practical. In this paper, we take a first step towards quantifying the efficiency of the GPS signature scheme. We propose some improvements in the underlying algorithms for the GPS scheme, along with a new method which trades off key size for signature size to decrease the signature size from around 11 kB to 1 kB at the 128-bit security level by using multi-bit challenges. We also provide a concrete implementation of the GPS signature scheme using Sage and CoCalc.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adj, G., Cervantes-Vázquez, D., Chi-Domínguez, J.J., Menezes, A., Rodríguez-Henríquez, F.: On the cost of computing isogenies between supersingular elliptic curves. In: Cid, C., Jacobson Jr., M. (eds.) SAC 2018. LNCS, vol. 11349. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-10970-7_15
Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, New York, NY, USA, pp. 390–399. ACM (2006)
Charles, D.X., Lauter, K.E., Goren, E.Z.: Cryptographic hash functions from expander graphs. J. Cryptology 22(1), 93–113 (2009)
Costello, C., Longa, P., Naehrig, M., Renes, J., Virdia, F.: Improved classical cryptanalysis of the computational supersingular isogeny problem. Cryptology ePrint Archive, Report 2019/298 (2019). https://eprint.iacr.org/2019/298
Couveignes, J.-M.: Hard homogeneous spaces. Cryptology ePrint Archive, Report 2006/291 (2006). https://eprint.iacr.org/2006/291
De Feo, L., Galbraith, S.D.: SeaSign: compact isogeny signatures from class group actions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 759–789. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_26
Eisenträger, K., Hallgren, S., Lauter, K., Morrison, T., Petit, C.: Supersingular isogeny graphs and endomorphism rings: reductions and solutions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 329–368. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_11
De Feo, L., Jao, D., Plût, J.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. J. Math. Cryptology 8(3), 209–247 (2014)
Galbraith, S.D., Petit, C., Shani, B., Ti, Y.B.: On the security of supersingular isogeny cryptosystems. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 63–91. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_3
Galbraith, S.D., Petit, C., Silva, J.: Identification protocols and signature schemes based on supersingular isogeny problems. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 3–33. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_1
Galbraith, S.D., Vercauteren, F.: Computational problems in supersingular elliptic curve isogenies. Quantum Inf. Process. 17(10), 265 (2018)
Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 19–34. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_2
Kohel, D.: Endomorphism rings of elliptic curves over finite fields. Ph.D. thesis, University of California, Berkeley, (1996)
Kohel, D., Lauter, K.E., Petit, C., Tignol, J.-P.: On the quaternion \(\ell \)-isogeny path problem. LMS J. Comput. Math. 17(A), 418–432 (2014)
Lyubashevsky, V.: Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 598–616. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_35
Petit, C., Smith, S.: An improvement to the quaternion analogue of the \(l\)-isogeny path problem. In: Proceedings of MATHCRYPT 2018 (2018)
Stolbunov, A.: Cryptographic schemes based on isogenies. Ph.D. thesis, Norwegian University of Science and Technology (2012)
The Sage Developers. SageMath, the Sage Mathematics Software System (Version 8.5) (2019). https://www.sagemath.org
Vélu, J.: Isogénies entre courbes elliptiques. C. R. Acad. Sci. Paris Sér. A-B 273, A238–A241 (1971)
Yoo, Y., Azarderakhsh, R., Jalali, A., Jao, D., Soukharev, V.: A post-quantum digital signature scheme based on supersingular isogenies. In: Kiayias, A. (ed.) FC 2017. LNCS, vol. 10322, pp. 163–181. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70972-7_9
Acknowledgments
The authors would like to thank the anonymous reviewers for their detailed reviews and helpful comments. This work is supported by the National Natural Science Foundation of China (No. 61872442, No. 61502487) and the National Cryptography Development Fund (No. MMJJ20180216), as well as NSERC, CryptoWorks21, Public Works and Government Services Canada, Canada First Research Excellence Fund, and the Royal Bank of Canada. Furthermore, Xiu Xu acknowledges the scholarship provided by the China Scholarship Council.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Xu, X. et al. (2019). Improved Digital Signatures Based on Elliptic Curve Endomorphism Rings. In: Heng, SH., Lopez, J. (eds) Information Security Practice and Experience. ISPEC 2019. Lecture Notes in Computer Science(), vol 11879. Springer, Cham. https://doi.org/10.1007/978-3-030-34339-2_16
Download citation
DOI: https://doi.org/10.1007/978-3-030-34339-2_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-34338-5
Online ISBN: 978-3-030-34339-2
eBook Packages: Computer ScienceComputer Science (R0)