1
$\begingroup$

Let $s$ be a private key and $k=intAsScalar(s)$. Finding $s$ from $P_k=[k]G$ involves solving the Elliptic curves discrete logarithm problem.

But what if the same $k$ is also used for performing 1 or 2 millions of other scalar multiplications: in the current case, $random=[k]seed$, with the list of $(seed, random)$ pairs being public, is it still too hard to recover $k$ ?

$\endgroup$
10
  • $\begingroup$ The idea is a gambler generates $seed$, and after paying gets $random$ that determines the bet outcome. $\endgroup$ Commented Apr 28 at 14:33
  • $\begingroup$ I've edited your question to make it more formal in the sense of notation. What is not clear that the $seed$ is a point or a number? $\endgroup$
    – kelalaka
    Commented Apr 28 at 22:02
  • $\begingroup$ Let we have $P_k=[k]G$ now double both side, $[2]P_k=[2]([k]G) = [k]([2]G)$, can you see that we can get as may pairs from the discrete logarithms as we want. $\endgroup$
    – kelalaka
    Commented Apr 28 at 22:08
  • $\begingroup$ @kelalaka I fail to understand as there are no relation between seed and the public key. I forgot to write $Seed$ is the result of $HashToCurve(bet)$. $\endgroup$ Commented Apr 28 at 22:26
  • $\begingroup$ If the curve order is prime, all elements are generators, so we can generate as many pairs as we want. $\endgroup$
    – kelalaka
    Commented Apr 28 at 22:59

2 Answers 2

1
$\begingroup$

In the question's context, it's safe to reuse the same scalar when doing direct scalar multiplication on Koblitz (or other elliptic) curves.

More precisely: irrespective of how many $(\mathsf{seed},\mathsf{random})$ pairs we have with $\mathsf{random}=[k]\mathsf{seed}$ and $\mathsf{seed}$ on the curve (thus $\mathsf{random}$ on the curve), as long as all the $\mathsf{seed}$ are chosen independently of $k$ (including, randomly or pseudo-randomly), it's still about as hard to find $k$ as it is knowing only $P_k=[k]G$ where $G$ is the conventional generator of the elliptic curve.

Argument: if we had an algorithm $\mathcal A$ that with non-negligible probability and bearable effort finds $k$ from a list of $t$ random pairs $(\mathsf{seed},\mathsf{random})$, we could turn it into an algorithm that with the same non-negligible probability and bearably more effort finds $k$ from $P_k$, as follows:

  • Starting from an empty list of pairs, repeat $t$ times
    • Draw a random $k'$ in $[1,n)$ where $n$ is the group order
    • Compute $U=[k']G$, which is a randomly seeded curve point other than the point at infinity.
    • Compute $V=[k']P_k$.
    • Add to the list the pair $(U,V)$. Here it holds $V=[k']P_k=[k']([k]G)=[k'\,k]G=[k\,k']G=[k]([k']G)=[k]U$, and thus $(U,V)$ is a $(\mathsf{seed},\mathsf{random})$ pair as in the question, and indistinguishable from one obtained for random $\mathsf{seed}$ and $\mathsf{random}=[k]\mathsf{seed}$.
  • Apply the algorithm $\mathcal A$ to the list of $t$ pairs and output whatever it outputs.
$\endgroup$
1
$\begingroup$

There are multiple ways in which question can be dealt but I will choose to explain what scalar multiplication is because it will be more natural .

Short Answer: No

Explanation:

In pure terms of elliptic curve there is nothing like scalar multiplication only one operation is defined: Point Addition.

Procedure1 (P1): To add two points you must draw a line passing through those two points, eventually due to cube in equation, this would intersect the curve at a third point. Let say this third point is $R’(x, y)$. Since the curve s symmetric around $x-$axis there must also exist $R(x, -y)$ this $R$ is the result of point addition.

Sub-Procedure1 (S1): When we have to add a point to itself we cannot draw a simple line as there is no second point. In this case we draw a tangent to the curve at the point which would eventually meet the curve at another point. Again let this meet at $R’$ as in P1 we would know that the result of S1 would be $R(x, -y)$.

P1 is called point addition, calculating the point $R(x, -y)$ is called point negation and S1 is called point doubling which is a special case of P1.

What is scalar multiplication?

Scalar multiplication is nothing but performing P1 $k-1$ times, where $k$ is an integer being referred to as scalar.

There are various approaches but the most basic is double ad add method.

For example: Multiplying $k = 5$ on a $seed$, say $G$, involves following steps:

(Notation {procedure} on {operand} = {result})

  1. S1 on $G$ = $G’$
  2. S1 on $G’$ = $G”$
  3. P1 on $G”, G$ = $R$

Conclusion

Now coming to your question if you keep $k$ same but $seed$ varies would it be easy to calculate $k$?

The answer is no because scalar multiplication has no real meaning in terms of elliptic curve, what you do is to add a point to itself that scalar($-1$) times. It doesn’t matter what point on curve you are adding to itself a fixed number of times. If calculating the fixed number is hard for one point it must be equally hard for another.

This is why if it is hard to calculate that scalar for $G_1$ it must be equally hard to calculate it for any other $G_2$ or seed.

$\endgroup$
3
  • $\begingroup$ I was thinking nonce should be used. $\endgroup$ Commented Apr 30 at 12:28
  • 1
    $\begingroup$ The answer's "no" is ambiguous, and wrong if reading only the question's title. The answer's conclusion is correct for the question in the body, but the proof can be made more mathematically convincing. Independently: in cryptography, we don't actually "draw a line" for point addition; we apply formulas to this effect, in a different field. Nitpick; scalar multiplication by $k$ is performing algorithm P1 (including S1) $k-1$ (not $k$) times to add $P$ starting from $P$. Suggestion: Scalar multiplication $[k]P$ is equivalent to adding $k$ terms $P$ using algorithm P1 or it's variant S1. $\endgroup$
    – fgrieu
    Commented Apr 30 at 13:48
  • $\begingroup$ Yes proof can be made more mathematically convincing but I didn’t see any point of using too much math for the question. Independently: I used draw because it was easier to understand and was important to introduce basics. Nitpick: Thanks for pointing out. Suggestion: Thanks, will include. $\endgroup$
    – madhurkant
    Commented Apr 30 at 14:50

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.