Verifiable Random Function from the Deuring Correspondence and Higher Dimensional Isogenies

In this paper, we introduce $\mathsf{DeuringVUF}$, a new Verifiable Unpredictable Function (VUF) protocol based on isogenies between supersingular curves.

The most interesting application of this VUF is $\mathsf{DeuringVRF}$ a post-quantum Verifiable Random Function (VRF). The main advantage of this new scheme is its compactness, with combined public key and proof size of roughly 450 bytes, which is orders of magnitude smaller than other generic purpose post-quantum VRF constructions. This scheme is also the first post-quantum VRF satisfying unconditional uniqueness. We show that this scheme is practical by providing a first non-optimized C implementation that runs in roughly 20ms for verification and 175ms for evaluation. 

The function at the heart of our construction is the one that computes the codomain of an isogeny of big prime degree from its kernel. The evaluation can be performed efficiently with the knowledge of the endomorphism ring using a new ideal-to-isogeny algorithm introduced recently by Basso, Dartois, De Feo, Leroux, Maino, Pope, Robert and Wesolowski that uses computation of dimension $2$ isogenies between elliptic products to compute effectively the translation through the Deuring correspondence of any ideal. On the other hand, without the knowledge of the endomorphism ring, this computation appears to be hard. The security of our $\mathsf{DeuringVUF}$ holds under a new assumption call the one-more isogeny problem (OMIP). 

Another application of $\mathsf{DeuringVUF}$ is the first hash-and-sign signature based on isogenies in the standard model. While we don't expect the signature in itself to outperform the recent variants of SQIsign, it remains very competitive in both compactness and efficiency while providing a new framework to build isogeny-based signature that could lead to new interesting applications.  

We also introduce several new algorithms for the effective Deuring correspondence. In particular, we introduce an algorithm to translate an ideal of norm a big power of a small prime $\ell$ into the corresponding isogeny of dimension $1$ using isogenies between abelian variety of dimension $2$ as a tool.
This algorithm can be used to improve the SQIsign signature scheme.