## New discrete logarithm records, and the death of Type 1 pairings

In the last few days there have been several announcements of record-breaking discrete logarithm computations:

All these papers are using the algorithmic ideas introduced by Joux and others in 2013.

The third result listed above is a continuation of the sort of records previously announced, in particular, since 9234 = 18 * 513 and 513 = 2^9 + 1, it is again using “twisted Kummer” extensions over GF( 2^9 ). This result breaks by a large margin the previous world-record for finite field discrete logarithm computations. It is a great result.

However, the first two results are particularly interesting from the point of view of pairing-based cryptography. Both of the computations are for fields that very naturally arise in pairing-based cryptography using supersingular curves. Importantly, the “large prime” in the field size is not a power of 2 plus or minus 1. Hence these records have shown that the new algorithmic ideas can be applied to a wider range of fields than the previous computations might suggest. This gives evidence that all supersingular elliptic and hyperelliptic curves over moderately-sized fields of small characteristic are not secure for pairing-based cryptography.

One interesting consequence of these works is that “Type 1″ pairings are now essentially dead. Recall that Galbraith, Paterson and Smart “Pairings for cryptographers” (Discrete Applied Mathematics, 2008) introduced a classification of pairings into Type 1, Type 2 and Type 3 (there is also a Type 4, but it is rarely used). Type 3 pairings are usually the most efficient, but some authors have preferred Type 1 pairings as they are convenient in certain applications. Hence, there are a lot of cryptographic protocols in the literature that have been designed only for Type 1 pairings.

The main way to implement Type 1 pairings is to use supersingular curves. There are traditionally two choices:

1. using fields of characteristic 2 or 3;
2. using supersingular elliptic curves (embedding degree 2) over GF( p ) where p is at least a 500-bit prime (and, nowadays, probably at least a 1500-bit prime).

The first option was by far the most efficient, but the recent discrete logarithm algorithms and computational records mean it must now be considered insecure. Hence we are stuck with the relatively slow choice of elliptic curves over GF( p ). It means that Type 1 pairings will now be much much slower than Type 3 pairings. It would be better in future to design protocols that do not require Type 1 pairings.

One technical remark:  One can implement Type 1 pairings using ordinary elliptic curves over any field.  One works in a subgroup that is not an eigenspace for Frobenius, and uses the trace map as a “distortion map” to ensure a non-degenerate pairing.  However this approach is also extremely inconvenient: there is no compact representation for elliptic curve points, and the pairing computation is also slow.  So the claim that Type 1 pairings are dead remains true.

— Steven Galbraith

Posted in Uncategorized | 2 Comments

## Algorithmic Number Theory Conference, 2014

The call for papers is now available for the ANTS conference.

This year the proceedings will be published in the open access London Mathematical Society Journal of Computational Mathematics. The submission deadline is February 20.

– Steven Galbraith

## ASIACRYPT 2013, Bangalore

What do you mean when you say

“…assuming there exists no algorithm that can solve the ECDLP in fewer than O(N^{1/2}) steps…”?

A quick survey of the people around me during Dan Bernstein and Tanja Lange’s “Non-Uniform Cracks in the Concrete” talk at ASIACRYPT suggested that most people were sure they knew what they mean—and they’re pretty sure they knew what anyone else who writes this kind of thing means, too.  Maybe that’s the problem.  To give a ridiculously oversimplified sketch of the idea: Everyone knows (or should know) that there exist faster algorithms, but they take longer to write down/precompute.  For example, the statement above is strictly false: for any group G of prime order N, given O(N^{2/3}) steps of precomputation, you can compute an algorithm that will solve DLP instances in G in O(N^{1/3}) steps.  On one hand, this renders some theorems in the literature false, because they make careless assumptions (which could, presumably, be easily fixed).  But on the other hand, you might think you still know what you mean—it all depends on your model of computation.  If you want to check, there’s now a choice: the 53-page full version (free) or the 20-page conference version (paywalled).  This paper caused a bit of a stir back when it first appeared, but a year and a half later the controversy has mostly cooled down; it was nice to be able to have a few civilised chats about it at a well-organised conference (with rather good food).

