International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Breaking the decisional Diffie-Hellman problem for class group actions using genus theory

Authors:
Wouter Castryck , imec-COSIC, KU Leuven, Belgium
Jana Sotakova , QuSoft / University of Amsterdam, The Netherlands
Frederik Vercauteren , imec-COSIC, KU Leuven, Belgium
Download:
DOI: 10.1007/978-3-030-56880-1_4 (login may be required)
Search ePrint
Search Google
Conference: CRYPTO 2020
Award: Best Paper Award
Abstract: In this paper, we use genus theory to analyze the hardness of the decisional Diffie--Hellman problem (DDH) for ideal class groups of imaginary quadratic orders, acting on sets of elliptic curves through isogenies; such actions are used in the Couveignes--Rostovtsev--Stolbunov protocol and in CSIDH. Concretely, genus theory equips every imaginary quadratic order O with a set of assigned characters χ:cl(O)→{±1}, and for each such character and every secret ideal class [a] connecting two public elliptic curves E and E′=[a]⋆E, we show how to compute χ([a]) given only E and E′, i.e., without knowledge of [a]. In practice, this breaks DDH as soon as the class number is even, which is true for a density 1 subset of all imaginary quadratic orders. For instance, our attack works very efficiently for all supersingular elliptic curves over Fp with p≡1mod4. Our method relies on computing Tate pairings and walking down isogeny volcanoes.
BibTeX
@inproceedings{crypto-2020-30457,
  title={Breaking the decisional Diffie-Hellman problem for class group actions using genus theory},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-56880-1_4},
  author={Wouter Castryck and Jana Sotakova and Frederik Vercauteren},
  year=2020
}