Could someone point me to the paper/reference where the following variant of q-strong Bilinear Diffie-Hellman assumption was used?

Given $s \in \mathbb{Z}_p^*$ and $g, g^{\frac{1}{s}}, g^{s}, g^{s^2}, \ldots, g^{s^q}$ it is difficult to compute $g^{\frac{1}{s + c}}$ for $c \in \mathbb{Z}_p^*\setminus \{-s\}$.

Essentially, I am looking for the variant which has $g^{\frac{1}{s}}$ as a part of the public parameter.

  • $\begingroup$ What is $q-$strong? Is $q=p$? $\endgroup$ – kodlu Nov 1 '19 at 0:00
  • $\begingroup$ @kodlu Actually $q$ and $p$ are completely independent. $p$ is the order of the group and $q$ is the maximum exponent of the secret parameter $s$. $\endgroup$ – Mahdi Nov 1 '19 at 10:05

To the best of my knowledge, this hard assumption is introduced by Boneh and Boyen in this paper.

But I don't think so the assumption that you mention being hard, because $c=0$ is a simple solution for it. Then the element $g^{\frac{1}{s}}$ should not publish. Also, this assumption is not bilinear because the challenge is an element in the cyclic group of $\mathbb{G}$ and it is not $e(g,g)^{\frac{1}{\alpha+c}}$.

| improve this answer | |
  • $\begingroup$ There is no obvious attack when $c \neq 0$. As mentioned in the question: $c \in \mathbb{Z}_p^*\setminus \{-s\}$. I am having a hard time recollect the reference and whether it is hard to break $g^{\frac{1}{s + c}}$ or $e(g, g)^{\frac{1}{s + c}}$. $\endgroup$ – Shravan Nov 1 '19 at 15:59
  • $\begingroup$ @Shravan I am not sure about the proof of security of your claim, but by issuing $g^{\frac{1}{s}}$ we know the Diffie-Hellman Inversion (DHI) will break. Meanwhile, I think if you are convinced then you can introduce a new assumption. :) I found a new version of the mentioned paper, take a look at it. theory.stanford.edu/~dabo/pubs/papers/bbsigs.pdf $\endgroup$ – Mahdi Nov 1 '19 at 18:46

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.