Paper 2023/1251

Verifiable random function from the Deuring correspondence and higher dimensional isogenies

Abstract

In this paper, we introduce the family $\mathsf{DeuringVRF}_{y,z}$ of Verifiable Random Function (VRF) protocols. Based on isogenies between supersingular curves, the random function at the heart of our scheme is the one that computes the codomain of an isogeny of big prime degree from its kernel. In $\mathsf{DeuringVRF}_{y,z}$, the evaluation is done with algorithms for the Deuring correspondence that make use of isogenies in dimension $z$, and the verification is based on the isogeny representation obtained from isogenies in dimension $y$. The main advantage of the $\mathsf{DeuringVRF}_{y,z}$ family is its compactness, with proof sizes of a few hundred bytes, which is orders of magnitude smaller than other generic purpose post-quantum VRF constructions. We describe four variants of our scheme with $(y,z) \in \lbrace (2,1),(2,2),(4,1), (4,2) \rbrace$ each offering different tradeoffs between compactness, evaluation efficiency and verification efficiency. In the process, we introduce several new algorithms that might be of independent interest. In particular, for the variants with $z=2$, we introduce the first algorithm to translate an ideal into the corresponding isogeny of dimension $1$ using isogenies between abelian variety of dimension $2$ as a tool. The main advantage of this new algorithm compared to existing solution is the relaxation of the constraints on the prime characteristic: our new algorithm can run efficiently with ``SIDH primes" that are very easy to generate unlike ``SQIsign primes" that are currently required by the state of the art appoach. We believe that this algorithm opens a promising research direction to speed-up other schemes based on the Deuring correspondence such as the SQIsign signature scheme.

Note: Some changes with the RandomGoodEndomorphism algorithm