Paper 2021/1289

Verifiable Isogeny Walks: Towards an Isogeny-based Postquantum VDF

Jorge Chavez-Saab, Francisco Rodríguez Henríquez, and Mehdi Tibouchi


In this paper, we investigate the problem of constructing postquantum-secure verifiable delay functions (VDFs), particularly based on supersingular isogenies. Isogeny-based VDF constructions have been proposed before, but since verification relies on pairings, they are broken by quantum computers. We propose an entirely different approach using succinct non-interactive arguments (SNARGs), but specifically tailored to the arithmetic structure of the isogeny setting to achieve good asymptotic efficiency. We obtain an isogeny-based VDF construction with postquantum security, quasi-logarithmic verification, and requiring no trusted setup. As a building block, we also construct non-interactive arguments for isogeny walks in the supersingular graph over Fp2 , which may be of independent interest.

Note: A typo in the statement of Theorem 2 has been addressed, which changes the complexities appearing in the appendix. The main results and complexities appearing in the body of the paper remain unchanged.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Selected Areas in Cryptography – SAC 2021
Isogeny-based cryptographyPostquantum cryptographyVerifiable delay functionsSupersingular elliptic curvesSNARGsVerifiable computation
Contact author(s)
jorgechavezsaab @ gmail com
Francisco rodriguez @ cinvestav mx
mehdi tibouchi @ normalesup org
2021-11-09: revised
2021-09-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jorge Chavez-Saab and Francisco Rodríguez Henríquez and Mehdi Tibouchi},
      title = {Verifiable Isogeny Walks: Towards an Isogeny-based Postquantum VDF},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1289},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.