International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: On the security of OSIDH

Authors:
Pierrick Dartois , IBM Research, Corps des Mines
Luca De Feo , IBM Research
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2022
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.
Video from PKC 2022
BibTeX
@inproceedings{pkc-2022-31740,
  title={On the security of OSIDH},
  publisher={Springer-Verlag},
  author={Pierrick Dartois and Luca De Feo},
  year=2022
}