Paper 2024/1626 Original: eprint.iacr.org/2024/1626 ↗

Faster Proofs and VRFs from Isogenies

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.