Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
