Accelerating Isogeny Walks for VDF Evaluation
Authors
David Jacquemin, Anisha Mukherjee, Ahmet Can Mert, Sujoy Sinha Roy
David Jacquemin
Graz University of Technology, Graz, Austria
david dot jacquemin at student dot tugraz dot at
david dot jacquemin at student dot tugraz dot at
Anisha Mukherjee
Graz University of Technology, Graz, Austria
anisha dot mukherjee at tugraz dot at
anisha dot mukherjee at tugraz dot at
Ahmet Can Mert
Graz University of Technology, Graz, Austria
ahmet dot mert at iaik dot tugraz dot at
ahmet dot mert at iaik dot tugraz dot at
Sujoy Sinha Roy
Graz University of Technology, Graz, Austria
sujoy dot sinharoy at tugraz dot at
sujoy dot sinharoy at tugraz dot at
Abstract
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.
References
[BBBF18]
Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch. Verifiable Delay Functions. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I, volume 10991 of Lecture Notes in Computer Science, pages 757–788. 2018. Springer. DOI: 10.1007/978-3-319-96884-1_25
[BF21]
Jeffrey Burdges and Luca De Feo. Delay Encryption. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part I, volume 12696 of Lecture Notes in Computer Science, pages 302–326. 2021. Springer. DOI: 10.1007/978-3-030-77870-5_11
[BFLS20]
Daniel J. Bernstein, Luca De Feo, Antonin Leroux, and Benjamin Smith. Faster computation of isogenies of large prime degree. CoRR, abs/2003.10118, 2020.
[CD23]
Wouter Castryck and Thomas Decru. An Efficient Key Recovery Attack On SIDH. In Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V, pages 423–447, Berlin, Heidelberg. 2023. Springer-Verlag. DOI: 10.1007/978-3-031-30589-4_15
[CH17]
Craig Costello and Hüseyin Hisil. A Simple and Compact Algorithm for SIDH with Arbitrary Degree Isogenies. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part II, volume 10625 of Lecture Notes in Computer Science, pages 303–329. 2017. Springer. DOI: 10.1007/978-3-319-70697-9_11
[CLG09]
Denis Xavier Charles, Kristin E. Lauter, and Eyal Z. Goren. Cryptographic Hash Functions from Expander Graphs. J. Cryptol., 22(1):93–113, 2009. DOI: 10.1007/s00145-007-9002-x
[CSRHT22]
Jorge Chavez-Saab, Francisco Rodríguez-Henríquez, and Mehdi Tibouchi. Verifiable Isogeny Walks: Towards an Isogeny-Based Postquantum VDF. In Riham AlTawy and Andreas Hülsing, editors, Selected Areas in Cryptography, pages 441–460, Cham. 2022. Springer International Publishing.
[Dad65]
L. Dadda. Some schemes for parallel multipliers. Alta Frequenza, 34:349–356, 1965.
[DFMPS19]
Luca De Feo, Simon Masson, Christophe Petit, and Antonio Sanso. Verifiable Delay Functions from Supersingular Isogenies and Pairings. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology – ASIACRYPT 2019, pages 248–277, Cham. 2019. Springer International Publishing.
[DGMV20]
Nico Döttling, Sanjam Garg, Giulio Malavolta, and Prashant Nalini Vasudevan. Tight Verifiable Delay Functions. In Clemente Galdi and Vladimir Kolesnikov, editors, Security and Cryptography for Networks - 12th International Conference, SCN 2020, Amalfi, Italy, September 14-16, 2020, Proceedings, volume 12238 of Lecture Notes in Computer Science, pages 65–84. 2020. Springer. DOI: 10.1007/978-3-030-57990-6_4
[DMPR24]
Pierrick Dartois, Luciano Maino, Giacomo Pope, and Damien Robert. An Algorithmic Approach to (2, 2)-Isogenies in the Theta Model and Applications to Isogeny-Based Cryptography. In Kai-Min Chung and Yu Sasaki, editors, Advances in Cryptology - ASIACRYPT 2024 - 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9-13, 2024, Proceedings, Part III, volume 15486 of Lecture Notes in Computer Science, pages 304–338. 2024. Springer. DOI: 10.1007/978-981-96-0891-1_10
[DMS23]
Thomas Decru, Luciano Maino, and Antonio Sanso. Towards a Quantum-Resistant Weak Verifiable Delay Function. In Abdelrahaman Aly and Mehdi Tibouchi, editors, Progress in Cryptology - LATINCRYPT 2023 - 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Quito, Ecuador, October 3-6, 2023, Proceedings, volume 14168 of Lecture Notes in Computer Science, pages 149–168. 2023. Springer. DOI: 10.1007/978-3-031-44469-2_8
[DN93]
Cynthia Dwork and Moni Naor. Pricing via Processing or Combatting Junk Mail. In Ernest F. Brickell, editor, Advances in Cryptology — CRYPTO' 92, pages 139–147, Berlin, Heidelberg. 1993. Springer Berlin Heidelberg.
[EKA22]
Rami Elkhatib, Brian Koziel, and Reza Azarderakhsh. Faster Isogenies for Post-quantum Cryptography: SIKE. In Steven D. Galbraith, editor, Topics in Cryptology - CT-RSA 2022 - Cryptographers' Track at the RSA Conference 2022, Virtual Event, March 1-2, 2022, Proceedings, volume 13161 of Lecture Notes in Computer Science, pages 49–72. 2022. Springer. DOI: 10.1007/978-3-030-95312-6_3
[FJP14]
Luca De Feo, David Jao, and Jérôme Plût. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. J. Math. Cryptol., 8(3):209–247, 2014. DOI: 10.1515/jmc-2012-0015
[JAC+22]
David Jao, Reza Azarderakhsh, Matthew Campagna, Craig Costello, Luca De Feo, Basil Hess, Aaron Hutchinson, Amir Jalali, Koray Karabina, Brian Koziel, Brian LaMacchia, Patrick Long, Michael Naehrig, Geovandro Pereira, Joost Renes, Vladimir Soukharev, and David Urbanik. SIDH-spec. NIST, 2022.
[KAK+20]
Brian Koziel, A-Bon Ackie, Rami El Khatib, Reza Azarderakhsh, and Mehran Mozaffari Kermani. SIKE’d Up: Fast Hardware Architectures for Supersingular Isogeny Key Encapsulation. IEEE Transactions on Circuits and Systems I: Regular Papers, 67(12):4842-4854, 2020. DOI: 10.1109/TCSI.2020.2992747
[KCYL06]
Fanyu Kong, Zhun Cai, Jia Yu, and Daxing Li. Improved generalized Atkin algorithm for computing square roots in finite fields. Information Processing Letters, 98(1):1-5, 2006. DOI: https://doi.org/10.1016/j.ipl.2005.11.015
[KH98]
C. K. Koç and Ching-Yu Hung. Fast algorithm for modular reduction. In IEE Proceedings: Computers and Digital Techniques. 1998.
[KYK+18]
Suhri Kim, Kisoon Yoon, Jihoon Kwon, Seokhie Hong, and Young-Ho Park. Efficient Isogeny Computations on Twisted Edwards Curves. Secur. Commun. Networks, 2018:5747642:1–5747642:11, 2018. DOI: 10.1155/2018/5747642
[KYK+20]
Suhri Kim, Kisoon Yoon, Jihoon Kwon, Young-Ho Park, and Seokhie Hong. New Hybrid Method for Isogeny-Based Cryptosystems Using Edwards Curves. IEEE Trans. Inf. Theory, 66(3):1934–1943, 2020. DOI: 10.1109/TIT.2019.2938984
[LW17]
Arjen K. Lenstra and Benjamin Wesolowski. Trustworthy public randomness with sloth, unicorn, and trx. Int. J. Appl. Cryptogr., 3(4):330–343, 2017. DOI: 10.1504/IJACT.2017.10010315
[MMM03]
C. Mclvor, M. McLoone, and J.V. McCanny. Fast Montgomery modular multiplication and RSA cryptographic processor architectures. In The Thrity-Seventh Asilomar Conference on Signals, Systems & Computers, 2003, volume 1, pages 379-384 Vol.1. 2003. DOI: 10.1109/ACSSC.2003.1291939
[MMP+23]
Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, and Benjamin Wesolowski. A Direct Key Recovery Attack on SIDH. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V, volume 14008 of Lecture Notes in Computer Science, pages 448–471. 2023. Springer. DOI: 10.1007/978-3-031-30589-4_16
[M{\"{O}}S22]
Ahmet Can Mert, Erdinç Öztürk, and Erkay Savas. Low-Latency ASIC Algorithms of Modular Squaring of Large Integers for VDF Evaluation. IEEE Trans. Computers, 71(1):107–120, 2022. DOI: 10.1109/TC.2020.3043400
[MS16]
Dustin Moody and Daniel Shumow. Analogues of Vélu's formulas for isogenies on alternate models of elliptic curves. Math. Comput., 85(300):1929–1951, 2016. DOI: 10.1090/mcom/3036
[Par00]
Behrooz Parhami. Computer arithmetic - algorithms and hardware designs. Oxford University Press 2000.
[Pie18]
Krzysztof Pietrzak. Simple Verifiable Delay Functions. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 60:1–60:15, Dagstuhl, Germany. 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. DOI: 10.4230/LIPIcs.ITCS.2019.60
[Pur83]
George B. Purdy. A carry-free algorithm for finding the greatest common divisor of two integers. Computers & Mathematics with Applications, 9(2):311-316, 1983. DOI: https://doi.org/10.1016/0898-1221(83)90133-5
[RM19]
Debapriya Basu Roy and Debdeep Mukhopadhyay. High-Speed Implementation of ECC Scalar Multiplication in GF(p) for Generic Montgomery Curves. IEEE Trans. Very Large Scale Integr. Syst., 27(7):1587–1600, 2019. DOI: 10.1109/TVLSI.2019.2905899
[Rob23]
Damien Robert. Breaking SIDH in Polynomial Time. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V, volume 14008 of Lecture Notes in Computer Science, pages 472–503. 2023. Springer. DOI: 10.1007/978-3-031-30589-4_17
[RSW96]
R. L. Rivest, A. Shamir, and D. A. Wagner. Time-Lock Puzzles and Timed-Release Crypto. Technical report, Massachusetts Institute of Technology. 1996.
[SB23]
Guantong Su and Guoqiang Bai. Towards High-Performance Supersingular Isogeny Cryptographic Hardware Accelerator Design. Electronics, 12(5), 2023. DOI: 10.3390/electronics12051235
[SHT22]
Kavya Sreedhar, Mark Horowitz, and Christopher Torng. A Fast Large-Integer Extended GCD Algorithm and Hardware Design for Verifiable Delay Functions and Modular Inversion. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2022(4):163–187, 2022. DOI: 10.46586/tches.v2022.i4.163-187
[Sil09]
J.H. Silverman. The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics. Springer New York 2009.
[SKN08]
Koji Shigemoto, Kensuke Kawakami, and Koji Nakano. Accelerating Montgomery Modulo Multiplication for Redundant Radix-64k Number System on the FPGA Using Dual-Port Block RAMs. In Cheng-Zhong Xu and Minyi Guo, editors, 2008 IEEE/IPIP International Conference on Embedded and Ubiquitous Computing (EUC 2008), Shanghai, China, December 17-20, 2008, Volume I, pages 44–51. 2008. IEEE Computer Society. DOI: 10.1109/EUC.2008.30
[{Tat}66]
J. Tate. Endomorphisms of Abelian Varieties over Finite Fields.. Inventiones Mathematicae, 2:134, January 1966. DOI: 10.1007/BF01404549
[V{\'e}l71]
J. Vélu. Isogénies entre courbes elliptiques. Comptes-Rendus de l'Académie des Sciences, Série I, 273:238–241, juillet 1971.
[Wal64]
Christopher S. Wallace. A Suggestion for a Fast Multiplier. IEEE Trans. Electron. Comput., 13(1):14–17, 1964. DOI: 10.1109/PGEC.1964.263830
[Was08]
L.C. Washington. Elliptic Curves: Number Theory and Cryptography, Second Edition (2nd ed.).. Chapman and Hall/CRC 2008. DOI: 10.1201/9781420071474
[Wes19]
Benjamin Wesolowski. Efficient Verifiable Delay Functions. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, pages 379–407, Cham. 2019. Springer International Publishing.
[ZZO+23]
Danyang Zhu, Rongrong Zhang, Lun Ou, Jing Tian, and Zhongfeng Wang. Low-Latency Design and Implementation of the Squaring in Class Groups for Verifiable Delay Function Using Redundant Representation. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(1):438–462, 2023. DOI: 10.46586/tches.v2023.i1.438-462
PDF
History
Submitted: 2025-01-14
Accepted: 2025-03-11
Published: 2025-04-08
Accepted: 2025-03-11
Published: 2025-04-08
How to cite
David Jacquemin, Anisha Mukherjee, Ahmet Can Mert, and Sujoy Sinha Roy, Accelerating Isogeny Walks for VDF Evaluation. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/a3qj893y6.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.