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

##### Abstract

In this paper, we use genus theory to analyze the hardness of the decisional Diffie-Hellman problem for ideal class groups of imaginary quadratic orders acting on sets of elliptic curves through isogenies (DDH-CGA). 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-CGA 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. We also show that these ideas carry over, at least partly, to abelian varieties of arbitrary dimension. This is an extended version of the paper that was presented at Crypto 2020.

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2020
Keywords
Decisional Diffie-Hellman isogeny-based cryptography class group action CSIDH
Contact author(s)
wouter castryck @ gmail com
j s sotakova @ uva nl
frederik vercauteren @ gmail com
History
2022-07-20: last of 3 revisions
See all versions
Short URL
https://ia.cr/2020/151

CC BY

BibTeX

@misc{cryptoeprint:2020/151,
author = {Wouter Castryck and Jana Sotáková and Frederik Vercauteren},
title = {Breaking the decisional Diffie-Hellman problem for class group actions using genus theory -- extended version},
howpublished = {Cryptology ePrint Archive, Paper 2020/151},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/151}},
url = {https://eprint.iacr.org/2020/151}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.