4
$\begingroup$

where $g$ is a group element in bilinear group $\mathbb{G}$. I understand it is very similar to the conventional DBDH problem, but $g^{1/b}$ is also known, possibly making it easier? Does anyone know the answer or suggest some material for reference? Thanks.

$\endgroup$
  • $\begingroup$ The DBDH is decisional, so maybe you are asking if it is hard to decide if a given $Q = e(g,g)^{abc}$ or random. $\endgroup$ – cygnusv Feb 6 '15 at 10:52
  • $\begingroup$ @cygnusv Yes, thanks a lot. I have revised the question. $\endgroup$ – Jingwei Feb 6 '15 at 11:34
  • $\begingroup$ Also, distinguishing $e(g,g)^{ac/b}$ is actually equivalent to distinguish $e(g,g)^{abc}$. You just have to switch $g^b$ with $g^{1/b}$, so maybe you can just drop $e(g,g)^{ac/b}$ from the question, for simplicity. $\endgroup$ – cygnusv Feb 6 '15 at 11:44
  • $\begingroup$ @cygnusv Thanks, I just want to ask whether the DBDH assumption still holds, if $g^{1/b}$ is additionally known. $\endgroup$ – Jingwei Feb 6 '15 at 11:52
8
$\begingroup$

Your problem seems to be at least as hard as the 2-weak Bilinear Diffie-Hellman Inversion Problem (2-wBDHI problem):

Given $g, g^x, g^{x^2}, g^y \in \mathbb G$, and $T \in \mathbb G_T$ to determine whether or not $T = e(g,g)^{x^3 y}$.

Proof: We first need to define an equivalent version of your problem, where we take some generator $h$ so $g = h^b$. Your original problem is to take input $(g,g^a, g^b, g^c, g^{1/b}, Q)$ and decide whether $Q = e(g,g)^{abc}$ or not. After substituting $g = h^b$, we have that the new problem is to take $(h^b, h^{ab}, h^{b^2}, h^{bc}, h, Q)$ and decide if $Q = e(h,h)^{b^3 ac}$.

So, assume you have a solver $S$ for the new problem. Then we can solve the 2-wDBDHI problem as follows:

  1. Input to 2-wDBDHI is a tuple $(g,g^x,g^{x^2},g^y,T)$.
  2. Sample a random element $z \in \mathbb Z_q^*$.
  3. Call $S$ with input $(g^x,g^y,g^{x^2},g^{x^2 z},g,T^z)$, which will output Yes when $T^z= e(g,g)^{x^3 y z}$, and No otherwise.
  4. Output the result from the last step.

Recall that solver $S$ takes input $(h^b, h^{ab}, h^{b^2}, h^{bc}, h, Q)$ and determines whether the following equation holds: \begin{align}Q = e(h,h)^{b^3 ac}\end{align} Take the substitutions $h=g$, $a = y/x$, $b = x$, $c = xz$, and $Q = T^z$, so: \begin{align}T^z = e(g,g)^{x^3 (y/x) xz} = e(g,g)^{x^3 yz}\end{align} It is clear that when this equation holds, then $T = e(g,g)^{x^3 y}$ holds too, and vice versa, so this algorithm is a solver for the 2-wBDHI problem.

According to the ECRYPT II report - D.MAYA.6 Final Report on Main Computational Assumptions in Cryptography, the best known algorithm for 2-wBDHI is to solve DLP in $\mathbb G$, so you can say that your problem is hard.

Note: My previous answer didn't answer your question, since the strong-DDH is not hard when using pairing groups... I was merely stating that your problem is at least as hard as an easy problem (duh!)

$\endgroup$
  • $\begingroup$ It is really a good answer. Thanks so much for your suggested report. $\endgroup$ – Jingwei Feb 6 '15 at 13:38
  • $\begingroup$ @Jingwei I have just updated the answer, since it was wrong. Now I think it is OK. $\endgroup$ – cygnusv Feb 6 '15 at 16:15
  • 1
    $\begingroup$ This answer is incorrect. To see why, consider a solver that simply computes the requisite d.logs. and then trivially decides the correct answer. Now modify the solver so that if its third and fourth inputs are identical, it instead flips a coin to determine its answer. Since they are almost never identical, this is still a good solver. Apply your reduction to this modified solver. This results in an algorithm that flips a coin, which is not a good solver for 2-wBDHI. Ergo, your reduction does not work. Perhaps it can be fixed. $\endgroup$ – K.G. May 21 '15 at 13:59
  • $\begingroup$ @cygnusv report link does not work $\endgroup$ – curious May 21 '15 at 14:07
  • 1
    $\begingroup$ That seems like it might work, cygnusv. You need to verify that, given the distribution of the input tuple, the distribution of the tuple you produce is the same as the solver expects. When T is random, your Q should be random. When T is real, so should Q be. $\endgroup$ – K.G. May 21 '15 at 20:49

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.