{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T09:44:29Z","timestamp":1766223869757,"version":"3.48.0"},"reference-count":33,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025,4,14]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    This article aims to speed up (the precomputation stage of) multiscalar multiplication (MSM) on ordinary elliptic curves of\n                    <jats:italic>j<\/jats:italic>\n                    -invariant 0 with respect to specific \u201cindependent\u201d (also known as \u201cbasis\u201d) points. For this purpose, the so-called Mordell\u2013Weil lattices (up to rank 8) with large kissing numbers (up to 240) are employed. In a nutshell, the new approach consists in obtaining more efficiently a considerable number (up to 240) of certain elementary linear combinations of the \u201cindependent\u201d points. By scaling the point (re)generation process, it is thus possible to obtain a significant performance gain. As usual, the resulting curve points can be then regularly used in the main stage of an MSM algorithm to avoid repeating computations. Seemingly, this is the first usage of lattices with large kissing numbers in cryptography, while such lattices have already found numerous applications in other mathematical domains. Without exaggeration, MSM is a widespread primitive (often the unique bottleneck) in modern protocols of real-world elliptic curve cryptography. Moreover, the new (re)generation technique is prone to further improvements by considering Mordell\u2013Weil lattices with even greater kissing numbers.\n                  <\/jats:p>","DOI":"10.1515\/jmc-2024-0034","type":"journal-article","created":{"date-parts":[[2025,4,14]],"date-time":"2025-04-14T11:56:51Z","timestamp":1744631811000},"source":"Crossref","is-referenced-by-count":0,"title":["Application of Mordell\u2013Weil lattices with large kissing numbers to acceleration of multiscalar multiplication on elliptic curves"],"prefix":"10.1515","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4796-8989","authenticated-orcid":false,"given":"Dmitrii","family":"Koshelev","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Lleida , Catalonia , Spain"}]}],"member":"374","published-online":{"date-parts":[[2025,4,14]]},"reference":[{"key":"2025122009205548714_j_jmc-2024-0034_ref_001","unstructured":"ZPRIZE 2022 competition. https:\/\/github.com\/z-prize."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_002","unstructured":"ZPRIZE 2023 competition. https:\/\/www.zprize.io."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_003","doi-asserted-by":"crossref","unstructured":"Avanzi RM. The complexity of certain multi-exponentiation techniques in cryptography. J Cryptol. 2005;18:357\u201373.","DOI":"10.1007\/s00145-004-0229-5"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_004","unstructured":"Bernstein DJ. Pippenger\u2019s exponentiation algorithm; 2002. https:\/\/cr.yp.to\/papers\/pippenger-20020118-retypeset20220327.pdf."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_005","doi-asserted-by":"crossref","unstructured":"Botrel G, El Housni Y. Faster Montgomery multiplication and multi-scalar-multiplication for SNARKs. Trans Cryptographic Hardware Embedded Systems (TCHES). 2023;2023(3):504\u201321.","DOI":"10.46586\/tches.v2023.i3.504-521"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_006","unstructured":"Koshelev D. Generation of two \u201cindependent\u201d points on an elliptic curve of j-invariant \u22600, 1728. 2023. https:\/\/eprint.iacr.org\/2023\/785."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_007","unstructured":"Koshelev D. Generation of \u201cindependent\u201d points on elliptic curves by means of Mordell-Weil lattices. Math Cryptol. 2024;4(1):11\u201322. https:\/\/journals.flvc.org\/mathcryptology\/article\/view\/132727"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_008","unstructured":"Cohn H. Kissing numbers. https:\/\/cohn.mit.edu\/kissing-numbers."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_009","unstructured":"Nebe G, Sloane N. LATTICES. https:\/\/www.math.rwth-aachen.de\/homes\/Gabriele.Nebe\/LATTICES."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_010","doi-asserted-by":"crossref","unstructured":"Vl\u0103du\u0163 S. Lattices with exponentially large kissing numbers. Moscow J Combinat Number Theory. 2019;8(2):163\u201377.","DOI":"10.2140\/moscow.2019.8.163"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_011","unstructured":"Vl\u0103du\u0163 S. Lattices with exponentially large kissing numbers do exist; 2024. https:\/\/arxiv.org\/abs\/2411.07371."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_012","doi-asserted-by":"crossref","unstructured":"Elkies ND. Mordell-Weil lattices in characteristic 2, I: Construction and first properties. Int Math Res Notices. 1994;1994(8):343\u201361.","DOI":"10.1155\/S1073792894000395"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_013","doi-asserted-by":"crossref","unstructured":"Elkies ND. Mordell-Weil lattices in characteristic 2, II: The Leech lattice as a Mordell-Weil lattice. Invent Math. 1997;128(1):1\u20138.","DOI":"10.1007\/s002220050133"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_014","doi-asserted-by":"crossref","unstructured":"Elkies ND. Mordell-Weil lattices in characteristic 2, III: A Mordell-Weil lattice of rank 128. Experiment Math. 2001;10(3):467\u201373.","DOI":"10.1080\/10586458.2001.10504463"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_015","doi-asserted-by":"crossref","unstructured":"Shioda T. Mordell-Weil lattices and sphere packings. Amer J Math. 1991;113(5):931\u201348.","DOI":"10.2307\/2374791"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_016","doi-asserted-by":"crossref","unstructured":"Conway JH, Sloane NJA. Sphere packings, lattices and groups. vol. 290 of Grundlehren der Mathematischen Wissenschaften. 3rd ed. New York: Springer; 2013. https:\/\/doi.org\/10.1007\/978-1-4757-6568-7","DOI":"10.1007\/978-1-4757-6568-7"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_017","unstructured":"Koshelev D. Magma code; 2023. https:\/\/github.com\/dishport\/Application-of-MW-lattices-with-large-kissing-numbers-to-acceleration-of-MSM-on-elliptic-curves."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_018","doi-asserted-by":"crossref","unstructured":"Shioda T. The splitting field of Mordell-Weil lattices. In: Pragacz P, Szurek M, Wi\u015bniewski J, editors. Algebraic Geometry: Hirzebruch 70. vol. 241  of Contemporary Mathematics. Providence: American Mathematical Society; 1999. p. 297\u2013303.","DOI":"10.1090\/conm\/241\/03641"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_019","doi-asserted-by":"crossref","unstructured":"Shioda T. Cyclotomic analogue in the theory of algebraic equations of type E6, E7, E8. In: Kim MH, Hsia JS, Kitaoka Y, Schulze-Pillot R, editors. Integral Quadratic Forms and Lattices. vol. 249 of Contemporary Mathematics. Providence: American Mathematical Society; 1999. p. 87\u201396.","DOI":"10.1090\/conm\/249\/03750"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_020","unstructured":"Bernstein DJ, Lange T. Explicit-Formulas Database. https:\/\/www.hyperelliptic.org\/EFD\/index.html."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_021","doi-asserted-by":"crossref","unstructured":"El Mrabet N, Joye M, editors. Guide to pairing-based cryptography. Cryptography and Network Security Series. New York: Chapman and Hall\/CRC; 2017.","DOI":"10.1201\/9781315370170"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_022","doi-asserted-by":"crossref","unstructured":"Joye M, Lapiha O, Nguyen K, Naccache D. The eleventh power residue symbol. J Math Cryptol. 2021;15(1):111\u201322.","DOI":"10.1515\/jmc-2020-0077"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_023","doi-asserted-by":"crossref","unstructured":"Shioda T. Integral points and Mordell-Weil lattices. In: W\u00fcstholz G, editor. A panorama of number theory or the view from Baker\u2019s garden. Cambridge: Cambridge University Press; 2002. p. 185\u201393.","DOI":"10.1017\/CBO9780511542961.013"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_024","doi-asserted-by":"crossref","unstructured":"Shioda T. Gr\u00f6bner basis, Mordell-Weil lattices and deformation of singularities, I. Proc Jpn Acad A: Math Sci. 2010;86(2):21\u20136.","DOI":"10.3792\/pjaa.86.21"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_025","doi-asserted-by":"crossref","unstructured":"Shioda T. Gr\u00f6bner basis, Mordell-Weil lattices and deformation of singularities, II. Proc Jpn Acad A: Math Sci. 2010;86(2):27\u201332.","DOI":"10.3792\/pjaa.86.27"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_026","unstructured":"Shioda T. Elliptic surfaces and Davenport-Stothers triples. Commentarii Mathematici Universitatis Sancti Pauli, Rikkyo Daigaku Sugaku Zasshi. 2005;54(1):49\u201368."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_027","unstructured":"Oguiso K, Shioda T. The Mordell-Weil lattice of a rational elliptic surface. Commentarii Mathematici Universitatis Sancti Pauli, Rikkyo Daigaku Sugaku Zasshi. 1991;40(1):83\u201399."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_028","unstructured":"Usui H. On the Mordell-Weil lattice of the elliptic curve y2=x3+tm+1. I. Commentarii Mathematici Universitatis Sancti Pauli, Rikkyo Daigaku Sugaku Zasshi. 2000;49(1):71\u20138."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_029","unstructured":"Usui H. On the Mordell-Weil lattice of the elliptic curve y2=x3+tm+1. II. Commentarii Mathematici Universitatis Sancti Pauli, Rikkyo Daigaku Sugaku Zasshi. 2001;50(1):65\u201387."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_030","unstructured":"Usui H. On the Mordell-Weil lattice of the elliptic curve y2=x3+tm+1. III. Commentarii Mathematici Universitatis Sancti Pauli, Rikkyo Daigaku Sugaku Zasshi. 2006;55(2):173\u201394."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_031","unstructured":"Usui H. On the Mordell-Weil lattice of the elliptic curve y2=x3+tm+1. IV. Commentarii Mathematici Universitatis Sancti Pauli, Rikkyo Daigaku Sugaku Zasshi. 2008;57(1):23\u201363."},{"key":"2025122009205548714_j_jmc-2024-0034_ref_032","doi-asserted-by":"crossref","unstructured":"Kumar A, Kuwata M. Elliptic K3 surfaces associated with the product of two elliptic curves: Mordell-Weil lattices and their fields of definition. Nagoya Math J. 2017;228:124\u201385.","DOI":"10.1017\/nmj.2016.56"},{"key":"2025122009205548714_j_jmc-2024-0034_ref_033","unstructured":"Shioda T. The Mordell-Weil lattice of y2=x3+t5\u20121\u2044t5\u201211. Commentarii Mathematici Universitatis Sancti Pauli, Rikkyo Daigaku Sugaku Zasshi. 2007;56(1):45\u201370."}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2024-0034\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2024-0034\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T09:39:52Z","timestamp":1766223592000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2024-0034\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,1]]},"references-count":33,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,4,14]]},"published-print":{"date-parts":[[2025,4,14]]}},"alternative-id":["10.1515\/jmc-2024-0034"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2024-0034","relation":{},"ISSN":["1862-2984"],"issn-type":[{"type":"electronic","value":"1862-2984"}],"subject":[],"published":{"date-parts":[[2025,1,1]]},"article-number":"20240034"}}