{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:31:19Z","timestamp":1764981079399,"version":"3.46.0"},"reference-count":31,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,12,14]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    This article makes an important contribution to solving the long-standing problem of whether all elliptic curves can be equipped with a hash function (indifferentiable from a random oracle) whose running time amounts to one exponentiation in the basic finite field\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2021-0051_eq_001.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:msub>\n                            <m:mrow>\n                              <m:mi mathvariant=\"double-struck\">F<\/m:mi>\n                            <\/m:mrow>\n                            <m:mrow>\n                              <m:mi>q<\/m:mi>\n                            <\/m:mrow>\n                          <\/m:msub>\n                        <\/m:math>\n                        <jats:tex-math>{{\\mathbb{F}}}_{q}<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . More precisely, we construct a new indifferentiable hash function to any ordinary elliptic\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2021-0051_eq_002.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:msub>\n                            <m:mrow>\n                              <m:mi mathvariant=\"double-struck\">F<\/m:mi>\n                            <\/m:mrow>\n                            <m:mrow>\n                              <m:mi>q<\/m:mi>\n                            <\/m:mrow>\n                          <\/m:msub>\n                        <\/m:math>\n                        <jats:tex-math>{{\\mathbb{F}}}_{q}<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -curve\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2021-0051_eq_003.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:msub>\n                            <m:mrow>\n                              <m:mi>E<\/m:mi>\n                            <\/m:mrow>\n                            <m:mrow>\n                              <m:mi>a<\/m:mi>\n                            <\/m:mrow>\n                          <\/m:msub>\n                        <\/m:math>\n                        <jats:tex-math>{E}_{a}<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    of\n                    <jats:italic>j<\/jats:italic>\n                    -invariant 1728 with the cost of extracting one quartic root in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2021-0051_eq_004.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:msub>\n                            <m:mrow>\n                              <m:mi mathvariant=\"double-struck\">F<\/m:mi>\n                            <\/m:mrow>\n                            <m:mrow>\n                              <m:mi>q<\/m:mi>\n                            <\/m:mrow>\n                          <\/m:msub>\n                        <\/m:math>\n                        <jats:tex-math>{{\\mathbb{F}}}_{q}<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . As is known, the latter operation is equivalent to one exponentiation in finite fields with which we deal in practice. In comparison, the previous fastest random oracles to\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2021-0051_eq_005.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:msub>\n                            <m:mrow>\n                              <m:mi>E<\/m:mi>\n                            <\/m:mrow>\n                            <m:mrow>\n                              <m:mi>a<\/m:mi>\n                            <\/m:mrow>\n                          <\/m:msub>\n                        <\/m:math>\n                        <jats:tex-math>{E}_{a}<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    require to perform two exponentiations in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2021-0051_eq_006.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:msub>\n                            <m:mrow>\n                              <m:mi mathvariant=\"double-struck\">F<\/m:mi>\n                            <\/m:mrow>\n                            <m:mrow>\n                              <m:mi>q<\/m:mi>\n                            <\/m:mrow>\n                          <\/m:msub>\n                        <\/m:math>\n                        <jats:tex-math>{{\\mathbb{F}}}_{q}<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . Since it is highly unlikely that there is a hash function to an elliptic curve without any exponentiations at all (even if it is supersingular), the new result seems to be unimprovable.\n                  <\/jats:p>","DOI":"10.1515\/jmc-2021-0051","type":"journal-article","created":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T00:36:40Z","timestamp":1670978200000},"page":"298-309","source":"Crossref","is-referenced-by-count":3,"title":["The most efficient indifferentiable hashing to elliptic curves of\n                    <i>j<\/i>\n                    -invariant 1728"],"prefix":"10.1515","volume":"16","author":[{"given":"Dmitrii","family":"Koshelev","sequence":"first","affiliation":[{"name":"Computer Sciences and Networks Department, T\u00e9l\u00e9com Paris , Paris , France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2022,12,14]]},"reference":[{"key":"2025120600292410070_j_jmc-2021-0051_ref_001","doi-asserted-by":"crossref","unstructured":"El Mrabet N, Joye M. Guide to pairing-based cryptography. Cryptography and network security series. New York: Chapman and Hall\/CRC; 2017.","DOI":"10.1201\/9781315370170"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_002","doi-asserted-by":"crossref","unstructured":"Silverman JH. The arithmetic of elliptic curves. Graduate texts in mathematics. vol. 106. New York: Springer; 2009.","DOI":"10.1007\/978-0-387-09494-6"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_003","unstructured":"Pornin T. Double-odd elliptic curves. 2020. https:\/\/eprint.iacr.org\/2020\/1558."},{"key":"2025120600292410070_j_jmc-2021-0051_ref_004","unstructured":"Pornin T, Bottinelli P, Doussot G, Schorn E. Double-odd elliptic curves. 2020. https:\/\/doubleodd.group."},{"key":"2025120600292410070_j_jmc-2021-0051_ref_005","doi-asserted-by":"crossref","unstructured":"Hamburg M. Decaf: eliminating cofactors through point compression. In: Gennaro R, Robshaw M, editors Advances in cryptology \u2013 CRYPTO 2015, LNCS. 9215. Berlin, Heidelberg: Springer; 2015. p. 705\u201323.","DOI":"10.1007\/978-3-662-47989-6_34"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_006","unstructured":"Boneh D, Gorbunov S, Wahby RS, Wee H, Wood CA, Zhang Z. BLS signatures. 2022. https:\/\/datatracker.ietf.org\/doc\/draft-irtf-cfrg-bls-signature."},{"key":"2025120600292410070_j_jmc-2021-0051_ref_007","doi-asserted-by":"crossref","unstructured":"Faz-Hernandez A, Scott S, Sullivan N, Wahby RS, Wood CA. Hashing to elliptic curves. 2022. https:\/\/datatracker.ietf.org\/doc\/draft-irtf-cfrg-hash-to-curve.","DOI":"10.17487\/RFC9380"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_008","doi-asserted-by":"crossref","unstructured":"Maurer UM, Renner R, Holenstein C. Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor M, editor. Theory of Cryptography Conference 2004. LNCS. vol. 2951. Berlin, Heidelberg: Springer; 2004. p. 21\u201339.","DOI":"10.1007\/978-3-540-24638-1_2"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_009","doi-asserted-by":"crossref","unstructured":"Brier E, Coron J-S, Icart T, Madore D, Randriam H, Tibouchi M. Efficient indifferentiable hashing into ordinary elliptic curves. In: Rabin T, editor, Advances in cryptology \u2013 CRYPTO 2010, LNCS. vol. 6223. Berlin, Heidelberg: Springer; 2010. p. 237\u201354.","DOI":"10.1007\/978-3-642-14623-7_13"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_010","doi-asserted-by":"crossref","unstructured":"Koshelev D. Optimal encodings to elliptic curves of j-invariants 0, 1728. 2021. https:\/\/eprint.iacr.org\/2021\/1034.","DOI":"10.1137\/21M1441602"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_011","doi-asserted-by":"crossref","unstructured":"Koshelev D. Hashing to elliptic curves of j-invariant 1728. Cryptogr Commun. 2021;13(4):479\u201394.","DOI":"10.1007\/s12095-021-00478-y"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_012","unstructured":"Koshelev D. Some remarks on how to hash faster onto elliptic curves. 2021. https:\/\/eprint.iacr.org\/2021\/1082."},{"key":"2025120600292410070_j_jmc-2021-0051_ref_013","doi-asserted-by":"crossref","unstructured":"Sch\u00fctt M, Shioda T. Mordell-Weil lattices. A series of modern surveys in mathematics. vol. 70. Singapore: Springer; 2019.","DOI":"10.1007\/978-981-32-9301-4"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_014","doi-asserted-by":"crossref","unstructured":"Hulek K, Kloosterman R. Calculating the Mordell-Weil rank of elliptic threefolds and the cohomology of singular hypersurfaces. Annales de l\u2019Institut Fourier. 2011;61(3):1133\u201379.","DOI":"10.5802\/aif.2637"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_015","doi-asserted-by":"crossref","unstructured":"Koshelev D. Indifferentiable hashing to ordinary elliptic Fq-curves of j=0 with the cost of one exponentiation in Fq. Designs Codes Cryptogr. 2022;90(3):801\u201312.","DOI":"10.1007\/s10623-022-01012-8"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_016","doi-asserted-by":"crossref","unstructured":"Ch\u00e1vez-Saab J, Rodriguez-Henriquez F, Tibouchi M. SwiftEC: Shallue-van de Woestijne indifferentiable function to elliptic curves. Faster indifferentiable hashing to most elliptic curves. 2022. https:\/\/eprint.iacr.org\/2022\/759.","DOI":"10.1007\/978-3-031-22963-3_3"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_017","doi-asserted-by":"crossref","unstructured":"Shallue A, van de Woestijne CE. Construction of rational points on elliptic curves over finite fields. In: Hess F, Pauli S, Pohst M, editors. ANTS 2006. vol. 4076. Berlin, Heidelberg: Springer; 2006. p. 510\u201324.","DOI":"10.1007\/11792086_36"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_018","doi-asserted-by":"crossref","unstructured":"Ska\u0142ba M. Points on elliptic curves over finite fields. Acta Arithmetica 2005;117(3):293\u2013301.","DOI":"10.4064\/aa117-3-7"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_019","doi-asserted-by":"crossref","unstructured":"H\u00fcbsch T. Calabi-Yau manifolds: A bestiary for physicists. Singapore: World Scientific; 1992.","DOI":"10.1142\/1410"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_020","doi-asserted-by":"crossref","unstructured":"Yui N. The arithmetic of certain Calabi-Yau varieties over number fields. In: Gordon BB, et al. editors. The arithmetic and geometry of algebraic cycles. NATO science series. vol. 548. Dordrecht: Springer; 2000. p. 515\u201360.","DOI":"10.1007\/978-94-011-4098-0_20"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_021","doi-asserted-by":"crossref","unstructured":"Im B-H, Larsen M. Rational curves on quotients of abelian varieties by finite groups. Math Res Lett. 2015;22(4):1145\u201357.","DOI":"10.4310\/MRL.2015.v22.n4.a9"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_022","doi-asserted-by":"crossref","unstructured":"Schoen C. On fiber products of rational elliptic surfaces with section. Mathematische Zeitschrift. 1988;197(2):177\u201399.","DOI":"10.1007\/BF01215188"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_023","doi-asserted-by":"crossref","unstructured":"G\u00f6rtz U, Wedhorn T. Algebraic geometry I: Schemes. Studium Mathematik \u2013 Master. Wiesbaden: Springer; 2020.","DOI":"10.1007\/978-3-658-30733-2"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_024","doi-asserted-by":"crossref","unstructured":"Dolgachev IV. Classical algebraic geometry: A modern view. Cambridge: Cambridge University Press; 2012.","DOI":"10.1017\/CBO9781139084437"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_025","doi-asserted-by":"crossref","unstructured":"Bryan J, appendix with Pietromonaco S. The Donaldson-Thomas partition function of the banana manifold. Algebraic Geometry. 2021;8(2):133\u201370.","DOI":"10.14231\/AG-2021-002"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_026","doi-asserted-by":"crossref","unstructured":"Koshelev D. Magma code. 2021. https:\/\/github.com\/dishport\/The-most-efficient-indifferentiable-hashing-to-elliptic-curves-of-j-invariant-1728.","DOI":"10.1007\/s12095-021-00478-y"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_027","doi-asserted-by":"crossref","unstructured":"Tsfasman M, Vl\u0103du\u0163 S, Nogin D. Algebraic geometric codes: Basic notions. Mathematical surveys and monographs. vol. 139. Providence: American Mathematical Society; 2007.","DOI":"10.1090\/surv\/139"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_028","doi-asserted-by":"crossref","unstructured":"Stichtenoth H. Algebraic function fields and codes. Graduate texts in mathematics. vol. 254. Berlin, Heidelberg: Springer; 2009.","DOI":"10.1007\/978-3-540-76878-4"},{"key":"2025120600292410070_j_jmc-2021-0051_ref_029","unstructured":"Cox DA. Primes of the form x2+ny2: Fermat, class field theory, and complex multiplication. In: Pure and applied mathematics. New York: John Wiley & Sons; 2011."},{"key":"2025120600292410070_j_jmc-2021-0051_ref_030","unstructured":"Fulton W. Algebraic curves: An introduction to algebraic geometry. Boston: Addison-Wesley; 2008."},{"key":"2025120600292410070_j_jmc-2021-0051_ref_031","doi-asserted-by":"crossref","unstructured":"Aubry Y, Perret M. A Weil theorem for singular curves. In: Pellikaan R, Perret M, Vl\u0103du\u0163 SG, editors, Arithmetic, Geometry, and Coding Theory, Proceedings in Mathematics. Berlin: De Gruyter; 1996. p. 1\u20137.","DOI":"10.1515\/9783110811056.1"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2021-0051\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2021-0051\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:29:37Z","timestamp":1764980977000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2021-0051\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,1]]},"references-count":31,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,2,10]]},"published-print":{"date-parts":[[2022,2,10]]}},"alternative-id":["10.1515\/jmc-2021-0051"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2021-0051","relation":{},"ISSN":["1862-2984"],"issn-type":[{"type":"electronic","value":"1862-2984"}],"subject":[],"published":{"date-parts":[[2022,1,1]]}}}