(p-BDHI): p-Bilinear Diffie-Hellman inversion problem

Given $P,sP,s^2P,...,s^pP$. Find $e(P,P)^{\frac{1}{s}}$.

(DL): discrete logarithm problem

Given $P,sP$. Find $s$.

To break (p-BDHI), attacker needs to break DL.

I think the two assumptions have same-level hard problem.

No one is stronger than another. Is it right?


p-BDHI is clearly at least stronger than DL: if you can break the DL problem, you can recover $s$, and then compute $e(P,P)^{1/s}$ (if you are in a group where inversion can be computed efficiently, which I think is always the case in known pairing groups).

On the other end, it is not clear that breaking p-BDHI could allow breaking the discrete logarithm problem, as, intuitively, breaking it only involve computing a group element and does not directly give a way to recover an exponent (this is informal as it could still be that p-BDHI allows too break the discrete logarithm problem, it does just seem far from obvious).

  • $\begingroup$ I agree that they do not seem equivalent. But I do not buy your argument. Considering 1-BDHI, the obstacle is that you get an element in a different group. If you got s^-1 P instead and your oracle works for any P, you could break CDH (I think) which often allows you to break DL. $\endgroup$ – K.G. Jan 25 '17 at 21:14
  • $\begingroup$ @Geoffroy Couteau. I didn't get your idea why p-BDHI is stronger than DL. $\endgroup$ – myat Jan 26 '17 at 6:26

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.