The last twelve months has seen a curious new wave of papers about scalar multiplication on elliptic curves using efficiently computable endomorphisms, following on from the Gallant–Lambert–Vanstone and Galbraith–Lin–Scott constructions.  This year’s ASIACRYPT had two papers on the subject.  Sorina Ionica presented her joint work with Aurore Guillevic, which gave a generalization of Patrick Longa and Francesco Sica’s four-dimensional GLV+GLS construction presented at ASIACYRPT last year, viewed on both elliptic curves and genus 2 curves (via the Weil restriction).  The other paper was mine; it deals with the problem of constructing twist-secure elliptic curves with two-dimensional scalar decompositions over the fastest finite fields (this is basically just the minimal modification of GLS required to get twist-security).

The rump session had a number of interesting results for curvists. Nadia Heninger presented joint work with Joppe Bos, Alex Halderman, Jonathan Moore, Michael Naehrig, and Eric Wustrow, which surveys how ECC is actually used in practice on the web today.  You’ll find a lot of interesting (and cute, and occasionally worrying) facts in the slides and the preprint.  We also saw some advertising for a range of projects involving Dan Bernstein and Tanja Lange: Elligator (encoding bitstrings into elliptic curve points, with Anna Krasnova and Mike Hamburg), MinimaLT (a fast replacement for TLS and TCP, with Michael Petullo, Xu Zhang, and Jon Solworth), and the safecurves page.

–Ben Smith

## Pairing 2013

The 6th InternationalConference on Pairing-Based Cryptography (Pairing 2013) took place in Beijing from November 22 to 24. The event started with two tutorials on friday the 22nd targeting students starting in the area of elliptic-curve and pairing-based cryptography.  More senior attendees used the time for an excursion to the Great Wall.

The main conference talks were held on saturday and sunday morning. As for ECC 2013 earlier this year, the major topic was the discrete-logarithm breakthroughs of this year. They were the subject of the invited talk “Computing discrete logarithms in finite fields of small characteristic” by Pierrick Gaudry and of two contributed talks (by Cécile Pierrot and by Gora Adj). A consequence of these breakthroughs is that most previously considered constructions of symmetric pairings are no longer considered secure. This fact was addressed by two papers (and corresponding talks, by Tadanori Teruya and Xusheng Zhang) that proposed new efficient constructions for symmetric pairings. Francisco Rodríguez-Henríquez in his invited talk focused on another research direction of pairing-based cryptography, namely efficient pairing-based-protocol implementations. The central point of his talk was to bring the “protocol community” and the “fast-implementation community” together to see more papers describing implementations of full pairing-based protocols in the future. The third invited talk was given by Xu Maozhi and described the state of the art in speeding up scalar multiplication on elliptic curves using efficiently computable endomorphisms. The sunday afternoon after the technical part of the conference was dedicated to a visit to the National Museum of Beijing, although some participants decided to rather enjoy the sunny weather for a visit to the Forbidden City.

— Peter Schwabe

## Elliptic Curve Cryptography in Practice

The recent paper Elliptic Curve Cryptography in Practice by Joppe W. Bos and J. Alex Halderman and Nadia Heninger and Jonathan Moore and Michael Naehrig and Eric Wustrow is well worth reading. The discovery in 2012 of a large number of RSA public keys with common factors showed that public key cryptography can go badly wrong in the real world. This paper reports on a thorough evaluation of ECC systems in the real world. Some of them, for example the Austrian e-ID citizen card, are found to have no weaknesses. However, serious issues are discovered with some other systems. In particular, the paper gives evidence that a theft of 59 bitcoins was achieved by an attacker exploiting duplicated nonces in ECDSA signatures. Further issues with bitcoin are discussed. The paper also reports some potentially serious bugs in TLS implementations in some commercially available devices. The paper does not reveal details of any companies or individuals affected by these issues.

— Steven Galbraith

## Pairing 2013 conference

The Pairing 2013 conference will take place in Beijing, China during November 22-24, 2013. The list of accepted papers is here. There are two interesting papers about the discrete logarithm problem in finite fields and the impact of recent results on the hardness of elliptic curve pairings.

— Steven Galbraith

## Recent work on pairing inversion

