|
March 08, 2015, 10:04:31 PM |
|
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
|