{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:21:15Z","timestamp":1764980475717,"version":"3.46.0"},"reference-count":20,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"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":[[2020,8,18]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We give a 4-list algorithm for solving the Elliptic Curve Discrete Logarithm (ECDLP) over some quadratic field \ud835\udd3d\n                    <jats:sub>\n                      <jats:italic>p<\/jats:italic>\n                      <jats:sup>2<\/jats:sup>\n                    <\/jats:sub>\n                    . Using the representation technique, we reduce ECDLP to a multivariate polynomial zero testing problem. Our solution of this problem using bivariate polynomial multi-evaluation yields a\n                    <jats:italic>p<\/jats:italic>\n                    <jats:sup>1.314<\/jats:sup>\n                    -algorithm for ECDLP. While this is inferior to Pollard\u2019s Rho algorithm with square root (in the field size) complexity \ud835\udcde(\n                    <jats:italic>p<\/jats:italic>\n                    ), it still has the potential to open a path to an\n                    <jats:italic>o<\/jats:italic>\n                    (\n                    <jats:italic>p<\/jats:italic>\n                    )-algorithm for ECDLP, since all involved lists are of size as small as\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2019-0025_eq_002.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:mtable>\n                            <m:mtr>\n                              <m:mtd>\n                                <m:msup>\n                                  <m:mi>p<\/m:mi>\n                                  <m:mrow>\n                                    <m:mfrac>\n                                      <m:mn>3<\/m:mn>\n                                      <m:mn>4<\/m:mn>\n                                    <\/m:mfrac>\n                                  <\/m:mrow>\n                                <\/m:msup>\n                                <m:mo>,<\/m:mo>\n                              <\/m:mtd>\n                            <\/m:mtr>\n                          <\/m:mtable>\n                        <\/m:math>\n                        <jats:tex-math>$\\begin{array}{}\np^{\\frac 3 4},\n\\end{array}$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    only their computation is yet too costly.\n                  <\/jats:p>","DOI":"10.1515\/jmc-2019-0025","type":"journal-article","created":{"date-parts":[[2020,8,26]],"date-time":"2020-08-26T07:12:44Z","timestamp":1598425964000},"page":"293-306","source":"Crossref","is-referenced-by-count":0,"title":["Can we Beat the Square Root Bound for ECDLP over \ud835\udd3d\n                    <sub>\n                      <i>p<\/i>\n                    <\/sub>\n                    <sup>2<\/sup>\n                    via Representation?"],"prefix":"10.1515","volume":"14","author":[{"given":"Claire","family":"Delaplace","sequence":"first","affiliation":[{"name":"Horst G\u00f6rtz Institute for IT Security , Ruhr University Bochum , Bochum , Germany"}]},{"given":"Alexander","family":"May","sequence":"additional","affiliation":[{"name":"Horst G\u00f6rtz Institute for IT Security , Ruhr University Bochum , Bochum , Germany"}]}],"member":"374","published-online":{"date-parts":[[2020,8,18]]},"reference":[{"key":"2025120600172416061_j_jmc-2019-0025_ref_001_w2aab3b7e1095b1b6b1ab2b1b1Aa","doi-asserted-by":"crossref","unstructured":"Anja Becker, Jean-S\u00e9bastien Coron and Antoine Joux, Improved Generic Algorithms for Hard Knapsacks, in: Advances in Cryptology \u2013 EUROCRYPT 2011 (Kenneth G. Paterson, ed.), Lecture Notes in Computer Science 6632, pp. 364\u2013385, Springer, Heidelberg, Germany, Tallinn, Estonia, May 15\u201319, 2011.","DOI":"10.1007\/978-3-642-20465-4_21"},{"key":"2025120600172416061_j_jmc-2019-0025_ref_002_w2aab3b7e1095b1b6b1ab2b1b2Aa","unstructured":"Gerhard Frey and Herbert Gangl, How to disguise an elliptic curve (Weil descent), Talk at ECC98 (1998), 128\u2013161."},{"key":"2025120600172416061_j_jmc-2019-0025_ref_003_w2aab3b7e1095b1b6b1ab2b1b3Aa","doi-asserted-by":"crossref","unstructured":"Steven D Galbraith and Pierrick Gaudry, Recent progress on the elliptic curve discrete logarithm problem, Designs, Codes and Cryptography78 (2016), 51\u201372.","DOI":"10.1007\/s10623-015-0146-7"},{"key":"2025120600172416061_j_jmc-2019-0025_ref_004_w2aab3b7e1095b1b6b1ab2b1b4Aa","doi-asserted-by":"crossref","unstructured":"Steven D. Galbraith, Florian Hess and Nigel P. Smart, Extending the GHS Weil Descent Attack, in: Advances in Cryptology \u2013 EUROCRYPT 2002 (Lars R. Knudsen, ed.), Lecture Notes in Computer Science 2332, pp. 29\u201344, Springer, Heidelberg, Germany, Amsterdam, The Netherlands, April 28 \u2013 May 2, 2002.","DOI":"10.1007\/3-540-46035-7_3"},{"key":"2025120600172416061_j_jmc-2019-0025_ref_005_w2aab3b7e1095b1b6b1ab2b1b5Aa","doi-asserted-by":"crossref","unstructured":"Steven D. Galbraith and Nigel P. Smart, A Cryptographic Application of Weil Descent, in: 7th IMA International Conference on Cryptography and Coding (Michael Walker, ed.), Lecture Notes in Computer Science 1746, pp. 191\u2013200, Springer, Heidelberg, Germany, Cirencester, UK, December 20\u201322, 1999.","DOI":"10.1007\/3-540-46665-7_23"},{"key":"2025120600172416061_j_jmc-2019-0025_ref_006_w2aab3b7e1095b1b6b1ab2b1b6Aa","doi-asserted-by":"crossref","unstructured":"Pierrick Gaudry, Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem, Journal of Symbolic Computation44 (2009), 1690 \u2013 1702, Gr\u00f6bner Bases in Cryptography, Coding Theory, and Algebraic Combinatorics.","DOI":"10.1016\/j.jsc.2008.08.005"},{"key":"2025120600172416061_j_jmc-2019-0025_ref_007_w2aab3b7e1095b1b6b1ab2b1b7Aa","doi-asserted-by":"crossref","unstructured":"Pierrick Gaudry, Florian Hess and Nigel P. Smart, Constructive and Destructive Facets of Weil Descent on Elliptic Curves, Journal of Cryptology15 (2002), 19\u201346.","DOI":"10.1007\/s00145-001-0011-x"},{"key":"2025120600172416061_j_jmc-2019-0025_ref_008_w2aab3b7e1095b1b6b1ab2b1b8Aa","doi-asserted-by":"crossref","unstructured":"Nick Howgrave-Graham and Antoine Joux, New Generic Algorithms for Hard Knapsacks, in: Advances in Cryptology \u2013 EUROCRYPT 2010 (Henri Gilbert, ed.), Lecture Notes in Computer Science 6110, pp. 235\u2013256, Springer, Heidelberg, Germany, French Riviera, May 30 \u2013 June 3, 2010.","DOI":"10.1007\/978-3-642-13190-5_12"},{"key":"2025120600172416061_j_jmc-2019-0025_ref_009_w2aab3b7e1095b1b6b1ab2b1b9Aa","unstructured":"Taechan Kim and Mehdi Tibouchi, Equidistribution Among Cosets of Elliptic Curve Points in Intervals, 2019, Accepted at NutMic 2019."},{"key":"2025120600172416061_j_jmc-2019-0025_ref_010_w2aab3b7e1095b1b6b1ab2b1c10Aa","doi-asserted-by":"crossref","unstructured":"Fran\u00e7ois Le Gall, Powers of tensors and fast matrix multiplication, in: Proceedings of the 39th international symposium on symbolic and algebraic computation, ACM, pp. 296\u2013303, 2014.","DOI":"10.1145\/2608628.2608664"},{"key":"2025120600172416061_j_jmc-2019-0025_ref_011_w2aab3b7e1095b1b6b1ab2b1c11Aa","unstructured":"Michael David Mitzenmacher, The power of two random choices in randomized load balancing, Ph.D. thesis, PhD thesis, Graduate Division of the University of California at Berkley, 1996."},{"key":"2025120600172416061_j_jmc-2019-0025_ref_012_w2aab3b7e1095b1b6b1ab2b1c12Aa","doi-asserted-by":"crossref","unstructured":"Michael N\u00fcsken and Martin Ziegler, Fast multipoint evaluation of bivariate polynomials, in: European Symposium on Algorithms, Springer, pp. 544\u2013555, 2004.","DOI":"10.1007\/978-3-540-30140-0_49"},{"key":"2025120600172416061_j_jmc-2019-0025_ref_013_w2aab3b7e1095b1b6b1ab2b1c13Aa","doi-asserted-by":"crossref","unstructured":"Christophe Petit, Michiel Kosters and Ange Messeng, Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields, in: PKC 2016: 19th International Conference on Theory and Practice of Public Key Cryptography, Part II (Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano and Bo-Yin Yang, eds.), Lecture Notes in Computer Science 9615, pp. 3\u201318, Springer, Heidelberg, Germany, Taipei, Taiwan, March 6\u20139, 2016.","DOI":"10.1007\/978-3-662-49387-8_1"},{"key":"2025120600172416061_j_jmc-2019-0025_ref_014_w2aab3b7e1095b1b6b1ab2b1c14Aa","unstructured":"Takakazu Satoh, Kiyomichi Araki et al., Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves, Rikkyo Daigaku sugaku zasshi47 (1998), 81\u201392."},{"key":"2025120600172416061_j_jmc-2019-0025_ref_015_w2aab3b7e1095b1b6b1ab2b1c15Aa","doi-asserted-by":"crossref","unstructured":"Ren\u00e9 Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Mathematics of computation44 (1985), 483\u2013494.","DOI":"10.1090\/S0025-5718-1985-0777280-6"},{"key":"2025120600172416061_j_jmc-2019-0025_ref_016_w2aab3b7e1095b1b6b1ab2b1c16Aa","doi-asserted-by":"crossref","unstructured":"Ren\u00e9 Schoof, Counting points on elliptic curves over finite fields, Journal de th\u00e9orie des nombres de Bordeaux7 (1995), 219\u2013254.","DOI":"10.5802\/jtnb.142"},{"key":"2025120600172416061_j_jmc-2019-0025_ref_017_w2aab3b7e1095b1b6b1ab2b1c17Aa","doi-asserted-by":"crossref","unstructured":"Igor Semaev, Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p, Mathematics of Computation of the American Mathematical Society67 (1998), 353\u2013356.","DOI":"10.1090\/S0025-5718-98-00887-4"},{"key":"2025120600172416061_j_jmc-2019-0025_ref_018_w2aab3b7e1095b1b6b1ab2b1c18Aa","unstructured":"Igor Semaev, Summation polynomials and the discrete logarithm problem on elliptic curves, Cryptology ePrint Archive, Report 2004\/031, 2004, http:\/\/eprint.iacr.org\/2004\/031."},{"key":"2025120600172416061_j_jmc-2019-0025_ref_019_w2aab3b7e1095b1b6b1ab2b1c19Aa","doi-asserted-by":"crossref","unstructured":"Daniel Shanks, Class number, a theory of factorization, and genera, in: Proc. of Symp. Math. Soc., 1971,  20, pp. 41\u2013440, 1971.","DOI":"10.1090\/pspum\/020\/0316385"},{"key":"2025120600172416061_j_jmc-2019-0025_ref_020_w2aab3b7e1095b1b6b1ab2b1c20Aa","doi-asserted-by":"crossref","unstructured":"Nigel P. Smart, The Discrete Logarithm Problem on Elliptic Curves of Trace One, Journal of Cryptology12 (1999), 193\u2013196.","DOI":"10.1007\/s001459900052"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jmc\/14\/1\/article-p293.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2019-0025\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2019-0025\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:17:59Z","timestamp":1764980279000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2019-0025\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,1]]},"references-count":20,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,8,7]]},"published-print":{"date-parts":[[2020,8,7]]}},"alternative-id":["10.1515\/jmc-2019-0025"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2019-0025","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"type":"electronic","value":"1862-2984"},{"type":"print","value":"1862-2976"}],"subject":[],"published":{"date-parts":[[2020,1,1]]}}}