1
$\begingroup$

Let $e: \mathbb G_1 \times \mathbb G_1 \rightarrow \mathbb G_T$ be an efficient bilinear pairing. Note that the pairing is symmetric (i.e., Type 1).

The problem is, given $g \in \mathbb G_1$ and $e(g,g)^a \in \mathbb G_T$, for an unknown $a$, to compute $X_1, X_2 \in \mathbb G_1$ such that $e(X_1,X_2) = e(g,g)^a$

Is this a hard problem? My feeling is that it is not and there should be an easy way to solve it.

Update 1: I have found a related problem that it is said to be hard:

The Pairing Pre-Image Problem (PPIP) in $\mathbb G_1, \mathbb G_T$ such that $\mathbb G_1 = <g>, |\mathbb G_1| = |\mathbb G_T | = p$ with pairing $e : \mathbb G_1 \times \mathbb G_1 \rightarrow \mathbb G_T$ is defined as follows: On input a tuple $(g, Z) \in \mathbb G_1 \times$ $\mathbb G_T$, output $X \in \mathbb G_1$ such that $e(X, g) = Z$.

According to this paper: CDH in $\mathbb G_1 \leq$ PPIP $\leq$ DL $\in \mathbb G_T$

The problem I am asking is not harder than PPIP since I could use PPIP to solve my problem : simply run the PPIP solver on $(g,Z)$, take output $X$, and return $X_1 = X, X_2 = g$. That is, PPIP is my problem but requiring that $X_2=g$.

Still, I think that there should be an easy way to solve my problem. Any ideas?

Update 2: Thanks to the comment from @DrLecter, now I know that the original problem I stated was exactly the Generalized Pairing Inversion (GPI) problem, which seems to be hard. That makes me reformulate the question to my real problem (see this question).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

What you present is a generalized version of the so called fixed-argument pairing inversion (FAPI) problem. The FAPI problem is given an element $z\in G_T$ and an element $h\in G$ to compute $f\in G$ such that $e(h,f)=z$.

Note, that FAPI is implied by the computational Diffie Hellman problem: Given $(g,g^a,g^b)\in G^3$, call the FAPI oracle with $z\gets e(g^a,g^b)$ and $h\gets g$ and clearly we have that $f=g^{ab}$ which is a solution to the CDHP in $G$.

The generalized (GPI) version is that when given $z\in G_T$ to compute $h,f\in G$ such that $e(h,f)=z$. Obviously, GPI implies FAPI.

Pairing inversion is AFAIK generally believed to be hard. You may study this paper or this blog post for more details.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the links! Now I know my problem is the Generalised Pairing Inversion. One comment: I think that FAPI implies GPI, and not the other way around, since FAPI fixes ones of the arguments to the pairing. $\endgroup$ Commented Jan 8, 2015 at 9:55
  • $\begingroup$ @gygnusv Nope, you get an GPI instance $z$, sample one element $h$ from $G$ randomly and call the FAPI oracle (which returns $f$) and output $z,h,f$. $\endgroup$ Commented Jan 8, 2015 at 10:00
  • $\begingroup$ OK, I think it is a problem of nomenclature. I thought that if you use an oracle P to solve problem Q, then "P implies Q". I have seen lots of references following this nomenclature, but also the other way around... At least, we agree on that GPI is not harder than FAPI, right? $\endgroup$ Commented Jan 8, 2015 at 10:09
  • $\begingroup$ @cygnusv Yes, GPI is not harder than FAPI. If $GPI \implies FAPI$, then the contraposition is $\neg FAPI \implies \neg GPI$. So if $FAPI$ does not hold if follows that $GPI$ does not hold (if you have an oracle for FAPI you can solve GPI). $\endgroup$ Commented Jan 8, 2015 at 10:36

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.