An important computational assumption in pairing-based cryptography is that it is hard to invert pairings. This problem has been studied for around 10 years, and it remains an active area of research. The purpose of this blog post is to survey recent work on the problem.

Recall that a pairing is a bilinear map $e : E[r] \times E[r] \to G_T \subseteq F_{q^k}^*$, where $E$ is an elliptic curve over a finite field $F_q$, $r$ divides $(q^k - 1)$, and $G_T$ is a group of order $r$. Usually we assume $r$ is prime. More generally, consider cyclic subgroups $G_1$ and $G_2$ of prime order $r$ of elliptic curves and a pairing $e : G_1 \times G_2 \to G_T$. Fixing a non-zero point $P \in G_1$, a pairing gives rise to a non-trivial group homomorphism $\phi : G_2 \to G_T$ as $\phi( Q ) = e( P, Q )$. Inverting a pairing is giving an efficiently computable group homomorphism from $G_T$ back to $G_2$ that is an inverse to $\phi$.

Most pairings $e(P,Q)$ on elliptic curves are computed by first computing some Miller function $f_{n,P}(Q)$ followed by a final exponentiation to some power $d \mid (q^k - 1)$. Pairing inversion (FAPI-1) is: Given a point $P \in G_1$ and a value $z \in G_T$ to find $Q \in G_2$ such that $e(P,Q) = z$. FAPI-2 is the problem with $P$ and $Q$ the other way around.

The first paper to consider group homomorphisms from $G_T$ to $G_1$ was:

• Eric R. Verheul, Evidence that XTR is more secure than supersingular elliptic curve cryptosystems, EUROCRYPT 2001.
• Eric R. Verheul, Evidence that XTR is more secure than supersingular elliptic curve cryptosystems, J. Crypt. 17, no 4 (2004) 277-296.

This paper comes from before pairing-based cryptography was a hot topic, so it does not mention pairings. Once pairing-based cryptography became established, several authors considered pairing inversion. For example, it is mentioned in the following survey paper.

• Antoine Joux, The Weil and Tate Pairings as Building Blocks for Public Key Cryptosystems, Algorithmic Number Theory, 5th International Symposium, ANTS-V, Springer LNCS 2369 (2002) 20-32.

In my (clearly biased) opinion, the story really starts with the following paper, which was not published until 2008 but the work was started at a workshop at the Fields institute in Toronto in 2006 where Florian and I both gave talks about pairings. Below I call this paper GHV.

• Steven D. Galbraith, Florian Hess, and Fre Vercauteren, Aspects of Pairing Inversion, IEEE Trans. Information Theory, Volume 54, Issue 12 (2008) 5719-5728.

This paper makes several observations.

1. A natural way to try to invert pairings is to first invert the final exponentiation by finding a $d$-th root of $z$, and then to invert the Miller function. A problem is that there are $d$ (which is exponentially large) possible $d$-th roots (as $d \mid (q^k - 1)$). What we need to do is to choose a $d$-th root that also lies in the set of images of the Miller function. The paper discusses the fact that there seems to be no way to efficiently recognise/classify the set of values of the Miller function. Hence, it is impractical in general to choose the “right” $d$-th root.

We quote from Section VII.A of the GHV paper:

“The main problem is that there are $d = (q^k - 1)/(3r)$ possible roots of $z$ and only one of them is likely to be of the correct form $y - \lambda x - \nu$ for some $(x, y) \in E(F_q )$. It is easy to compute random $d$-th roots of $z$, but it seems to be hard to select the correct root efficiently. For further discussion see [21].”

Here [21] is:

• Fre Vercauteren, The hidden root problem, Pairing 2008, Springer LNCS 5209 (2008) 89-99.

2. The paper then notes that for FAPI-1 and for certain pairings, a random $d$-th root might suffice. This is due to specific properties of the Tate pairing.

3. The main conclusion of the paper is that pairing inversion always seems to be hard, but sometimes it is the hardness of inverting the Miller function that provides the security, and sometimes it is the fact that there are too many possible $d$-th roots to check. Precisely, in Section VII.D of the GHV paper, Lemma 19 gives a lower bound on the total degree of a rational function $f(Q)^d$ corresponding to a group homomorphism from $G_2$ to $G_T$. This Lemma explains a fundamental obstruction to inverting pairings.

