2
$\begingroup$

For the q-SDH problem, given the generator $g_1$ as a point on the elliptic curve, I can picture the $\beta g_1, \beta^2g_1, ..., \beta^qg_1$ since we can simply do the point adding $g_1$ multiple of $\beta$ times.

However, I cannot picture the point $\frac{1}{\beta+x}g_1$ (for some $x \in Z_p $). Is $\frac{1}{\beta+x}g_1$ a point on elliptic curve?

Moreover, in this q-SDH paper, there is a notation $g_1^{1/(x+c)}$. Is this $1/(x+c)$ equal a fraction $\frac{1}{x+c}$?

I cannot picture this $g_1^\frac{1}{x+c}$ either.

Improve this question
$\endgroup$
2
  • $\begingroup$ @kelaka Yes, I want to convert this to an EEC. Thank you for this clarification as pointing out that it is just taking the power as scalar. I cannot see the wood for the trees. $\endgroup$ – richard Sep 14 '20 at 2:48
  • $\begingroup$ I've converted those comments into an answer. If anything is not clear please comment under the answer. $\endgroup$ – kelalaka Sep 14 '20 at 9:48
2
$\begingroup$

The linked paper is not about Elliptic Curves which relies on additive groups. It is about the multiplicative groups. For both of them the discrete logarithm is defined. There are common notations that confuse people about them.

In the multiplicative version, the division is actually not a division like in the reals. It is the inverse in the group and sometimes written both way.

$$\frac{1}{\beta+x}g_1 = (\beta+x)^{-1}g_1$$

Similarly $$g_1^{1/(x+c)} = g_1^{(x+c)^{-1}}$$

If you want to convert the idea in to elliptic curve you need to replace the exponent with the elliptic curve scalar multiplication. We can see this from here

The power in the multiplicative group is actually a definition by

$$g^x := \underbrace{g \cdot g \cdots g}_{x-times}$$

and similarly the scalar multiplication in elliptic curve is also a definition by

$$ [x]P : = \underbrace{P + P + \cdots + P}_{x-times}$$

Both have faster calculation methods see the Wikipedia Pages.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thank you for this clarification. I think there is this confusion in some of the papers, and some people like me get confused when first reading them. $\endgroup$ – richard Sep 14 '20 at 14:23
  • $\begingroup$ In the beginning, one should get their base knowledge from well-written books. Then, they can start to judge the so-called papers, themself. $\endgroup$ – kelalaka Sep 14 '20 at 17:05

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.