Zero-Knowledge Proofs for SIDH variants with Masked Degree or Torsion

Youcef Mokrani; David Jao

Paper 2024/056

Zero-Knowledge Proofs for SIDH variants with Masked Degree or Torsion

Youcef Mokrani, University of Waterloo

David Jao

, University of Waterloo

Abstract

The polynomial attacks on SIDH by Castryck, Decru, Maino, Martindale and Robert have shown that, while the general isogeny problem is still considered unfeasible to break, it is possible to efficiently compute a secret isogeny when given its degree and image on enough torsion points. A natural response from many researchers has been to propose SIDH variants where one or both of these possible extra pieces of information is masked in order to obtain schemes for which a polynomial attack is not currently known. Example of such schemes are M-SIDH, MD-SIDH and FESTA. However, by themselves, theses SIDH variants are vulnerable to the same adaptive attacks where the adversary sends public keys whose associated isogeny is either unknown or inexistent. For the original SIDH scheme, one possible defense against these attacks is to use zero-knowledge proofs that a secret isogeny has been honestly computed. However, such proofs do not currently exist for most SIDH variants. In this paper, we present new zero-knowledge proofs for isogenies whose degree or torsion points have been masked. The security of these proofs mainly relies on the hardness of DSSP.

Note: Corrected Typo

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. SPACE 2023
DOI: 10.1007/978-3-031-51583-5_3
Keywords: Elliptic curves Supersingular isogenies Zero-knowledge proofs
Contact author(s): ymokrani @ uwaterloo ca
djao @ uwaterloo ca
History: 2024-01-15: revised; 2024-01-14: received; See all versions
Short URL: https://ia.cr/2024/056
License: CC BY-SA

BibTeX

@misc{cryptoeprint:2024/056,
      author = {Youcef Mokrani and David Jao},
      title = {Zero-Knowledge Proofs for {SIDH} variants with Masked Degree or Torsion},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/056},
      year = {2024},
      doi = {10.1007/978-3-031-51583-5_3},
      url = {https://eprint.iacr.org/2024/056}
}