I am working on a cryptographic scheme and I need to rely on the following problem, which I have nicknamed the "Hybrid Decisional Bilinear Diffie Hellman (hDBDH)" problem:

Let $e: \mathbb G_1 \times \mathbb G_1 \rightarrow \mathbb G_T$ be an efficient bilinear pairing. Given the tuple $(g,g^x,e(g,g)^y,Q)$ as input, the problem is to decide whether $Q = e(g,g)^{xy}$

First, has this problem already been defined? Now, I want to prove that this problem is equivalent to the DBDH problem. I have the feeling that they are equivalent, but so far I only have that $DBDH \leq hDBDH$:

Proof: From a hDBDH solver, we can construct a DBDH solver in the following way:

Input: DBDH tuple = $(g, g^a, g^b, g^c, Q)$

Output: Return $hDBDH_{\mathsf{solver}}(g,g^a,e(g^b,g^c),Q)$

Now I want to prove the other direction. Any ideas of how a DBDH oracle could be used to solve the hDBDH problem? Any ideas of why it is not possible?

  • 2
    $\begingroup$ Why do you want to show the equivalence? Currently, you know that assuming bilinear DH is hard you are fine. $\endgroup$ – DrLecter Jan 8 '15 at 17:40
  • $\begingroup$ Now that you mention, it seems that I don't need to prove the equivalence, but I'm curious to know. My gut tells me that they are equivalent... $\endgroup$ – cygnusv Jan 8 '15 at 18:16
  • 1
    $\begingroup$ I've looked at it for a few minutes, and I wouldn't expect them to be equivalent. The information about $y$ in your problem lies only in the field. To get a DBDH relation related to $y$ seems to require some kind of pairing inversion, which is very hard to do. $\endgroup$ – K.G. Jan 8 '15 at 22:39
  • $\begingroup$ @DrLecter Actually, my intention is to base the security of the scheme on the Gap Bilinear Diffie Hellman (gap-BDH) problem, which is assumed to be hard, and consists on solving the Computational BDH using a Decisional BDH oracle. So, if the problem I posted on the question (hDBDH) were equivalent to the Decisional BDH then I'm done, since I can rely on the Gap BDH assumption, but if not then I will have a stronger assumption, since the available oracle (hDBDH) is stronger. $\endgroup$ – cygnusv Jan 9 '15 at 10:16
  • $\begingroup$ @cygnusv Ok, I see. But as K.G. already said it does not seem to be possible without pairing inversions and thus poly time equivalence does not seem to be possible. But your assumption thus seems to be strictly weaker than bilinear DH. $\endgroup$ – DrLecter Jan 9 '15 at 20:42

Your problem is stronger than DBDH problem. Because any oracle that response to your problem, can response to DBDH. I think that you must try to reduce this problem to DDH. This mean that input $(e(g,g),P=e(g,g)^x,R=e(g,g)^y,Q)$ and decide whether $Q=e(g,g)^{xy}$.


Given $(g,g^x,e(g,g)^y,Q)$, let $Q' = Q/e(g,g)^y$. Give $(g,g,g,g^x,Q')$ to the DBDH oracle. It will decides whether $Q'$ is random or equal to $e(g,g)^x$. If $Q'$ is random, guess $Q$ random, otherwise guess $e(g,g)^{xy}$.

So they are equivalent, I would reckon.


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.