I have some troubles in understanding the q-SDH problem. The discrete logarithm problem states the following.

Given a point P of order on an elliptic curve and a point Q on the same curve. It is hard to find a such that $0 \leq a \leq p-1 $ and $Q = aP$.

The q-SDH problem states the following:

Let $g_1$ be a generator of the elliptic curve. Given $\beta \in \mathbb{Z}_q^*$ and q+1 tuple $(g_1, \beta g_1, \beta^2g_1, ..., \beta^qg_1)$ it is hard to find the SDH tuple $(x, \frac{1}{\beta+x}g_1 ) $

I do not understand why we have to find $\frac{1}{\beta+x}g_1$. Why is this hard? What is the underlying problem? Is the discrete log problem somewhere hidden? Why do we need x?

  • $\begingroup$ You may want to note that this is at most as hard as DLOG as if you can recover $\beta$ from $\beta g_1$ you can easily come up with $x=0$ such that $(0,\frac1\beta g_1)$. $\endgroup$
    – SEJPM
    Commented Jun 26, 2018 at 13:51
  • $\begingroup$ Yes, If I can recover $\beta$ I am able to compute the discrete logarithm. But why is $\beta$ in the denominator and what about x? $\endgroup$
    – null
    Commented Jun 26, 2018 at 14:38
  • 1
    $\begingroup$ In order to understand why $\beta$ is in the denominator, you need to understand the cryptosystems that motivated the q-SDH problem. The proof of security for those cryptosystems reduces to solving q-SDH. So in short $\beta$ is in the denominator because that's what those cryptosystems need. $\endgroup$
    – djao
    Commented Jun 26, 2018 at 23:26

1 Answer 1


The goal of the problem as you've described it is to find any $x$ along with $\frac{1}{\beta + x} g_1$.

There's no real reason it's in the denominator. That's just the definition of the problem. If you believe the assumption that this problem is hard, then you believe that finding those values (where $x, \beta$ are in the denominator) is hard to compute.

As for why it's hard: we don't know that it's hard, it's just an assumption (as one comment pointed out, it's definitely not harder than the discrete log problem).


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.