## CryptoDB

### Paper: 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 DOI: 10.1007/978-3-030-56880-1_4 (login may be required) Search ePrint Search Google CRYPTO 2020 Best Paper Award 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 $\mathcal{O}$ with a set of assigned characters $\chi : \text{cl}(\mathcal{O}) \to \{ \pm 1 \}$, and for each such character and every secret ideal class $[\mathfrak{a}]$ connecting two public elliptic curves $E$ and $E' = [\mathfrak{a}] \star E$, we show how to compute $\chi([\mathfrak{a}])$ given only $E$ and $E'$, i.e., without knowledge of $[\mathfrak{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 $\mathbb{F}_p$ with $p \equiv 1 \bmod 4$. 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
}