Cryptology ePrint Archive: Report 2021/1289

Verifiable Isogeny Walks: Towards an Isogeny-based Postquantum VDF

Jorge Chavez-Saab and 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.

Category / Keywords: public-key cryptography / Isogeny-based cryptography, Postquantum cryptography, Verifiable delay functions, Supersingular elliptic curves, SNARGs, Verifiable computation

Original Publication (with minor differences): Selected Areas in Cryptography – SAC 2021

Date: received 24 Sep 2021, last revised 9 Nov 2021

Contact author: jorgechavezsaab at gmail com, Francisco rodriguez at cinvestav mx, mehdi tibouchi at normalesup org

Available format(s): PDF | BibTeX Citation

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.

Version: 20211109:101408 (All versions of this report)

Short URL: ia.cr/2021/1289


[ Cryptology ePrint archive ]