Paper 2021/1289 Original: eprint.iacr.org/2021/1289 ↗
Verifiable Isogeny Walks: Towards an Isogeny-based Postquantum VDF
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2021-11-09: last updated
- 2021-09-24: published
- Short URL
- https://ia.cr/2021/1289
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2021/1289}
}