Paper 2017/571

Faster Algorithms for Isogeny Problems using Torsion Point Images

Christophe Petit

Abstract

There is a recent trend in cryptography to construct protocols based on the hardness of computing isogenies between supersingular elliptic curves. Two prominent examples are Jao-De Feo's key exchange protocol and the resulting encryption scheme by De Feo-Jao-Plût. One particularity of the isogeny problems underlying these protocols is that some additional information is given in input, namely the image of some torsion points with order coprime to the isogeny. This additional information was used in several active attacks against the protocols but the current best passive attacks on the protocols make no use of it at all. In this paper, we provide new algorithms that exploit the additional information provided in isogeny protocols to speed up the resolution of the underlying problems. Our techniques lead to a heuristic polynomial-time key recovery on a non-standard variant of De Feo-Jao-Plût's protocols in a plausible attack model. This shows that at least some isogeny problems are easier to solve when additional information is leaked.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Asiacrypt 2017
Keywords
isogeny-based cryptographycryptanalysis
Contact author(s)
christophe f petit @ gmail com
History
2017-09-14: revised
2017-06-14: received
See all versions
Short URL
https://ia.cr/2017/571
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/571,
      author = {Christophe Petit},
      title = {Faster Algorithms for Isogeny Problems using Torsion Point Images},
      howpublished = {Cryptology ePrint Archive, Paper 2017/571},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/571}},
      url = {https://eprint.iacr.org/2017/571}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.