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).

$\endgroup$
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.

$\endgroup$
  • $\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$ – cygnusv Jan 8 '15 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$ – DrLecter Jan 8 '15 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$ – cygnusv Jan 8 '15 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$ – DrLecter Jan 8 '15 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.