[Resource Topic] 2023/1251: Verifiable random function from the Deuring correspondence and higher dimensional isogenies

Welcome to the resource topic for 2023/1251

Title:
Verifiable random function from the Deuring correspondence and higher dimensional isogenies

Authors: Antonin Leroux

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.

ePrint: https://eprint.iacr.org/2023/1251

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .