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

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

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

You are commenting using your 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