CryptoDB
Verifiable random function from the Deuring correspondence and higher dimensional isogenies
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2025 |
| Abstract: | In this paper, we introduce \textsf{DeuringVUF}, a new Verifiable Unpredictable Function (VUF) protocol based on isogenies between supersingular curves. The most interesting application of this VUF is \textsf{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 400 bytes, which is orders of magnitude smaller than other generic purpose post-quantum VRF constructions. We also show that this scheme is practical by providing a first non-optimized C implementation that runs in roughly 20ms for verification and 350ms 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 \textsf{DeuringVUF} holds under a new assumption call the one-more isogeny problem (OMIP). Another application of \textsf{DeuringVUF} is the first hash-and-sign signature based on isogenies. 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. |
BibTeX
@inproceedings{eurocrypt-2025-34967,
title={Verifiable random function from the Deuring correspondence and higher dimensional isogenies},
publisher={Springer-Verlag},
author={Antonin Leroux},
year=2025
}