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 $1$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.

Metadata
Available format(s)
-- withdrawn --
Publication info
Preprint. MINOR revision.
Keywords
Isogeny based-cryptographyVerifiable Random FunctionIsogeny Proof of KnowledgeQuaternion
Contact author(s)
antonin leroux @ polytechnique org
History
2021-09-02: withdrawn
2021-06-03: received
See all versions
Short URL
https://ia.cr/2021/744
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.