Paper 2021/1289

Verifiable Isogeny Walks: Towards an Isogeny-based Postquantum VDF

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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.Selected Areas in Cryptography – SAC 2021
Keywords
Isogeny-based cryptographyPostquantum cryptographyVerifiable delay functionsSupersingular elliptic curvesSNARGsVerifiable computation
Contact author(s)
jorgechavezsaab @ gmail com
Francisco rodriguez @ cinvestav mx
mehdi tibouchi @ normalesup org
History
2021-11-09: revised
2021-09-24: received
See all versions
Short URL
https://ia.cr/2021/1289
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1289,
      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{https://eprint.iacr.org/2021/1289}},
      url = {https://eprint.iacr.org/2021/1289}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.