Topic: Quick elliptic curve security question (Read 1312 times)
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.
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.
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
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
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.
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?
Qi is a secp256k1 curve point (public key), ki is a private key, and G is the secp256k1 base point.
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?
Qi is a secp256k1 curve point (public key), ki is a private key, and G is the secp256k1 base point.
Jump to: