Paper 2019/1333

The Dark SIDH of Isogenies

Paul Bottinelli, Victoria de Quehen, Chris Leonardi, Anton Mosunov, Filip Pawlega, and Milap Sheth

Abstract

Many isogeny-based cryptosystems are believed to rely on the hardness of the Supersingular Decision Diffie-Hellman (SSDDH) problem. However, most cryptanalytic efforts have treated the hardness of this problem as being equivalent to the more generic supersingular $\ell^e$-isogeny problem --- an established hard problem in number theory. In this work, we shine some light on the possibility that the combination of two additional pieces of information given in practical SSDDH instances --- the image of the torsion subgroup, and the starting curve's endomorphism ring --- can lead to better attacks cryptosystems relying on this assumption. We show that SIKE/SIDH are secure against our techniques. However, in certain settings, e.g., multi-party protocols, our results may suggest a larger gap between the security of these cryptosystems and the $\ell^e$-isogeny problem. Our analysis relies on the ability to find many endomorphisms on the base curve that have special properties. To the best of our knowledge, this class of endomorphisms has never been studied in the literature. We informally discuss the parameter sets where these endomorphisms should exist. We also present an algorithm which may provide information about additional torsion points under the party's private isogeny, which is of independent interest. Finally, we present a minor variation of the SIKE protocol that avoids exposing a known endomorphism ring.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
isogeniescryptanalysisSIDHSIKE
Contact author(s)
victoria dequehen @ isara com
History
2019-11-20: received
Short URL
https://ia.cr/2019/1333
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1333,
      author = {Paul Bottinelli and Victoria de Quehen and Chris Leonardi and Anton Mosunov and Filip Pawlega and Milap Sheth},
      title = {The Dark SIDH of Isogenies},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1333},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1333}},
      url = {https://eprint.iacr.org/2019/1333}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.