2
$\begingroup$

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?

$\endgroup$
6
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 20:42

4 Answers 4

1
$\begingroup$

This problem is defined as the Decisional Bilinear Problem (DBP) in Definition 3.7 on page 30 in the paper New Privacy-Preserving Architectures for Identity-/Attribute-based Encryption (2010) by Sze-Ming Chow.

$\endgroup$
1
1
$\begingroup$

Your problem is stronger than the DBDH problem because any oracle that responds to your query can also respond to DBDH. I think that you must try to reduce this problem to DDH. This means an input $(e(g,g),P=e(g,g)^x,R=e(g,g)^y,Q)$ and the decision whether $Q=e(g,g)^{xy}$.

$\endgroup$
1
$\begingroup$

This problems are not known to be equivalent, and cannot be shown to be equivalent generically (meaning, over arbitrary groups).

Here is an intuitive explanation: let $\mathbb{G}$ be a group equipped with a symmetric pairing, and $\mathbb{G}_\mathsf{T}$ be the target group. Observe that the following is perfectly possible (in the sense of not being ruled out by the definitions as far as we know): it could be that computational Diffie-Hellman (CDH) is easy over $\mathbb{G}$, yet decision hDBDH is hard over $(\mathbb{G}, \mathbb{G}_\mathsf{T})$.

This can be formalized by considering the generic symmetric bilinear group model (there are formal definitions, see e.g. this paper; it might be only for asymmetric groups, but specializing the definition to symmetric groups should be easy), and enhancing it with a CDH oracle over $\mathbb{G}$. In this model, it is relatively easy to prove that hDBDH remains hard over $(\mathbb{G},\mathbb{G}_\mathsf{T})$ (intuitively, that's because the CDH oracle doesn't help whatsoever, since we cannot "reverse the pairing").

In such a weird situation, it would be the case that hDBDH is secure, yet DBDH is insecure (given a CDH oracle in $\mathbb{G}$, it is straightforward to compute $e(g,g)^{a,b,c}$ by first computing $g^{abc}$ and then using a pairing).

What the above proves is that the equivalence cannot hold over arbitrary groups where hDBDH is conjectured to hold: any proof of equivalence must be somehow dependent of some specific properties of the underlying groups.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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