We now give more details about the problem of $d$-th roots. Typical pairing parameters have $r \approx q$ and $k > 2$, so that $d = (q^k - 1)/r$ is much bigger than $r$. Given an element $z \in G_T \subseteq F_{q^k}^*$, there are $d$ possible values $u \in F_{q^k}$ such that $u^d = z$. This is a huge (exponentially large) set of values. Finding a random root of the polynomial $x^d - z = 0$ in $F_{q^k}$ is easy. But imposing some kind of structure on the roots seems to be very hard.

As a result of these ideas, one line of research has been to consider situations where the final exponentiation is essentially trivial. In these cases pairing inversion reduces to Miller inversion. The first paper to consider this situation was:

• Steven D. Galbraith, Colm O hEigeartaigh and Caroline Sheedy, Simplified pairing computation and security implications, J. Mathematical Crypt, Vol. 1, No. 3 (2007) 267-281.

A recent paper in a similar direction is:

• Takakazu Satoh, On a Relation between the Ate Pairing and the Weil Pairing for Supersingular Elliptic Curves, eprint 2013/532.

Due to Lemma 19 of the GHV paper we know that the Miller function in this situation cannot have low degree. Hence, the problem of inverting Miller’s algorithm for these curves is still hard.

This reminds me I should mention several other papers by Satoh about pairing inversion:

• Takakazu Satoh, On polynomial interpolations related to Verheul homomorphisms, LMS J. Comput. Math 9 (2006) 135-158.
• Takakazu Satoh, On Pairing Inversion Problems, Pairing 2007, 317-328.
• Takakazu Satoh, Closed formulae for the Weil pairing inversion, Finite Fields and Their Applications 14(3) (2008) 743-765.

Recently Kanayama and Okamoto published a paper with a new approach to inverting pairings.

• Naoki Kanayama and Eiji Okamoto, Approach to Pairing Inversions Without Solving Miller Inversion, IEEE Transactions on Information Theory, 58 No. 2 (2012) 1248-1253.

Their paper employs a cute algebraic trick, motivated by papers on fault analysis of pairings, that certain combinations of Miller functions can be equal to a very simple rational function of low degree. The paper then notes that if one can correctly invert the final exponentiation for a selection of different pairing functions then one can then solve the pairing inversion problem by a very simple calculation. In other words, they have a strategy to avoid Miller inversion and hence bypass the restriction coming from Lemma 19 of the GHV paper.

In an attempt to make this precise the paper introduces a new problem EI (exponent inversion): Given $(d, \beta^d)$ to compute $\beta$. But here the troubles begin, as the paper is very poorly written. For a start, the EI problem in Definition 3 is not well-defined as a computational problem. The statement is (where the authors make clear that this is interesting for $d \mid (q^k - 1)$, and I have changed notation $(n,w)$ to $(d,z)$):

“For an unknown element $\beta \in F_{q^k}^*$ assume that an integer $d$ and the value of $z = \beta^d \in F_{q^k}^*$ are known. Then the EI is the problem of finding $\beta$ from $(d,z)$.”

The problem is that there are $d$ possible solutions when $d \mid (q^k - 1)$ and the solver has no way to know which $\beta$ the challenger is thinking of. Therefore, the success probability of the solver is clearly at most $1/d$, which is negligible. This is a computational problem that cannot be solved. It is astonishing that the authors and reviewers of this paper missed such a major error.

The most natural interpretation of what this problem should be is: Given $z$ find a $d$-th root of $z$ that lies in the image of the Miller functions. This issue is already implicit in the GHV paper. Sungwook Kim and Jung Hee Cheon (in the paper listed below) have noted this issue with the work of Kanayama and Okamoto and have formulated the problem more carefully.

However, Kanayama and Okamoto need more than just any possible value of the Miller function. They need to be able to find d-th roots of several field elements in a consistent way so that a precise algebraic relationship between values of Miller functions is achieved.

