# Variants of Bilinear Diffie-Hellman Assumption

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.

• What is $q-$strong? Is $q=p$? – kodlu Nov 1 '19 at 0:00
• @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$. – Mahdi Nov 1 '19 at 10:05

## 1 Answer

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}}$$.

• 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}}$. – Shravan Nov 1 '19 at 15:59
• @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 – Mahdi Nov 1 '19 at 18:46