Abstract
We revisit the Commutative Isogeny Hidden Number Problem (CI-HNP), an analogue of the classical Hidden Number Problem in the CSURF setting, where an adversary is tasked with recovering a shared elliptic curve \( E_{AB} \) over a prime field GF(p) from partial information about the most significant bits (MSBs) of the Montgomery coefficient. In particular, we focus on improving the recovery bound for the CSURF protocol.
Meers and Nowakowski (Asiacrypt 2023) demonstrated that an adversary can recover \( E_{AB} \) in polynomial time when the total unknown portion is bounded by 73.2% of size of prime p. We present an enhanced attack that improves this bound to 77.9%. Our improvement is achieved by refining the application of Coppersmith method. Our result highlights the need for a thorough reassessment of bit security in isogeny-based cryptographic protocols like CSURF, particularly in the context of partial information attacks.
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
Boneh, D., Halevi, S., Howgrave-Graham, N.: The modular inversion hidden number problem. In: Boyd, C. (ed.) Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9-13, 2001, Proceedings. LNCS, vol. 2248, pp. 36–51. Springer (2001)
Boneh, D., Venkatesan, R.: Hardness of computing the most significant bits of secret keys in diffie-hellman and related schemes. In: Advances in Cryptology - CRYPTO ’96, vol. 1109. LNCS, pp. 129–142. Springer (1997)
Castryck, W., Decru, T.: CSIDH on the surface. In: Ding, J., Tillich, J.-P. (ed.) Post-Quantum Cryptography - 11th International Conference, PQCrypto 2020, Paris, France, April 15-17, 2020, Proceedings. LNCS, vol. 12100, pp. 111–129. Springer (2020)
Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: Csidh: an efficient post-quantum commutative group action. In: Advances in Cryptology - ASIACRYPT 2018. Springer, Cham (2018)
Childs, A.M., Jao, D., Soukharev, V.: Constructing elliptic curve isogenies in quantum subexponential time. J. Math. Cryptol. 8(1), 1–29 (2014)
Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644–654 (1976)
Ernst, M., Jochemsz, E., May, A., de Weger, B.: Partial key exposure attacks on RSA up to full size exponents. In: Cramer, R. (ed.) Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings. LNCS, vol. 3494, pp. 371–386. Springer (2005)
De Feo, L., Jao, D., Plût, J.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. J. Math. Cryptol. 8(3), 209–247 (2014)
Galbraith, S.D., Petit, C., Shani, B., Ti, Y.B.: On the security of supersingular isogeny cryptosystems. In: Advances in Cryptology - ASIACRYPT 2016, pp. 63–91 (2016)
Herrmann, M., May, A.: Attacking power generators using unravelled linearization: When do we output too much? In: Matsui, M. (ed.) Advances in Cryptology - ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings, vol. 5912. LNCS, pp. 487–504. Springer (2009)
Howgrave-Graham, N.: Finding small roots of univariate modular equations revisited. In: Darnell, M. (ed.) Cryptography and Coding, 6th IMA International Conference, Cirencester, UK, December 17-19, 1997, Proceedings. LNCS, vol. 1355, pp. 131–142. Springer (1997)
Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.-Y. (ed.) Post-Quantum Cryptography - 4th International Workshop, PQCrypto 2011, Taipei, Taiwan, November 29 - December 2, 2011. Proceedings. LNCS, vol. 7071, pp. 19–34. Springer (2011)
Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48(177), 203–209 (1987)
Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982)
Meers, J., Nowakowski, J.: Solving the hidden number problem for CSIDH and CSURF via automated coppersmith. In: Guo, J., Steinfeld, R. (eds.) Advances in Cryptology - ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part IV. LNCS, vol. 14441, pp. 39–71. Springer (2023)
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)
Ryan, K., Heninger, N.: Fast practical lattice reduction through iterated compression. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part III. LNCS, vol. 14083, pp. 3–36. Springer (2023)
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pp. 124–134. IEEE Computer Society (1994)
Acknowledgements
The author would like to express sincere gratitude to Julian Nowakowski and Alexander May of Ruhr University Bochum for their valuable discussions and insights, which significantly contributed to shaping many of the ideas presented in this work during the author’s visit. The author also wishes to acknowledge the anonymous Indocrypt reviewers for their detailed comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2025 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Sarkar, S. (2025). Enhanced Bound for the Commutative Isogeny Hidden Number Problem in CSURF. In: Mukhopadhyay, S., Stănică, P. (eds) Progress in Cryptology – INDOCRYPT 2024. INDOCRYPT 2024. Lecture Notes in Computer Science, vol 15496. Springer, Cham. https://doi.org/10.1007/978-3-031-80311-6_10
Download citation
DOI: https://doi.org/10.1007/978-3-031-80311-6_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-80310-9
Online ISBN: 978-3-031-80311-6
eBook Packages: Computer ScienceComputer Science (R0)