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?


1 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.