Faster Proofs and VRFs from Isogenies

Shai Levin; Robi Pedersen

Paper 2024/1626

Faster Proofs and VRFs from Isogenies

Shai Levin

, University of Auckland

Robi Pedersen

, Technical University of Denmark, COSIC, KU Leuven

Abstract

We improve recent generic proof systems for isogeny knowledge by Cong, Lai, Levin based on circuit satisfiability, by using radical isogeny descriptions to prove a path in the underlying isogeny graph. We then present a new generic construction for a verifiable random function (VRF) based on a one-more type hardness assumption and zero-knowledge proofs. We argue that isogenies fit the constraints of our construction and instantiate the VRF with a CGL walk and our new proofs. As a different contribution, we also propose a new VRF in the effective group action description of isogenies. Our protocol takes a novel approach based on the polynomial-in-the-exponent technique, but without the need of a trusted setup or heavy preprocessing. We compare our protocols to the current state-of-the-art isogeny VRFs by Leroux and Lai, with a particular emphasis on computational efficiency.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in ASIACRYPT 2025
Keywords: Isogeny-based cryptography Verifiable Random Functions Zero-Knowledge Proofs isogenies cryptographic protocols
Contact author(s): shai levin @ auckland ac nz
robi pedersen @ protonmail com
History: 2025-09-02: last of 3 revisions; 2024-10-10: received; See all versions
Short URL: https://ia.cr/2024/1626
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1626,
      author = {Shai Levin and Robi Pedersen},
      title = {Faster Proofs and {VRFs} from Isogenies},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1626},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1626}
}