{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T01:13:28Z","timestamp":1779326008808,"version":"3.51.4"},"reference-count":36,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T00:00:00Z","timestamp":1720483200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/S022503\/1"],"award-info":[{"award-number":["EP\/S022503\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002347","name":"Federal Ministry of Education and Research","doi-asserted-by":"publisher","award":["16KISK033"],"award-info":[{"award-number":["16KISK033"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,9,2]]},"abstract":"<jats:p>        Isogeny-based schemes often come with special requirements on         the field of definition of the involved elliptic curves.         For instance, the efficiency of SQIsign, a promising candidate in the NIST         signature standardisation process,         requires a large power of two and a large smooth integer <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>T<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math> to         divide <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:msup>\n                  <mml:mi>p<\/mml:mi>\n                  <mml:mn>2<\/mml:mn>\n                <\/mml:msup>\n                <mml:mo>\u2212<\/mml:mo>\n                <mml:mn>1<\/mml:mn>\n              <\/mml:mrow>\n            <\/mml:math> for its prime parameter <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>p<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math>.                  We present two new methods that combine previous techniques for finding         suitable primes: sieve-and-boost and XGCD-and-boost.         We use these methods to find primes for the NIST submission of SQIsign.         Furthermore, we show that our methods are flexible and can be adapted         to find suitable parameters for other isogeny-based schemes such as         Apr\u00e8sSQI or POKE.         For all three schemes, the parameters we present offer the best performance         among all parameters proposed in the literature. <\/jats:p>","DOI":"10.62056\/ayojbhey6b","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T15:13:33Z","timestamp":1728314013000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":5,"title":["Finding Practical Parameters for   Isogeny-based Cryptography"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2651-8951","authenticated-orcid":false,"given":"Maria","family":"Santos","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02jx3x895","id-type":"ROR","asserted-by":"publisher"}],"name":"University College London","place":["London, UK"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-3040-2965","authenticated-orcid":false,"given":"Jonathan","family":"Eriksen","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05xg72x27","id-type":"ROR","asserted-by":"publisher"}],"name":"Norwegian University of Science and Technology","place":["Trondheim, Norway"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-2972-7324","authenticated-orcid":false,"given":"Michael","family":"Meyer","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01eezs655","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Regensburg","place":["Regensburg, Germany"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5916-6625","authenticated-orcid":false,"given":"Francisco","family":"Rodr\u00edguez-Henr\u00edquez","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/001kv2y39","id-type":"ROR","asserted-by":"publisher"}],"name":"Cryptography Research Center, Technology Innovation Institute","place":["Abu Dhabi, United Arab Emirates"]}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1:NIS23a","volume-title":"Post-quantum cryptography: Digital signature schemes, 2023","author":"NIST","year":"2023"},{"key":"ref2:AC:Costello20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/978-3-030-64834-3_15","article-title":"B-SIDH: Supersingular Isogeny Diffie-Hellman Using\n  Twisted Torsion","volume":"12492","author":"Craig Costello","year":"2020"},{"key":"ref3:AC:DKLPW20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/978-3-030-64837-4_3","article-title":"SQISign: Compact Post-quantum Signatures from Quaternions\n  and Isogenies","volume":"12491","author":"Luca De Feo","year":"2020"},{"key":"ref4:EC:DLLW23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1007\/978-3-031-30589-4_23","article-title":"New Algorithms for the Deuring Correspondence - Towards\n  Practical and Secure SQISign Signatures","volume":"14008","author":"Luca De Feo","year":"2023"},{"key":"ref5:poke","volume-title":"POKE: A Framework for Efficient PKEs, Split KEMs, and OPRFs\n  from Higher-dimensional Isogenies","author":"Andrea Basso","year":"2024"},{"key":"ref6:velu","first-page":"238","article-title":"Isog\u00e9nies entre courbes elliptiques","volume":"273","author":"Jacques V\u00e9lu","year":"1971","journal-title":"Comptes Rendus de l'Acad\u00e9mie des Sciences de Paris,\n  S\u00e9ries A"},{"key":"ref7:velusqrt","doi-asserted-by":"publisher","first-page":"39","DOI":"10.2140\/obs.2020.4.39","article-title":"Faster computation of isogenies of large prime degree","volume":"4","author":"Daniel J Bernstein","year":"2020","journal-title":"Open Book Series"},{"key":"ref8:EC:CosMeyNae21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/978-3-030-77870-5_10","article-title":"Sieving for Twin Smooth Integers with Solutions to the\n  Prouhet-Tarry-Escott Problem","volume":"12696","author":"Craig Costello","year":"2021"},{"key":"ref9:AC:BSCEMNS23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/978-981-99-8739-9_7","article-title":"Cryptographic Smooth Neighbors","volume":"14444","author":"Giacomo Bruno","year":"2023"},{"key":"ref10:EC:CasDec23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/978-3-031-30589-4_15","article-title":"An Efficient Key Recovery Attack on SIDH","volume":"14008","author":"Wouter Castryck","year":"2023"},{"key":"ref11:EC:MMPPW23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/978-3-031-30589-4_16","article-title":"A Direct Key Recovery Attack on SIDH","volume":"14008","author":"Luciano Maino","year":"2023"},{"key":"ref12:EC:Robert23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1007\/978-3-031-30589-4_17","article-title":"Breaking SIDH in Polynomial Time","volume":"14008","author":"Damien Robert","year":"2023"},{"key":"ref13:apressqi","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/978-3-031-58716-0_3","article-title":"Apr\u00e8sSQI: Extra Fast Verification for SQIsign Using\n  Extension-Field Signing","volume":"14651","author":"Maria Corte-Real Santos","year":"2024"},{"key":"ref14:sqisign-specs","volume-title":"SQIsign: Algorithm specifications and supporting\n  documentation","author":"Jorge Chavez-Saab","year":"2023"},{"key":"ref15:SQIsign2D-West","volume-title":"SQIsign2D-West: The Fast, the Small, and the Safer","author":"Andrea Basso","year":"2024"},{"key":"ref16:SQIPrime","volume-title":"SQIPrime: A dimension 2 variant of SQISignHD with non-smooth\n  challenge isogenies","author":"Max Duparc","year":"2024"},{"key":"ref17:SQIsign2D-East","volume-title":"SQIsign2D-East: A New Signature Scheme Using 2-dimensional\n  Isogenies","author":"Kohei Nakagawa","year":"2024"},{"key":"ref18:SQIsignHD","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-031-58716-0_1","article-title":"SQIsignHD: New Dimensions in Cryptography","volume":"14651","author":"Pierrick Dartois","year":"2024"},{"key":"ref19:AAA+24","volume-title":"Optimized SQIsign 1D verification on Intel and Cortex-M4","author":"Marius A. Aardal","year":"2024"},{"key":"ref20:Stormer","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1215\/ijm\/1256067456","article-title":"Quelques th\u00e9or\u00e8mes sur l'\u00e9quation de Pell\n  $x^2-Dy^2=\\pm1$ et leurs applications","author":"Carl St\u00f8rmer","year":"1897","journal-title":"Christiania Videnskabens Selskabs Skrifter, Math. Nat. Kl"},{"key":"ref21:Lehmer","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1215\/ijm\/1256067456","article-title":"On a problem of St\u00f6rmer","volume":"8","author":"Derrick H. Lehmer","year":"1964","journal-title":"Illinois Journal of Mathematics"},{"key":"ref22:BHLNV","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2211.04315","article-title":"Finding twin smooth integers by solving Pell equations","volume":"abs\/2211.04315","author":"Jan Buzek","year":"2022","journal-title":"CoRR"},{"key":"ref23:chm","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1080\/10586458.2013.768483","article-title":"Smooth neighbors","volume":"22","author":"Brian Conrey","year":"2013","journal-title":"Experimental Mathematics"},{"key":"ref24:cryptoeprint:2023\/1576","volume-title":"Towards Optimally Small Smoothness Bounds for\n  Cryptographic-Sized Twin Smooth Integers and their Isogeny-based\n  Applications","author":"Bruno Sterner","year":"2023"},{"key":"ref25:AAA+24b","volume-title":"Scoring primes for computing isogenies in extension\n  fields","author":"Marius A. Aardal","year":"2024"},{"key":"ref26:TCHES:BBCCLMSS21","doi-asserted-by":"publisher","first-page":"351","DOI":"10.46586\/tches.v2021.i4.351-387","article-title":"CTIDH: faster constant-time CSIDH","volume":"2021","author":"Gustavo Banegas","year":"2021","journal-title":"IACR TCHES","ISSN":"https:\/\/id.crossref.org\/issn\/2569-2925","issn-type":"electronic"},{"key":"ref27:LC:CCCDRS19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-030-30530-7_9","article-title":"Stronger and Faster Side-Channel Protections for CSIDH","volume":"11774","author":"Daniel Cervantes-V\u00e1zquez","year":"2019"},{"key":"ref28:CCC+24","doi-asserted-by":"publisher","DOI":"10.62056\/ANJBKSDJA","article-title":"Optimizations and Practicality of High-Security CSIDH","volume":"1","author":"Fabio Campos","year":"2024","journal-title":"IACR Communications in Cryptology"},{"key":"ref29:DftP","series-title":"Contemporary Mathematics","isbn-type":"print","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1090\/conm\/796\/16008","article-title":"Deuring for the People: Supersingular elliptic curves with\n  prescribed endomorphism ring in general characteristic","volume":"796","author":"Jonathan Komada Eriksen","year":"2024","ISBN":"https:\/\/id.crossref.org\/isbn\/9781470472603"},{"key":"ref30:JCEng:BajDuq21","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s13389-021-00260-z","article-title":"Montgomery-friendly primes and applications to\n  cryptography","volume":"11","author":"Jean-Claude Bajard","year":"2021","journal-title":"Journal of Cryptographic Engineering"},{"key":"ref31:Montgomery05","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1109\/TC.2005.49","article-title":"Five, Six, and Seven-Term Karatsuba-Like Formulae","volume":"54","author":"Peter L. Montgomery","year":"2005","journal-title":"IEEE Trans. Computers"},{"key":"ref32:JCEng:Cenk18","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/s13389-017-0155-8","article-title":"Karatsuba-like formulae and their associated techniques","volume":"8","author":"Murat Cenk","year":"2018","journal-title":"Journal of Cryptographic Engineering"},{"key":"ref33:bernstein2004find","volume-title":"How to find smooth parts of integers","author":"Daniel J. Bernstein","year":"2004"},{"key":"ref34:BanksShparlinski","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.8281131","article-title":"Integers with a large smooth divisor","volume":"7","author":"William D. Banks","year":"2007","journal-title":"Integers. Electronic Journal of Combinatorial Number\n  Theory","ISSN":"https:\/\/id.crossref.org\/issn\/1553-1732","issn-type":"electronic"},{"key":"ref35:dickman","article-title":"On the frequency of numbers containing prime factors of a\n  certain relative magnitude","volume":"22","author":"Karl Dickman","year":"1930","journal-title":"Arkiv for matematik, astronomi och fysik"},{"key":"ref36:deBruijn","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S1385-7258(66)50029-4","article-title":"On the number of positive integers $\\leq$ x and free of\n  prime factors $> y$, II","volume":"38","author":"Nicolaas G. de Bruijn","year":"1966","journal-title":"Indag. Math"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:28:40Z","timestamp":1733866120000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":36,"URL":"https:\/\/doi.org\/10.62056\/ayojbhey6b","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"2024-07-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-3-106"}}