Fixed argument pairing inversion on elliptic curves

Abstract

Let $E$ be an elliptic curve over a finite field ${\mathbb F}_q$ with a power of prime $q,\,r$ a prime dividing $\#E({\mathbb F}_q)$, and $k$ the smallest positive integer satisfying $r\,|\, q^k-1$, called embedding degree. Then a bilinear map $t: E({\mathbb F}_{q^k})[r] \times E({\mathbb F}_{q^k})/rE({\mathbb F}_{q^k}) \rightarrow {\mathbb F}_{q^k}^*$ is defined, called the Tate pairing. The Ate pairing and other variants are obtained by reducing the domain for each argument and raising it to some power. In this paper we consider the Fixed Argument Pairing Inversion (FAPI) problem for the Tate pairing and its variants. In 2012, considering FAPI for the Ate$_i$ pairing, Kanayama and Okamoto formulated the Exponentiation Inversion (EI) problem. However the definition gives a somewhat inaccurate description of the hardness of EI. We point out that the described EI can be easily solved, and hence give a repaired definition of EI so that the problem does contain the actual hardness in connection with the prescribed domain for given pairings. Next we show that inverting the Ate pairing (including other variants of the Tate pairing) defined on the smaller domain is neither easier nor harder than inverting the Tate pairing defined on the larger domain. This is interesting because the structure of the Ate pairing is so simple and good (that is, the Miller length is short, the solution domain is small and has an algebraic structure induced from the Frobenius map) that it looks more probable that attackers find further approach to solve FAPI for the Ate pairing, differently from the Tate pairing.