Welcome to the resource topic for 2024/1219
Title:
Foldable, Recursive Proofs of Isogeny Computation with Reduced Time Complexity
Authors: Krystal Maughan, Joseph Near, Christelle Vincent
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.
ePrint: https://eprint.iacr.org/2024/1219
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .