How hard is the following q-Strong Diffie-Hellman problem?

Question

From On the $q$-Strong Diffie-Hellman Problem, the following problem is well-known to be hard.

For an randomly chosen element $x \in \mathbb{Z}_p$ and a random generator $g \in \mathbb{G}$, the exponent $q$-strong Diffie-Hellman Problem is, given $(g, g^x, g^{x^2}, \dots, g^{x^{q-1}}) \in \mathbb{G}^{q}$ to compute an element $g^{x^q} \in \mathbb{G}$.

Here, I want to ask how hard is the following problem:

For an randomly chosen element $x \in \mathbb{Z}_p$ and a random generator $g \in \mathbb{G}$, given $(g, g^x, g^{x^2}, \dots, g^{x^{q-1}}, g^{x^{q+1}}, g^{x^{q+2}}, \dots, g^{x^{2q-2}}) \in \mathbb{G}^{2q-2}$ to compute an element $g^{x^q} \in \mathbb{G}$.

Can it be reduced to other well-known Diffie-Hellman problem?

Answer 1

So I found that [1][2] shows that the hard assumption of the following problem holds in generic bilinear groups.

$\ell$-BDHE problem: given $(h, g, g^{\alpha}, g^{(\alpha^2)}, \dots, g^{(\alpha^\ell)}, g^{(\alpha^{\ell+2})}, \dots, g^{(\alpha^{2\ell})}) \in \mathbb{G}^{2\ell+1}$, output $e(g,h)^{(\alpha^{\ell+1})} \in \mathbb{G}_T$.

And it is trivial to see that $\ell$-BDHE can be reduced to the problem described in the question.

However, I am still wonder whether there is a better reduction without introducing bilinear pairing.

Update: It seems that [3] uses the same technique as the one in the above to prove the hardness.

[1] Hierarchical Identity Based Encryption with Constant Size Ciphertext

[2] Collusion Resistant Broadcast Encryption With Short Ciphertexts and Private Keys

[3] An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials