Recent work on pairing inversion

A few days ago (April 10, 2019) Takakazu Satoh posted on eprint the paper Miller Inversion is Easy for the Reduced Tate Pairing on Trace Zero Supersingular Curves on eprint. I was delighted to hear from Takakazu Satoh, as I know him well but I had not heard from him for several years. Satoh’s papers have a distinctive look, since he uses his own typesetting package that he wrote in the 1980s before TeX was widely available.

Takakazu Satoh has been interested in pairing inversion for quite a while, and has published several papers on the topic, including “On Degrees of Polynomial Interpolations Related to Elliptic Curve Cryptography” (WCC 2005), “On Pairing Inversion Problems” (Pairing 2007), and “Closed formulae for the Weil pairing inversion” (Finite Fields and Their Applications 2008).

To recall basic definitions: Let $E$ be an ellptic curve over a field $\mathbb{F}_q$. Let $\ell$ be a large prime such that $\ell \mid \#E( \mathbb{F}_q )$. The embedding degree is the smallest integer $k$ such that $\ell \mid (q^k - 1).$ A pairing-friendly elliptic curve is one whose embedding degree is small, e.g., $2 \le k \le 30.$

The (reduced) Tate-Lichtenbaum pairing takes two points $P, Q \in E[ \ell ]$ and gives a value $e_\ell( P, Q ) \in \mathbb{F}_{q^k}$. A lot of researchers, including me and many of my friends, worked between 2000 and 2010 trying to compute pairings faster. The computation of the reduced Tate-Lichtenbaum pairing has two stages. First one computes a Miller function $f_{\ell, P}(Q)$. The function $f_{\ell, P}$ has divisor
$\ell(P) - (\ell P ) - (\ell -1)(\infty).$
Then one computes the final exponentiation, which is an exponentiation to the power $(q^k - 1)/\ell.$

It was discovered that, for many pairing-friendly curves, there was a more efficient way to compute the Miller function. Essentially instead of computing $f_{\ell, P}$ one can compute values like $f_{q, P}(Q)$, which is a simpler computation when $\ell > q$, which is usually the case. This observation was first made in a special case in a paper of Duursma and Lee from ASIACRYPT 2003. Further special cases were noted by Kwon (ACISP 2005) and Barreto, Galbraith, O hEigeartaigh and Scott (Designs, Codes and Cryptography, 2007). The situation was finally clarified by Granger, Hess, Oyono, Thériault and Vercauteren (“Ate Pairing on Hyperelliptic Curves”, EUROCRYPT 2007). The key idea is to work with Frobenius eigenspaces and change the pairing to $f_{q,Q}(P)$. I call this paper GHOTV below. Subsequently, Hess (“Pairing Lattices”, Pairing 2008) and Vercauteren (“Optimal pairings”, IEEE Trans. Information Theory 2010) showed how to use this idea most effectively in general pairing implementations.

One particular feature of the ate pairing introduced in GHOTV, is that the pairing computation only needs the first stage (Miller’s algorithm) and does not require a final exponentiation. This makes it a lot faster to compute. The ate pairing is not the exact same function as the reduced Tate-Lichtenbaum pairing, so one cannot use them interchangeably. But they are both bilinear maps and so a system can be implemented using the ate pairing and it all works fine.

In those days, we thought pairings would be useful for identity-based crypto and short signatures, and we were mostly trying to work with large embedding degrees like $k = 12$. So the case $k = 2$ was considered of relatively minor interest and was not studied much.

The computational assumptions underlying pairing-based crypto all required pairing inversion to be hard. Typically pairing inversion means: Given $z \in \mathbb{F}_{q^k}$ and a point $P \in E[\ell]$ to find $Q \in E[ \ell ]$ such that $e_\ell(P, Q) = z.$

It was quickly realised that there are two obstacles to pairing inversion: First it is necessary to invert the final exponentiation. Second one needs to invert the Miller function. It turned out that sometimes one or the other of these problems could be easy, but I know no situation for prime order groups where both are easy at the same time. For example, since the ate pairing does not require a final exponentiation, pairing inversion for the ate pairing is equivalent to Miller inversion (which seems to be hard in this case). In short, pairing inversion remains a hard computational problem, which is good news for pairing-based crypto. A good reference for these ideas is Galbraith, Hess, Vercauteren (“Aspects of Pairing Inversion”, IEEE Trans. Information Theory 2008).

Satoh’s recent paper explores the case $k = 2$. Work on discrete logs in finite fields (e.g., see these blog posts has caused some pairing researchers to become very conservative and reconsider choices such as $k = 2.$ When $k = 2$ we essentially have $\ell = q+1$ and the final exponentiation is to the power $(q^2-1)/(q+1) = q-1.$ The reduced Tate-Lichtenbaum pairing is
$f_{q+1, Q}(P)^{q-1}.$
Satoh uses Lemma 2 of GHOTV, that $f_{q, Q}(P) \in \mathbb{F}_{q^2}$ already has order $q+1$. This is the fact that the ate pairing does not require a final exponentiation. Let $v = f_{q+1, Q}(P)$ be the value computed by Miller’s algorithm, so that $v^{q-1}$ is the pairing value. Suppose one has the value $v$ (this is not normally the case, normally the attacker has $v^{q-1}$, from which there are $q-1$ possible values for $v$). Since $f_{q+1, Q}(P) = (x(P) - x(Q)) f_{q,Q}(P)$ (I am using different notation to Satoh here) it means that an attacker can get their hands on $P$ by raising $v$ to the power $q+1$, remembering that exponentiation to the power $q$ is linear, and hence solving a square-root to get $x(P)$. Hence, Satoh has shown that Miller inversion is easy in this case, but pairing inversion is still hard.

In fact, when $k = 2$ it would be quite natural to instead use the ate pairing for any crypto application. Now there is no final exponentiation. However Satoh’s attack does not work since his approach is precisely to kill off the “ate pairing” contribution to the Tate-Lichtenbaum pairing.

In short, there are two pairings one can use in embedding degree 2 and both seem to be hard to invert: the ate pairing has trivial final exponentiation but the Miller function seems hard to invert; the Tate-Lichtenbaum pairing has easy Miller inversion (as Satoh has just shown) but it seems hard to invert the final exponentiation.

I end with a comment about applications of pairings. As I mentioned, 15 years ago we thought that the “killer applications” for pairings were identity-based crypto and short signatures. Nowadays it seems pairings are most useful for short zero knowledge proofs. For example, Jens Groth’s pairing-based zk-SNARK (zero-knowledge succinct non-interactive argument of knowledge) is a key component of Zcash. As far as I can tell, the implementation in Zcash uses curves with embedding degree $k=12$ and does use the ate pairing.

— Steven Galbraith