Paper 2023/037

Efficient Isogeny Proofs Using Generic Techniques

Kelong Cong, KU Leuven
Yi-Fu Lai, University of Auckland
Shai Levin, University of Auckland
Abstract

Generating supersingular elliptic curves of unknown endomorphism ring has been a problem vexing isogeny-based cryptographers for several years. A recent development has proposed a trusted setup protocol to generate such a curve, where each participant generates and proves knowledge of an isogeny. Thus, the construction of efficient proofs of knowledge of isogeny has developed new interest. Historically, the isogeny community has assumed that obtaining isogeny proofs of knowledge from generic proof systems, such as zkSNARKs, was not a practical approach. We contribute the first concrete result in this area by applying Aurora (EUROCRYPT'19), Ligero (CCS'17) and Limbo (CCS'21) to an isogeny path relation, and comparing their performance to a state-of-the-art, tailor-made protocol for the same relation. In doing so, we show that modern generic proof systems are competitive when applied to isogeny assumptions, and provide an order of magnitude ($3\textrm{-}10\times$) improvement to proof and verification times, with similar proof sizes. In addition, these proofs provide a stronger notion of soundness, and statistical zero-knowledge; a property that has only recently been achieved in isogeny PoKs. Independently, this technique shows promise as a component in the design of future isogeny-based or other post-quantum protocols.

Note: Update 10 Feb 2023: We correct the information of the comparison table in Sec 4 (see Remark 3). In App A, we include a method preventing backtracking for completeness.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
IsogenyZero-knowledgezkSNARKInteractive Oracle ProofMPC-in-the-Head
Contact author(s)
kelong cong @ esat kuleuven be
27182818284fu lai @ gmail com
shai levin @ auckland ac nz
History
2023-02-10: last of 2 revisions
2023-01-11: received
See all versions
Short URL
https://ia.cr/2023/037
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/037,
      author = {Kelong Cong and Yi-Fu Lai and Shai Levin},
      title = {Efficient Isogeny Proofs Using Generic Techniques},
      howpublished = {Cryptology ePrint Archive, Paper 2023/037},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/037}},
      url = {https://eprint.iacr.org/2023/037}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.