# Strong Diffie Hellman in bilinear groups

The $$n$$-strong Diffie Hellman assumption state that given the subset $$\{g, g^s,\cdots,g^{s^n}\} \subseteq \mathbb{G}$$ in a cyclic group $$\mathbb{G}$$ of prime order $$p$$, a PPT algorithm cannot output $$g^{\frac{1}{s+\alpha}}$$ for any $$\alpha \in \mathbb{F}_p$$ except with negligible probability.

Does it somehow imply that no PPT algorithm can output an irreducible polynomial $$f(X)\in \mathbb{F}_p[X]$$ and the element $$g^{\frac{1}{f(s)}}$$? Or does that entail a strictly stronger assumption?

• I guess it is weaker than $n$-SDH asumption. The $g^{f(s)}$ can be expressed by the subset {${g^{s^0},...,g^{s^n}}$}, thus the problem is: Given the $g^{f(s)}$, no PPT algorithm can output $g^{1/f(s)}$. Sep 13 at 12:35
• Actually, I meant for any irreducible $f(X)$ rather than a prescribed $f(X)$. Since linear polynomials are an example of irreducible polynomials, I think this would be a stronger assumption that $n$-SDH. But I am not sure whether it can be reduced to the $n$-SDH Sep 13 at 16:08

If I understand your quantifies (for any given irreducible $$f(x)$$, there does not exist such an algorithm), then it’s a stronger assumption and one that is unlikely to be true as $$n$$ grows. First, note that if we write $$x_i$$ for $$g^{s_i}$$ then the degree (at most) $$n$$ polynomial $$\sum c_is^i$$ gives $$g^{\sum c_is^i}=\prod x_i^{c_i}$$ as easily calculable.

Now for any polynomial $$h(x)$$ of degree at most $$n$$ with no roots mod $$p$$, let $$f(x)$$ be a solution to $$f(x)h(x)\equiv 1\pmod {p, x^p-x}$$ Then $$g^{1/f(s)}=g^{h(s)}$$ and so can be calculated easily. As $$n$$ grows the number of possible $$h(x)$$ grows and soon we will be guaranteed that one of our $$f(x)$$ is irreducible.

• Good point. I should have specified that the degree of $f(X)$ is bounded. What if we add the condition that $\deg(f(X))≤n$ or is polynomial in $n$? Also, the PPT algorithm won't be able to compute the coefficients of $f(X)$ since it's degree would be $\geq p-\deg(h(X))$. Sep 14 at 0:32