Let us consider these issues in closer detail. Restrict to the case where we have a pairing $e : G_1 \times G_2 \to G_T$, where all three groups are cyclic of prime order $r$. Fixing $P \in G_1$ and $z \in G_T$ there is a unique point $Q$ in $G_2$ such that $e( P, Q ) = z$. Hence, it is true that there exists a unique Miller function value $f_{n,P}(Q)$ which is a $d$-th root of $z$. So what is the problem? The problem is that there are lots of other points $Q \in E( F_{q^k} )$ and, for each one of them, $f_{n,P}(Q)$ is some random-looking field element in $F_{q^k}$. Precisely, there are around $q^k$ points $Q \in E( F_{q^k} )$ and so it is reasonable to expect “most” field elements in $F_{q^k}$ to be possible values of $f_{n,P}(Q)$. Hence, it is reasonable to expect that many of the possible $d$-th roots of $z$ are of the form $f_{n,P}(Q)$ for some $Q \in E( F_{q^k} )$. To narrow it down we need to impose the condition $Q \in G_2$, which is given by a number of conditions some of them being “nice” and some of them not. More precisely, $Q \in G_2$ usually means $Q$ has order $r$ and $Q$ is in a Frobenius eigenspace (sometimes also expressed as $Q$ being a point on a twist of $E$ over some subfield). The latter conditions are fairly nice algebraic conditions that might be handled, but the former condition (that $Q$ has order $r$) is pretty ugly to express algebraically.

My fundamental concern is that the EI problem cannot be well-defined without reference to the solution of pairing inversion. A precise formulation of the EI problem is really this:

Given $(P,d,z)$ compute the field element $\beta \in F_{q^k}^*$ such that $\beta^d = z$ and $\beta = f_{n,P}(Q)$ where $Q \in G_2$ is the solution to the pairing inversion problem $(P,z)$.

It seems unhelpful to reduce pairing inversion to a sub-problem EI that cannot be defined without reference to the solution to the pairing inversion problem. Unlike previous works, which reduce pairing inversion to truly “simpler” problems, the reasoning introduced by Kanayama and Okamoto seems, in my opinion, to be intrinsically circular. It is therefore not at all surprising that if one can solve EI then one can efficiently invert pairings. Hence, overall, I am not optimistic that this research avenue is going to lead to interesting insights into pairing inversion.

Nevertheless, there is some subsequent work.

• Sungwook Kim and Jung Hee Cheon, Fixed Argument Pairing Inversion on Elliptic Curves, eprint 2012/657.
• Seunghwan Chang and Hoon Hong and Eunjeong Lee and Hyang-Sook Lee, Pairing Inversion via Non-degenerate Auxiliary Pairings. eprint 2013/313 (to appear at the Pairing 2013 conference).

Both papers point out the serious flaw in the definition of EI introduced by Kanayama and Okamoto. Then the two papers make different contributions. Kim and Cheon show that the Tate and ate pairings are basically the same with respect to inversion. Chang, Hong, Lee and Lee make some changes to the details of the Kanayama-Okamoto method: While Kanayama and Okamoto required performing EI on several different pairing functions (each time using a potentially different formulation of the EI problem), the new paper unifies this into inverting a single “auxiliary pairing”. In other words, they invert an arbitrary pairing by reducing to inverting an optimal pairing.

None of these results are particularly surprising when one considers this from a group-theoretical view: any pairing gives a group homomorphism from $G_2 \to G_T$ and so inverting any pairing gives a homomorphism from $G_T \to G_2$. As shown by Verheul, as soon as one has a non-trivial group homomorphism from $G_T \to G_2$ then one can solve most of the problems one is interested in. Hence, it does not really matter which specific pairing function is being inverted.

In conclusion, I make three remarks:

• The pairing inversion problem is an important question, and it should be studied. But I am personally doubtful that the recent trend of work on the EI problem is going to lead to any useful results.
• I strongly advise all future researchers in this area to implement their algorithms before writing papers on the subject. By doing this you will notice any errors.
• The inversion problem for multilinear maps is also of interest. If one can invert a multilinear map then one can also break all the important cryptographic assumptions in that topic. The inversion problem in this case is essentially the problem of “refreshing” a level i ciphertext back to a level 1 ciphertext, which is a little bit like bootstrapping.

— Steven Galbraith