3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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♦ Jun 26 '18 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 Jun 26 '18 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 Jun 26 '18 at 23:26
2
$\begingroup$

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).

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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