Quick elliptic curve security question

[Peter R]

Question for the experts out there:

Let

    Q1 = k1 * G

and
  
    Q2 = (k1 + n) * G.

If Q1, Q2, G, and n are known, is it still difficult to determine k1?

What about if

    Q2 = n * k1 * G?


Q_i is a secp256k1 curve point (public key), k_i is a private key, and G is the secp256k1 base point.

[Nikinger]

If Q1, Q2, G, and n are known, is it still difficult to determine k1?

• Yes, knowing Q1, Q2, G, n is not sufficient to calculate k1 easyly because there is no known fast method doing a point division.
• Knowing Q1, Q2, G, k1 is not sufficient to calculate n easyly
• Knowing Q1, n, G is sufficient to calculate Q2 easyly (Q2 = Q1 + G*n)

   Q2 = n * k1 * G?

If one of n, k1, G is not known, you can't recover it's value easyly because it would involve point division. If Q2 is unknown, you can calculate it easyly just by multiplying.

[andytoshi]

Hey Peter,

k1 is indeed hidden. You can argue this by reduction ... suppose you had an algorithm A which given (G, (n + k)G, n, kG) could spit out k. Then if I wanted to solve a discrete log challenge (G, kG), I'd just choose my own n, compute (n + k)G as nG + kG, and give all these values to the algorithm A. It'd spit out k which is my answer.

I'm glossing over the distributions of secret values (all should be i.i.d. uniformly random over their domains) here.

You can also argue the reverse direction, which shows that your problem is exactly as hard as discrete log.

Edit: Given (G, nkG, n, kG) the same argument works. (Get a DL challenge kG, multiply by your own n, solve for k if it's really so simple, and you've solved DL.)

Andrew

[gmaxwell]

Do take care that because your one more discrete log problem is secure doesn't mean that any larger system you embed it into is secure.

[Peter R]

Thanks for the responses Andrew, Greg and Nikinger.  I was quite certain the answer was "yes, it's still secure" (e.g., I suppose this is why split-key vanity address generation works), but Andrew's reduction argument makes this rock solid.