Paper 2021/1681

On the security of OSIDH

Pierrick Dartois and Luca De Feo

Abstract

The Oriented Supersingular Isogeny Diffie-Hellman is a post-quantum key exchange scheme recently introduced by Colò and Kohel. It is based on the group action of an ideal class group of a quadratic imaginary order on a subset of supersingular elliptic curves, and in this sense it can be viewed as a generalization of the popular isogeny based key exchange CSIDH. From an algorithmic standpoint, however, OSIDH is quite different from CSIDH. In a sense, OSIDH uses class groups which are more structured than in CSIDH, creating a potential weakness that was already recognized by Colò and Kohel. To circumvent the weakness, they proposed an ingenious way to realize a key exchange by exchanging partial information on how the class group acts in the neighborhood of the public curves, and conjectured that this additional information would not impact security. In this work we revisit the security of OSIDH by presenting a new attack, building upon previous work of Onuki. Our attack has exponential complexity, but it practically breaks Colò and Kohel's parameters unlike Onuki's attack. We also discuss countermeasures to our attack, and analyze their impact on OSIDH, both from an efficiency and a functionality point of view.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2022
Keywords
Post-quantum cryptographyIsogeniesCryptographic group actions.
Contact author(s)
pierrickdartois @ icloud com
History
2021-12-24: revised
2021-12-22: received
See all versions
Short URL
https://ia.cr/2021/1681
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1681,
      author = {Pierrick Dartois and Luca De Feo},
      title = {On the security of OSIDH},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1681},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1681}},
      url = {https://eprint.iacr.org/2021/1681}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.