Breaking the Decisional Diffie-Hellman Problem for Class Group Actions Using Genus Theory

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 chi : cl(O) -> {+/- 1}, and for each such character and every secret ideal class [a] connecting two public elliptic curves E and E' = [a] star E, we show how to compute chi([alpha]) 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 F-p with p equivalent to 1 mod 4. Our method relies on computing Tate pairings and walking down isogeny volcanoes.