{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T22:27:51Z","timestamp":1766269671357,"version":"3.37.3"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,2,27]],"date-time":"2024-02-27T00:00:00Z","timestamp":1708992000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,2,27]],"date-time":"2024-02-27T00:00:00Z","timestamp":1708992000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2024,4]]},"DOI":"10.1007\/s00145-024-09490-w","type":"journal-article","created":{"date-parts":[[2024,2,27]],"date-time":"2024-02-27T20:02:20Z","timestamp":1709064140000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Hashing to Elliptic Curves Through Cipolla\u2013Lehmer\u2013M\u00fcller\u2019s Square Root Algorithm"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4796-8989","authenticated-orcid":false,"given":"Dmitrii","family":"Koshelev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,2,27]]},"reference":[{"unstructured":"Stark Curve. https:\/\/docs.starkware.co\/starkex\/crypto\/stark-curve.html","key":"9490_CR1"},{"unstructured":"Starkjub (2023). https:\/\/github.com\/hashcloak\/starkjub","key":"9490_CR2"},{"key":"9490_CR3","series-title":"Developments in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-54109-9","volume-title":"Quadratic Diophantine Equations","author":"T Andreescu","year":"2015","unstructured":"T. Andreescu, D. Andrica, Quadratic Diophantine Equations. Developments in Mathematics, vol.\u00a040 (Springer, New York, 2015)"},{"issue":"11","key":"9490_CR4","doi-asserted-by":"publisher","first-page":"3333","DOI":"10.1007\/s10623-022-01135-y","volume":"91","author":"DF Aranha","year":"2023","unstructured":"D.F. Aranha, Y. El Housni, A. Guillevic, A survey of elliptic curves for proof systems. Des. Codes Cryptogr. 91(11), 3333\u20133378 (2023)","journal-title":"Des. Codes Cryptogr."},{"doi-asserted-by":"crossref","unstructured":"D.F. Aranha, B. Salling Hvass, B. Spitters, M. Tibouchi, Faster constant-time evaluation of the Kronecker symbol with application to elliptic curve hashing, in CCS 2023: ACM SIGSAC Conference on Computer and Communications Security (Association for Computing Machinery, New York, 2023), pp. 3228\u20133238","key":"9490_CR5","DOI":"10.1145\/3576915.3616597"},{"unstructured":"P. Bottinelli, Breaking Pedersen hashes in practice (2023). https:\/\/research.nccgroup.com\/2023\/03\/22\/breaking-pedersen-hashes-in-practice","key":"9490_CR6"},{"doi-asserted-by":"crossref","unstructured":"E. Brier, J.S. Coron, T. Icart, D. Madore, H. Randriam, M. Tibouchi, Efficient indifferentiable hashing into ordinary elliptic curves, in T. Rabin, editors, Advances in Cryptology\u2014CRYPTO 2010. Lecture Notes in Computer Science, vol.\u00a06223 (Springer, Berlin, 2010), pp. 237\u2013254","key":"9490_CR7","DOI":"10.1007\/978-3-642-14623-7_13"},{"doi-asserted-by":"crossref","unstructured":"G. Cardona, $$\\mathbb{Q}$$-curves and abelian varieties of $${\\rm GL}_2$$-type from dihedral genus $$2$$ curves, in J.E. Cremona, J.C. Lario, J. Quer, K.A. Ribet, editors, Modular Curves and Abelian Varieties. Progress in Mathematics, vol.\u00a0224 (Birkh\u00e4user, Basel, 2004), pp. 45\u201352","key":"9490_CR8","DOI":"10.1007\/978-3-0348-7919-4_3"},{"issue":"6","key":"9490_CR9","doi-asserted-by":"publisher","first-page":"2831","DOI":"10.1090\/S0002-9947-07-04111-6","volume":"359","author":"G Cardona","year":"2007","unstructured":"G. Cardona, J. Quer, Curves of genus $$2$$ with group of automorphisms isomorphic to $${{\\rm D}}_8$$ or $${{\\rm D}}_{12}$$. Trans. Am. Math. Soc. 359(6), 2831\u20132849 (2007)","journal-title":"Trans. Am. Math. Soc."},{"doi-asserted-by":"crossref","unstructured":"L. Chen, D. Moody, A. Regenscheid, A. Robinson, K. Randall, Recommendations for discrete logarithm-based cryptography: elliptic curve domain parameters (NIST Special Publication 800-186) (2023). https:\/\/csrc.nist.gov\/publications\/detail\/sp\/800-186\/final","key":"9490_CR10","DOI":"10.6028\/NIST.SP.800-186"},{"doi-asserted-by":"crossref","unstructured":"J. Ch\u00e1vez-Saab, F. Rodr\u00edguez-Henr\u00edquez, M. Tibouchi, SWIFTEC: Shallue-van de Woestijne indifferentiable function to elliptic curves, in S. Agrawal, D. Lin, editors, Advances in Cryptology\u2014ASIACRYPT 2022. Lecture Notes in Computer Science, vol. 13791 (Springer, Cham, 2022), pp. 63\u201392","key":"9490_CR11","DOI":"10.1007\/978-3-031-22963-3_3"},{"issue":"3","key":"9490_CR12","first-page":"153","volume":"5","author":"F Ch\u00e2telet","year":"1959","unstructured":"F. Ch\u00e2telet, Points rationnels sur certaines courbes et surfaces cubiques. L\u2019Enseign. Math. 5(3), 153\u2013170 (1959)","journal-title":"L\u2019Enseign. Math."},{"key":"9490_CR13","first-page":"154","volume":"9","author":"M Cipolla","year":"1903","unstructured":"M. Cipolla, Un metodo per la risolutione della congruenza di secondo grado. Rend. dell\u2019Accad. Sci. Fis. Mat. 9, 154\u2013163 (1903)","journal-title":"Rend. dell\u2019Accad. Sci. Fis. Mat."},{"issue":"243","key":"9490_CR14","doi-asserted-by":"publisher","first-page":"1417","DOI":"10.1090\/S0025-5718-02-01480-1","volume":"72","author":"J Cremona","year":"2003","unstructured":"J. Cremona, D. Rusin, Efficient solution of rational conics. Math. Comput. 72(243), 1417\u20131441 (2003)","journal-title":"Math. Comput."},{"key":"9490_CR15","series-title":"Cryptography and Network Security Series","volume-title":"Guide to Pairing-Based Cryptography","year":"2017","unstructured":"N. El Mrabet, M. Joye, (eds.) Guide to Pairing-Based Cryptography. Cryptography and Network Security Series (Chapman and Hall\/CRC, New York, 2017)"},{"issue":"281","key":"9490_CR16","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1090\/S0025-5718-2012-02606-8","volume":"82","author":"RR Farashahi","year":"2013","unstructured":"R.R. Farashahi, P.A. Fouque, I.E. Shparlinski, M. Tibouchi, J.F. Voloch, Indifferentiable deterministic hashing to elliptic and hyperelliptic curves. Math. Comput. 82(281), 491\u2013512 (2013)","journal-title":"Math. Comput."},{"doi-asserted-by":"crossref","unstructured":"A. Faz-Hernandez, S. Scott, N. Sullivan, R.S. Wahby, C.A. Wood, Hashing to elliptic curves (RFC 9380) (2023). https:\/\/datatracker.ietf.org\/doc\/draft-irtf-cfrg-hash-to-curve","key":"9490_CR17","DOI":"10.17487\/RFC9380"},{"key":"9490_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139012843","volume-title":"Mathematics of Public Key Cryptography","author":"SD Galbraith","year":"2012","unstructured":"S.D. Galbraith, Mathematics of Public Key Cryptography. Cambridge University Press, New York (2012)"},{"key":"9490_CR19","series-title":"Graduate Texts in Mathematics","volume-title":"Algebraic Geometry","author":"R Hartshorne","year":"1997","unstructured":"R. Hartshorne, Algebraic Geometry. Graduate Texts in Mathematics, 8 edn., vol.\u00a052 (Springer, New York, 1997)","edition":"8"},{"unstructured":"D. Hopwood, The Pasta curves for Halo $$2$$ and beyond (2020). https:\/\/electriccoin.co\/blog\/the-pasta-curves-for-halo-2-and-beyond","key":"9490_CR20"},{"unstructured":"D. Hopwood, Pluto\/Eris supporting evidence (2021). https:\/\/github.com\/daira\/pluto-eris","key":"9490_CR21"},{"issue":"3","key":"9490_CR22","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1515\/form.2000.008","volume":"12","author":"EW Howe","year":"2000","unstructured":"E.W. Howe, F. Lepr\u00e9vost, B. Poonen, Large torsion subgroups of split Jacobians of curves of genus two or three. Forum Math. 12(3), 315\u2013364 (2000)","journal-title":"Forum Math."},{"doi-asserted-by":"crossref","unstructured":"T. Icart, How to hash into elliptic curves, in S. Halevi, editors, Advances in Cryptology\u2014CRYPTO 2009. Lecture Notes in Computer Science, vol.\u00a05677 (Springer, Berlin, 2009), pp. 303\u2013316","key":"9490_CR23","DOI":"10.1007\/978-3-642-03356-8_18"},{"issue":"3","key":"9490_CR24","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1017\/S1474748002000117","volume":"1","author":"J Koll\u00e1r","year":"2002","unstructured":"J. Koll\u00e1r, Unirationality of cubic hypersurfaces. J. Inst. Math. Jussieu 1(3), 467\u2013476 (2002)","journal-title":"J. Inst. Math. Jussieu"},{"issue":"4","key":"9490_CR25","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1353\/ajm.2017.0024","volume":"139","author":"J Koll\u00e1r","year":"2017","unstructured":"J. Koll\u00e1r, M. Mella, Quadratic families of elliptic curves and unirationality of degree $$1$$ conic bundles. Am. J. Math. 139(4), 915\u2013936 (2017)","journal-title":"Am. J. Math."},{"key":"9490_CR26","doi-asserted-by":"publisher","DOI":"10.1016\/j.ffa.2020.101774","volume":"69","author":"D Koshelev","year":"2021","unstructured":"D. Koshelev, New point compression method for elliptic $${\\mathbb{F} }_{\\!q^2}$$-curves of $$j$$-invariant $$0$$. Finite Fields Appl. 69, 101774 (2021)","journal-title":"Finite Fields Appl."},{"unstructured":"D. Koshelev, Some remarks on how to hash faster onto elliptic curves (2021). https:\/\/eprint.iacr.org\/2021\/1082","key":"9490_CR27"},{"issue":"3","key":"9490_CR28","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1007\/s10623-022-01012-8","volume":"90","author":"D Koshelev","year":"2022","unstructured":"D. Koshelev, Indifferentiable hashing to ordinary elliptic $${\\mathbb{F} }_{\\!q}$$-curves of $$j = 0$$ with the cost of one exponentiation in $${\\mathbb{F} }_{\\!q}$$. Des. Codes Cryptogr 90(3), 801\u2013812 (2022)","journal-title":"Des. Codes Cryptogr"},{"issue":"1","key":"9490_CR29","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1515\/jmc-2021-0051","volume":"16","author":"D Koshelev","year":"2022","unstructured":"D. Koshelev, The most efficient indifferentiable hashing to elliptic curves of $$j$$-invariant $$1728$$. J. Math. Cryptol. 16(1), 298\u2013309 (2022)","journal-title":"J. Math. Cryptol."},{"issue":"4","key":"9490_CR30","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1137\/21M1441602","volume":"6","author":"D Koshelev","year":"2022","unstructured":"D. Koshelev, Optimal encodings to elliptic curves of $$j$$-invariants $$0$$, $$1728$$. SIAM J. Appl. Algebra Geom. 6(4), 600\u2013617 (2022)","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"9490_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-023-00625-3","author":"D Koshelev","year":"2023","unstructured":"D. Koshelev, Batch point compression in the context of advanced pairing-based protocols. Appl. Algebra Eng. Commun. Comput. (2023). https:\/\/doi.org\/10.1007\/s00200-023-00625-3","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"unstructured":"D. Koshelev, Hashing to elliptic curves over highly $$2$$-adic fields $${\\mathbb{F}}_{\\!q}$$ with $${O}(\\log q)$$ operations in $${\\mathbb{F}}_{\\!q}$$ (2023). https:\/\/eprint.iacr.org\/2023\/121","key":"9490_CR32"},{"doi-asserted-by":"crossref","unstructured":"D. Koshelev, Magma code (2023). https:\/\/github.com\/dishport\/Hashing-to-elliptic-curves-through-Cipolla-Lehmer-Muller-square-root-algorithm","key":"9490_CR33","DOI":"10.1007\/s00145-024-09490-w"},{"unstructured":"R.J. Lambert, Method to calculate square roots for elliptic curve cryptography (2013). https:\/\/patents.google.com\/patent\/US9148282B2\/en, United States patent No. 9148282B2","key":"9490_CR34"},{"unstructured":"D.H. Lehmer, Computer technology applied to the theory of numbers, in W.J. LeVeque, editors, Studies in Number Theory. Studies in Mathematics, vol.\u00a06 (Mathematical Association of America, Washington, 1969), pp. 117\u2013151","key":"9490_CR35"},{"key":"9490_CR36","volume-title":"Finite Fields, Encyclopedia of Mathematics and its Applications","author":"R Lidl","year":"1997","unstructured":"R. Lidl, H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its Applications, vol.\u00a020 (Cambridge University Press, Cambridge, 1997)"},{"issue":"3","key":"9490_CR37","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1023\/B:DESI.0000015890.44831.e2","volume":"31","author":"S M\u00fcller","year":"2004","unstructured":"S. M\u00fcller, On the computation of square roots in finite fields. Des. Codes Cryptogr 31(3), 301\u2013312 (2004)","journal-title":"Des. Codes Cryptogr"},{"unstructured":"T. Pornin, Optimized discrete logarithm computation for faster square roots in finite fields (2023). https:\/\/eprint.iacr.org\/2023\/828","key":"9490_CR38"},{"doi-asserted-by":"crossref","unstructured":"V. Sedlacek, V. Suchanek, A. Dufka, M. Sys, V. Matyas, DiSSECT: distinguisher of standard and simulated elliptic curves via traits, in L. Batina, J. Daemen, editors, Progress in Cryptology\u2014AFRICACRYPT 2022. Lecture Notes in Computer Science, vol. 13503 (Springer, Cham, 2022), pp. 493\u2013517","key":"9490_CR39","DOI":"10.1007\/978-3-031-17433-9_21"},{"doi-asserted-by":"crossref","unstructured":"A. Shallue, C.E. van\u00a0de Woestijne, Construction of rational points on elliptic curves over finite fields, in F. Hess, S. Pauli, M. Pohst, editors, Algorithmic Number Theory Symposium. ANTS 2006. Lecture Notes in Computer Science, vol.\u00a04076 (Springer, Berlin, 2006), pp. 510\u2013524","key":"9490_CR40","DOI":"10.1007\/11792086_36"},{"unstructured":"D. Shanks, Five number-theoretic algorithms, in R.S.D. Thomas, H.C. Williams, editors, Proceedings of the Second Manitoba Conference on Numerical Mathematics. Congressus Numerantium, vol.\u00a07 (Utilitas Mathematica Publishing Inc., Winnipeg, 1973), pp. 51\u201370","key":"9490_CR41"},{"key":"9490_CR42","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814549","volume-title":"A Computational Introduction to Number Theory and Algebra","author":"V Shoup","year":"2008","unstructured":"V. Shoup, A Computational Introduction to Number Theory and Algebra. Cambridge University Press, Cambridge, 2 edn. (2008)","edition":"2"},{"issue":"3","key":"9490_CR43","doi-asserted-by":"publisher","first-page":"293","DOI":"10.4064\/aa117-3-7","volume":"117","author":"M Ska\u0142ba","year":"2005","unstructured":"M. Ska\u0142ba, Points on elliptic curves over finite fields. Acta Arith. 117(3), 293\u2013301 (2005)","journal-title":"Acta Arith."},{"issue":"273","key":"9490_CR44","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1090\/S0025-5718-10-02356-2","volume":"80","author":"AV Sutherland","year":"2011","unstructured":"A.V. Sutherland, Structure computation and discrete logarithms in finite abelian $$p$$-groups. Math. Comput. 80(273), 477\u2013500 (2011)","journal-title":"Math. Comput."},{"issue":"2","key":"9490_CR45","doi-asserted-by":"publisher","first-page":"331","DOI":"10.5802\/afst.935","volume":"8","author":"P Swinnerton-Dyer","year":"1999","unstructured":"P. Swinnerton-Dyer, Rational points on some pencils of conics with $$6$$ singular fibres. Ann. Fac. Sci. Toulouse Math. (S\u00e9r. 6) 8(2), 331\u2013341 (1999)","journal-title":"Ann. Fac. Sci. Toulouse Math. (S\u00e9r. 6)"},{"issue":"275","key":"9490_CR46","doi-asserted-by":"publisher","first-page":"1797","DOI":"10.1090\/S0025-5718-2011-02419-1","volume":"80","author":"TW Sze","year":"2011","unstructured":"T.W. Sze, On taking square roots without quadratic nonresidues over finite fields. Math. Comput. 80(275), 1797\u20131811 (2011)","journal-title":"Math. Comput."},{"issue":"1\u20132","key":"9490_CR47","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s10623-016-0288-2","volume":"82","author":"M Tibouchi","year":"2017","unstructured":"M. Tibouchi, T. Kim, Improved elliptic curve hashing and point representation. Des. Codes Cryptogr. 82(1\u20132), 161\u2013177 (2017)","journal-title":"Des. Codes Cryptogr."},{"unstructured":"A. Tonelli, Bemerkung \u00fcber die aufl\u00f6sung quadratischer congruenzen. Nachrichten von der K\u00f6niglichen Gesellschaft der Wissenschaften und der Georg-Augusts-Universit\u00e4t zu G\u00f6ttingen (1891), pp. 344\u2013346","key":"9490_CR48"},{"issue":"4","key":"9490_CR49","doi-asserted-by":"publisher","first-page":"154","DOI":"10.46586\/tches.v2019.i4.154-179","volume":"2019","author":"RS Wahby","year":"2019","unstructured":"R.S. Wahby, D. Boneh, Fast and simple constant-time hashing to the BLS12-381 elliptic curve. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2019(4), 154\u2013179 (2019)","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09490-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-024-09490-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09490-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,25]],"date-time":"2024-04-25T21:01:55Z","timestamp":1714078915000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-024-09490-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,27]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["9490"],"URL":"https:\/\/doi.org\/10.1007\/s00145-024-09490-w","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"type":"print","value":"0933-2790"},{"type":"electronic","value":"1432-1378"}],"subject":[],"published":{"date-parts":[[2024,2,27]]},"assertion":[{"value":"27 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 December 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 December 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 February 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"11"}}