On safety of ECDLP used in Bitcoin

[aplistir]

I recently reviewed an interesting work about solving ECDLP  (that Bitcoin uses too.)

Most people think we will need a quantum computer(QC) for cracking ECC, but I am not so sure about it anymore. Conventional methods may prove to be good enough.

Bitcoin uses "Elliptic Curve Discrete Logarithm Problem" (ECDLP). But why is it called Discrete Logarithm Problem? It has nothing to do with DLP. Apparently someone thought that ECC would sound COOLER and SAFER if it is called DLP! And hence the DLP.

In DLP we try to solve x in equations like this: 6^x ≡ 8 mod 11. It is hard (with big numbers) because 6^x can get quite big, many times bigger than the (mod 11) and you will have to subtract 11 many many times.
eg. 6^7= 279936 =8 mod 11. That makes it hard to "guess" x and you will have to try different x values to find the correct one.

In the case of ECDLP we go from 1 to the private key and NEVER go over the order n of the curve.

So basically we try to solve x (x=private key) from  x*G=P , where G is point representing 1 in this system and P is the public key point, and x is always between 1 and n.

The possible weakness comes from the fact that we NEVER go over the order n of the curve. Unlike in DLP, which goes over the "order" (=11 in the example above) many many many times.

Because we always stay between 1 and n, we are not really dealing with DLP and some possibilities arise.

Odd or even. If we can reliably know if a point is odd or even, we can also break ECC.
One point about Finite fields is that they do NOT hide if a number is odd or even.
For example. Finite field of 11 points.

0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8...

If we ALWAYS stay in the first "round" of the field 0-10 (like we do in ECC) the numbers are as they are. 1,3,5,7,9 are odd, 2,4,6,8,10 are even.
So even if odd and even are not really defined inside finite fields, when we stay in the first "round", then odd and even work like they do in the real world.
If we go to the second "round" then odd and even would flip around. eg. odd number 13=13 mod 11=2 which "looks" like an even number. But we never go there, because we are actually not dealing with a DLP problem.  

Luckily for the safety of Bitcoin, Bitcoin uses coordinate points instead of numbers.
Finding out if a point is odd or even is hard. How can you define if a point (8,19) is odd or even? Can it be done?

If you divide the point by 2 it will of-course behave differently depending on if the point is odd or even, but since the result is symmetrical this wont lead very far.

But the conclusion was that they did not get it to work, and ECC is still safe. FOR NOW.

Wonder if this kind of work is the reason NSA stopped recommending ECC.

[DevilOper]

I recently reviewed an interesting work about solving ECDLP

Would you mind to share it to us?

It has nothing to do with DLP.

Yes, formally saying it hasn't. But it is called that way in the likeness and similarity.

...to solve x in equations ... you will have to subtract 11 many many times

And so you (may) do for EC points.

In the case of ECDLP we go from 1 to the private key and NEVER go over the order n of the curve.

Sure, you can go over n.
It depends on what algorithm you do use.

Finding out if a point is odd or even is hard. How can you define if a point (8,19) is odd or even? Can it be done?

If you divide the point by 2 ...

Scalar division (as well as multiplication) is not defined for EC math. So basically dividing by 2 has the same complexity as dividing by any other number x (and thus solving ECDLP).

[aplistir]

I recently reviewed an interesting work about solving ECDLP

Would you mind to share it to us?

Not my thing to share. Sorry. But It will probably be published sometime.

It has nothing to do with DLP.

Yes, formally saying it hasn't. But it is called that way in the likeness and similarity.

Quite strange, because there is very little similarity and in maths usually things are not named based on "feelings". Imho

...to solve x in equations ... you will have to subtract 11 many many times

And so you (may) do for EC points.

Not in the same sense. Yes, in adding points you do use mod, but the points themselves go only from 1 to n and never over n. (like they do in DLP)
 

In the case of ECDLP we go from 1 to the private key and NEVER go over the order n of the curve.

Sure, you can go over n.
It depends on what algorithm you do use.

Well. If your private key is bigger than n then your private key will be subtracted by n, but that is a different thing, since then your private key will actually be the smaller key...

Finding out if a point is odd or even is hard. How can you define if a point (8,19) is odd or even? Can it be done?
If you divide the point by 2 ...

Scalar division (as well as multiplication) is not defined for EC math. So basically dividing by 2 has the same complexity as dividing by any other number x (and thus solving ECDLP).

Here you are wrong. You certainly CAN multiple an ECC point with a number. That is what you do when you multiple a point with your private key to get the public key. Dividing with a number is also possible. Even though it is almost never mentioned anywhere. IT is possible. I can do it, and if you understand finite fields, so can you.  

What you cannot do is multiplying a point with a point, or dividing a point by a point. That is a completely different thing and is not defined in EC.

[DevilOper]

In the case of ECDLP we go from 1 to the private key and NEVER go over the order n of the curve.

Sure, you can go over n.
It depends on what algorithm you do use.

Well. If your private key is bigger than n then your private key will be subtracted by n, but that is a different thing, since then your private key will actually be the smaller key...

Keep in mind do not confuse EC order n, which is number of EC points, with modulo p.

...to solve x in equations ... you will have to subtract 11 many many times

And so you (may) do for EC points.

Not in the same sense. Yes, in adding points you do use mod, but the points themselves go only from 1 to n and never over n. (like they do in DLP)

Finding out if a point is odd or even is hard. How can you define if a point (8,19) is odd or even? Can it be done?
If you divide the point by 2 ...

Scalar division (as well as multiplication) is not defined for EC math. So basically dividing by 2 has the same complexity as dividing by any other number x (and thus solving ECDLP).

Here you are wrong. You certainly CAN multiple an ECC point with a number. That is what you do when you multiple a point with your private key to get the public key. Dividing with a number is also possible. Even though it is almost never mentioned anywhere. IT is possible. I can do it, and if you understand finite fields, so can you.  

What you cannot do is multiplying a point with a point, or dividing a point by a point. That is a completely different thing and is not defined in EC.

Strictly speaking, it is neither addition nor multiplication.
The operation defined over EC point group is called group law, I suggest you to learn some group theory basics before inventing your own interpretations.

It has nothing to do with DLP.

Yes, formally saying it hasn't. But it is called that way in the likeness and similarity.

Quite strange, because there is very little similarity and in maths usually things are not named based on "feelings". Imho

The similarity is quite obvious.
When you do exponentiation, you actually calculate X power of n as Y = X•X•....•X n times. So finding n is finding logarithm of Y.
When you do scalar multiplication by n on EC, you calculate it as Q = G•G•...•G n times. Where "•" - is a group law. Thus finding n is similarily named as finding (digital) logarithm of Q.