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

This post is about the paper Breaking the decisional Diffie-Hellman problem for class group actions using genus theory by Wouter Castryck, Jana Sotáková and Frederik Vercauteren.

First let us recall the situation in the setting of \mathbb{Z}_p^* where p is prime. A Diffie-Hellman quadruple is (g, g^a, g^b, g^{ab} ) for g \in \mathbb{Z}_p^*. The Decision Diffie-Hellman problem (DDH) is to distinguish such a triple (for uniformly sampled g \in \mathbb{Z}_p^* and a,b \in \mathbb{Z}_{p-1}) from a quadruple (g, g^a, g^b, g^c) for uniformly sampled g \in \mathbb{Z}_p^* and a,b,c \in \mathbb{Z}_{p-1}.

The Legendre symbol is multiplicative, which implies that (\tfrac{g^a}{p} ) = ( \tfrac{g}{p} )^a. If (\tfrac{g}{p})= -1 (which may happen when g has even order) then one can learn the parity of a and b from g^a, g^b respectively, and hence test if the fourth value of the quadruple has Legendre symbol consistent with g^{ab}. This well-known fact allows to reject half of all uniformly sampled quadruples (g, g^a, g^b, g^c) when (\tfrac{g}{p})= -1, which is sufficient to say that DDH is not a hard problem in \mathbb{Z}_p^*.

One can increase the success rate beyond 1/2 by using a random-self-reduction of Diffie-Hellman quadruples, but one can never get a perfect DDH oracle (i.e., an oracle that only accepts (g, g^a, g^b, g^{ab} )) from this technique, as the Legendre symbol only “sees” the order 2 elements.

The Legendre symbol is just a group homomorphism \mathbb{Z}_p^* \to \{ 1, -1\}, and for any prime \ell \mid (p-1) one can get a homomorphism \mathbb{Z}_p^* \to H where H is a subgroup of order \ell. Hence, if (p-1) has a range of small factors then one can get an increasingly accurate algorithm to distinguish Diffie-Hellman quadruples from random quadruples (and hence solve DDH).

[As an aside: The amazing thing about the Legendre symbol, and the reason it is taught in all good number theory courses, is not the existence of a group homomorphism \mathbb{Z}_p^* \to \{ 1, -1\}. This is trivial. What is non-trivial is the quadratic reciprocity law, which gives a non-obvious and very efficient way to compute Legendre symbols.]

Similarly, for any finite group one can consider group homomorphisms to subgroups of small order. So one can also attack elliptic curve DDH in a similar way. This is one of the main reasons why the community works with groups of prime order, and in particular elliptic curves of prime order.

Now we turn to group actions. Let G be a finite group acting on a set X. Write the action of g \in G on x \in X as g*x. For example, let G = Cl( \mathcal{O} ) be an ideal class group acting on the set X of supersingular elliptic curves with j-invariant in \mathbb{F}_p. This is the setting of the CSIDH system in isogeny-based post-quantum crypto. The natural analogue of DLP is: Given E and a * E to compute a. The natural analogue of DDH is to distinguish (E, a*E, b*E, (ab)*E ) from (E, a*E, b*E, c*E ), where a, b, c are uniformly sampled from G.

Knowing about Legendre symbols, it is natural to speculate that one might be able to do something similar for group actions. We’d like a group homomorphism \phi : G \to H for some group H of small prime order, and to be able to compute \phi(a) from a*E. That is what the paper of Castryck, Sotáková and Vercauteren does.

In some survey talks (such as at ANTS 2018 and at the Alice Silverberg birthday conference in 2018) I asked “Can subgroups of ideal class group be exploited?” While I thought this would be a good problem, I did not have any clue how to do this. I am surprised and delighted by the new results.

Without going into the details, what the paper shows is that one can get enough information about the degree of an isogeny from E to a*E (and hence the norm of the ideal a) from looking at pairings of points on the elliptic curve. It is a wonderful and surprising (at least, to me) result, and brings a new set of ideas and techniques into isogeny crypto. The paper is not too hard to follow (don’t be put off by the phrase “genus theory” — it is not as scary as it sounds).

I end with a few small comments. First, as with the case of \mathbb{Z}_p^*, this does not give a perfect algorithm to distinguish DDH quadruples from uniform ones. But it does allow to reject some quadruples as being definitely not DDH, and this is enough to break the DDH assumption. Second, breaking the DDH assumption does not, as far as I know, break any isogeny cryptosystem. This is because isogeny cryptosystems are rather unsophisticated compared with DLP-based protocols. Third, the results do not apply to SIDH and have no impact on the SIKE submission to the NIST standardization process.

To conclude, this paper is a great theoretical result that brings new ideas to the field. What will be next for isogeny crypto? Whatever it is, I look forward to it!

— Steven Galbraith

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s