Welcome to the resource topic for 2023/549
Title:
Weak instances of class group action based cryptography via self-pairings
Authors: Wouter Castryck, Marc Houben, Simon-Philipp Merz, Marzio Mula, Sam van Buuren, Frederik Vercauteren
Abstract:In this paper we study non-trivial self-pairings with cyclic domains that are compatible with isogenies between elliptic curves oriented by an imaginary quadratic order \mathcal{O}. We prove that the order m of such a self-pairing necessarily satisfies m \mid \Delta_\mathcal{O} (and even 2m \mid \Delta_\mathcal{O} if 4 \mid \Delta_\mathcal{O} and 4m \mid \Delta_\mathcal{O} if 8 \mid \Delta_\mathcal{O}) and is not a multiple of the field characteristic. Conversely, for each m satisfying these necessary conditions, we construct a family of non-trivial cyclic self-pairings of order m that are compatible with oriented isogenies, based on generalized Weil and Tate pairings.
As an application, we identify weak instances of class group actions on elliptic curves assuming the degree of the secret isogeny is known. More in detail, we show that if m^2 \mid \Delta_\mathcal{O} for some prime power m then given two primitively \mathcal{O}-oriented elliptic curves (E, \iota) and (E',\iota') = [\mathfrak{a}] E,\iota) connected by an unknown invertible ideal \mathfrak{a} \subseteq \mathcal{O}, we can recover \mathfrak{a} essentially at the cost of a discrete logarithm computation in a group of order m^2, assuming the norm of \mathfrak{a} is given and is smaller than m^2. We give concrete instances, involving ordinary elliptic curves over finite fields, where this turns into a polynomial time attack.
Finally, we show that these self-pairings simplify known results on the decisional Diffie-Hellman problem for class group actions on oriented elliptic curves.
ePrint: https://eprint.iacr.org/2023/549
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .