Paper 2021/744

Proofs of Isogeny Knowledge and Application to Post-quantum One-Time Verifiable Random Function

Antonin Leroux

Abstract

In this paper, we introduce a new method to prove the knowledge of an isogeny of given degree between two supersingular elliptic curves. Our approach can be extended to verify the evaluation of the secret isogeny on some points of the domain. The main advantage of this new proof of knowledge is its compactness which is orders of magnitude better than existing proofs of isogeny knowledge. The principle of our method is to reveal some well-chosen endomorphisms and does not constitute a zero-knowledge proof. However, when the degree is a large prime, we can introduce a new hardness assumption upon which we build the first verifiable random function (VRF) based on isogenies. Our protocol can be seen as a generalization of the BLS-style classical construction from elliptic curves and achieves one-time pseudo-randomness in the random oracle model. We propose concrete parameters for this new scheme which reach post-quantum NIST-1 level of security. Our VRF has an overall cost (proof size, key size and output size) of roughly $$KB, which is shorter than all the other post-quantum instantiations based on lattices. In the process, we also develop several algorithmic tools to solve norm equations over quaternion orders that may be of independent interest.