Paper 2024/1219

Foldable, Recursive Proofs of Isogeny Computation with Reduced Time Complexity

Abstract

The security of certain post-quantum isogeny-based cryptographic schemes relies on the ability to provably and efficiently compute isogenies between supersingular elliptic curves without leaking information about the isogeny other than its domain and codomain. Earlier work in this direction give mathematical proofs of knowledge for the isogeny, and as a result when computing a chain of $n$ isogenies each proceeding node must verify the correctness of the proof of each preceding node, which is computationally linear in $n$. In this work, we empirically build a system to prove the execution of the circuit computing the isogeny rather than produce a proof of knowledge. This proof can then be used as part of the verifiable folding scheme Nova, which reduces the complexity of an isogeny proof of computation for a chain of $n$ isogenies from $O(n)$ to $O(1)$ by providing at each step a single proof that proves the whole preceding chain. To our knowledge, this is the first application of this type of solution to this problem.