{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T09:54:26Z","timestamp":1785405266540,"version":"3.56.0"},"reference-count":42,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T00:00:00Z","timestamp":1736812800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["PAT6402023"],"award-info":[{"award-number":["PAT6402023"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,3,11]]},"abstract":"<jats:p>VDFs are characterized by sequential function evaluation but an immediate output verification. In order to ensure secure use of VDFs in real-world applications, it is important to determine the fastest implementation. Considering the point of view of an attacker (say with unbounded resources), this paper aims to accelerate the isogeny-based VDF proposed by De Feo-Mason-Petit-Sanso in 2019. It is the first work that implements a hardware accelerator for the evaluation step of an isogeny VDF. To meet our goal, we use redundant representations of integers and introduce a new lookup table-based algorithm for modular reduction. We also provide both a survey of elliptic curve arithmetic to arrive at the most cost-effective curve computations and an in-depth cost analysis of the different base degree isogeny and method for the isogeny evaluation. The evaluation step of a VDF is defined to be sequential, which means that there is limited scope for parallelism. Nevertheless, taking this constraint into account our proposed design targets the highest levels of parallelism possible on an architectural level of an isogeny VDF implementation. We provide a technology-independent metric to model the delay of isogeny evaluation, which a VDF developer can use to derive secure parameters. ASIC synthesis results in 28nm are used as a baseline to estimate VDF parameters.<\/jats:p>","DOI":"10.62056\/a3qj893y6","type":"journal-article","created":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T17:23:17Z","timestamp":1744132997000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":1,"title":["Accelerating Isogeny Walks for VDF Evaluation"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-8386-006X","authenticated-orcid":false,"given":"David","family":"Jacquemin","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00d7xrm67","id-type":"ROR","asserted-by":"publisher"}],"name":"Graz University of Technology","place":["Graz, 8010, Austria"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5565-5744","authenticated-orcid":false,"given":"Anisha","family":"Mukherjee","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00d7xrm67","id-type":"ROR","asserted-by":"publisher"}],"name":"Graz University of Technology","place":["Graz, 8010, Austria"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7400-2450","authenticated-orcid":false,"given":"Ahmet","family":"Mert","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00d7xrm67","id-type":"ROR","asserted-by":"publisher"}],"name":"Graz University of Technology","place":["Graz, 8010, Austria"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9805-5389","authenticated-orcid":false,"given":"Sujoy","family":"Roy","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00d7xrm67","id-type":"ROR","asserted-by":"publisher"}],"name":"Graz University of Technology","place":["Graz, 8010, Austria"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2025,4,8]]},"reference":[{"key":"ref1:Boneh18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/978-3-319-96884-1_25","article-title":"Verifiable Delay Functions","volume":"10991","author":"Dan Boneh","year":"2018"},{"key":"ref2:vdf_tches_stanfort","doi-asserted-by":"publisher","first-page":"163","DOI":"10.46586\/tches.v2022.i4.163-187","article-title":"A Fast Large-Integer Extended GCD Algorithm and Hardware\n  Design for Verifiable Delay Functions and Modular Inversion","volume":"2022","author":"Kavya Sreedhar","year":"2022","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"ref3:Wesolowski19","isbn-type":"print","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/978-3-030-17659-4_13","article-title":"Efficient Verifiable Delay Functions","author":"Benjamin Wesolowski","year":"2019","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030176594"},{"key":"ref4:pietrzak:LIPIcs:2018:10153","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2019.60","article-title":"Simple Verifiable Delay Functions","volume":"124","author":"Krzysztof Pietrzak","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9783959770958","ISSN":"https:\/\/id.crossref.org\/issn\/1868-8969","issn-type":"electronic"},{"key":"ref5:DBLP:journals\/joc\/CharlesLG09","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00145-007-9002-x","article-title":"Cryptographic Hash Functions from Expander Graphs","volume":"22","author":"Denis Xavier Charles","year":"2009","journal-title":"J. Cryptol."},{"key":"ref6:isogeny_vdf_2019","isbn-type":"print","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/978-3-030-34578-5_10","article-title":"Verifiable Delay Functions from Supersingular Isogenies and\n  Pairings","author":"Luca De Feo","year":"2019","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030345785"},{"key":"ref7:Saab22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/978-3-030-99277-4_21","article-title":"Verifiable Isogeny Walks: Towards an Isogeny-Based\n  Postquantum VDF","author":"Jorge Chavez-Saab","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030992774"},{"key":"ref8:isogeny_vdf_2023","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-3-031-44469-2_8","article-title":"Towards a Quantum-Resistant Weak Verifiable Delay Function","volume":"14168","author":"Thomas Decru","year":"2023"},{"key":"ref9:ahmet_vdf","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1109\/TC.2020.3043400","article-title":"Low-Latency ASIC Algorithms of Modular Squaring of Large\n  Integers for VDF Evaluation","volume":"71","author":"Ahmet Can Mert","year":"2022","journal-title":"IEEE Trans. Computers"},{"key":"ref10:BF21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/978-3-030-77870-5_11","article-title":"Delay Encryption","volume":"12696","author":"Jeffrey Burdges","year":"2021"},{"key":"ref11:sike_hw_1","doi-asserted-by":"publisher","DOI":"10.3390\/electronics12051235","article-title":"Towards High-Performance Supersingular Isogeny Cryptographic\n  Hardware Accelerator Design","volume":"12","author":"Guantong Su","year":"2023","journal-title":"Electronics","ISSN":"https:\/\/id.crossref.org\/issn\/2079-9292","issn-type":"electronic"},{"key":"ref12:castryck2022efficient","isbn-type":"print","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","author":"Wouter Castryck","year":"2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031305887"},{"key":"ref13:robert2023breaking","series-title":"Lecture Notes in Computer Science","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":"ref14:maino2023direct","series-title":"Lecture Notes in Computer Science","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":"ref15:SIKE_specs22","article-title":"SIDH-spec","author":"David Jao","year":"2022","journal-title":"NIST"},{"key":"ref16:cs_form_def","isbn-type":"print","volume-title":"Computer arithmetic - algorithms and hardware designs","author":"Behrooz Parhami","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/9780195125832"},{"key":"ref17:sqrtvelu","article-title":"Faster computation of isogenies of large prime degree","volume":"abs\/2003.10118","author":"Daniel J. Bernstein","year":"2020","journal-title":"CoRR"},{"key":"ref18:kani_Velu_comp","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1007\/978-981-96-0891-1_10","article-title":"An Algorithmic Approach to (2, 2)-Isogenies in the Theta\n  Model and Applications to Isogeny-Based Cryptography","volume":"15486","author":"Pierrick Dartois","year":"2024"},{"key":"ref19:isogeny_paper","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1515\/jmc-2012-0015","article-title":"Towards quantum-resistant cryptosystems from supersingular\n  elliptic curve isogenies","volume":"8","author":"Luca De Feo","year":"2014","journal-title":"J. Math. Cryptol."},{"key":"ref20:DN93","isbn-type":"print","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/3-540-48071-4_10","article-title":"Pricing via Processing or Combatting Junk Mail","author":"Cynthia Dwork","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540480716"},{"key":"ref21:Sloth17","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1504\/IJACT.2017.10010315","article-title":"Trustworthy public randomness with sloth, unicorn, and trx","volume":"3","author":"Arjen K. Lenstra","year":"2017","journal-title":"Int. J. Appl. Cryptogr."},{"key":"ref22:RSAW96","volume-title":"Time-Lock Puzzles and Timed-Release Crypto","author":"R. L. Rivest","year":"1996"},{"key":"ref23:DBLP:conf\/scn\/DottlingGMV20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-030-57990-6_4","article-title":"Tight Verifiable Delay Functions","volume":"12238","author":"Nico D\u00f6ttling","year":"2020"},{"key":"ref24:Tate","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/BF01404549","article-title":"Endomorphisms of Abelian Varieties over Finite Fields.","volume":"2","author":"J. Tate","year":"1966","journal-title":"Inventiones Mathematicae"},{"key":"ref25:silverman2009arithmetic","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-09494-6","volume-title":"The Arithmetic of Elliptic Curves","author":"J.H. Silverman","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387094946"},{"key":"ref26:cs_form_Mont_mul","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1109\/EUC.2008.30","article-title":"Accelerating Montgomery Modulo Multiplication for Redundant\n  Radix-64k Number System on the FPGA Using Dual-Port Block RAMs","author":"Koji Shigemoto","year":"2008"},{"key":"ref27:csa_ec_1","doi-asserted-by":"publisher","first-page":"1587","DOI":"10.1109\/TVLSI.2019.2905899","article-title":"High-Speed Implementation of ECC Scalar Multiplication in\n  GF(p) for Generic Montgomery Curves","volume":"27","author":"Debapriya Basu Roy","year":"2019","journal-title":"IEEE Trans. Very Large Scale Integr. Syst."},{"key":"ref28:kong","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ipl.2005.11.015","article-title":"Improved generalized Atkin algorithm for computing square\n  roots in finite fields","volume":"98","author":"Fanyu Kong","year":"2006","journal-title":"Information Processing Letters","ISSN":"https:\/\/id.crossref.org\/issn\/0020-0190","issn-type":"electronic"},{"key":"ref29:cs_form_1","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0898-1221(83)90133-5","article-title":"A carry-free algorithm for finding the greatest common\n  divisor of two integers","volume":"9","author":"George B. Purdy","year":"1983","journal-title":"Computers & Mathematics with Applications","ISSN":"https:\/\/id.crossref.org\/issn\/0898-1221","issn-type":"electronic"},{"key":"ref30:cs_form_2","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1109\/ACSSC.2003.1291939","article-title":"Fast Montgomery modular multiplication and RSA cryptographic\n  processor architectures","volume":"1","author":"C. Mclvor","year":"2003"},{"key":"ref31:CSA_sign","article-title":"Fast algorithm for modular reduction","author":"C. K. Ko\u00e7","year":"1998"},{"key":"ref32:edward_iso","doi-asserted-by":"publisher","DOI":"10.1155\/2018\/5747642","article-title":"Efficient Isogeny Computations on Twisted Edwards Curves","volume":"2018","author":"Suhri Kim","year":"2018","journal-title":"Secur. Commun. Networks"},{"key":"ref33:edwards_iso2","doi-asserted-by":"publisher","first-page":"1929","DOI":"10.1090\/mcom\/3036","article-title":"Analogues of V\u00e9lu's formulas for isogenies on\n  alternate models of elliptic curves","volume":"85","author":"Dustin Moody","year":"2016","journal-title":"Math. Comput."},{"key":"ref34:LCW-isogeny","doi-asserted-by":"publisher","DOI":"10.1201\/9781420071474","volume-title":"Elliptic Curves: Number Theory and Cryptography, Second\n  Edition (2nd ed.).","author":"L.C. Washington","year":"2008"},{"key":"ref35:EKA19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-030-95312-6_3","article-title":"Faster Isogenies for Post-quantum Cryptography: SIKE","volume":"13161","author":"Rami Elkhatib","year":"2022"},{"key":"ref36:2017\/504","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-319-70697-9_11","article-title":"A Simple and Compact Algorithm for SIDH with Arbitrary\n  Degree Isogenies","volume":"10625","author":"Craig Costello","year":"2017"},{"key":"ref37:Velu","first-page":"238","article-title":"Isog\u00e9nies entre courbes elliptiques","volume":"273","author":"J. V\u00e9lu","year":"1971","journal-title":"Comptes-Rendus de l'Acad\u00e9mie des Sciences, S\u00e9rie I"},{"key":"ref38:adder_tree_wallace","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1109\/PGEC.1964.263830","article-title":"A Suggestion for a Fast Multiplier","volume":"13","author":"Christopher S. Wallace","year":"1964","journal-title":"IEEE Trans. Electron. Comput."},{"key":"ref39:adder_tree_Dadda","first-page":"349","article-title":"Some schemes for parallel multipliers","volume":"34","author":"L. Dadda","year":"1965","journal-title":"Alta Frequenza"},{"key":"ref40:sike_hw_2","doi-asserted-by":"publisher","first-page":"4842","DOI":"10.1109\/TCSI.2020.2992747","article-title":"SIKE\u2019d Up: Fast Hardware Architectures for Supersingular\n  Isogeny Key Encapsulation","volume":"67","author":"Brian Koziel","year":"2020","journal-title":"IEEE Transactions on Circuits and Systems I: Regular\n  Papers"},{"key":"ref41:vdf_ches_2023","doi-asserted-by":"publisher","first-page":"438","DOI":"10.46586\/tches.v2023.i1.438-462","article-title":"Low-Latency Design and Implementation of the Squaring in\n  Class Groups for Verifiable Delay Function Using Redundant Representation","volume":"2023","author":"Danyang Zhu","year":"2023","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"ref42:DBLP:journals\/tit\/KimYKPH20","doi-asserted-by":"publisher","first-page":"1934","DOI":"10.1109\/TIT.2019.2938984","article-title":"New Hybrid Method for Isogeny-Based Cryptosystems Using\n  Edwards Curves","volume":"66","author":"Suhri Kim","year":"2020","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T17:25:08Z","timestamp":1744133108000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/1\/30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,8]]},"references-count":42,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,4,8]]}},"URL":"https:\/\/doi.org\/10.62056\/a3qj893y6","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,8]]},"assertion":[{"value":"2025-01-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-1-52"}}