Hacker News new | past | comments | ask | show | jobs | submit login

Neither of which helps with elliptic curve cryptography.



Pollard's rho algorithm can be applied to not just numbers but any cyclic group, which secp256k1 (the elliptic curve used by Bitcoin) is.


the problem of finding discrete logarithms is the same problem as breaking elliptic curve cryptography.


Technically, while the two problems share the same name, the one on elliptic curves is matematically different from the one over finite fields modulo a prime number.


I politely don’t understand this. It’s taught in cryptography 101 that breaking ecc is just solving the discrete logarithm problem and there’s a ton of online articles about how to break ecc if you’ve solved the discrete logarithm problem (not that anyone has).


There's a family of discrete logarithm problems, one for each representation of a group. (Where I mean "representation" in the usual sense, not the precise mathematical one. It's an important distinction because the secp256k1 group, for instance, is isomorphic to all cyclic groups of the same order, but the discrete logarithm problem on secp256k1 is harder than the additive group on Z/<order of secp256k1>Z, because the isomorphism is computationally intractable.) So there isn't simply one monolithic discrete logarithm problem.


It's indeed called the discrete logarithm problem both in the case of finite fields modulo some number and elliptic curves modulo a number. In the first case, you are reversing an exponentiation, so you're indeed computing a logarithm. But in the case of elliptic curves you're not dealing with exponentiation, you're instead reversing the multiplication of a curve element (i. e. a point) by a scalar. The two problems (and the way you solve them) look similar in the end, and I think this is why we ended up using the same name. But, if we nitpick, those are different operations and so the two problems are different, despite the similarities.

Note for cryptographers/matematicians: I know that "reversing" isn't the correct term here, so you could accuse me of the same sin I'm calling out in my previous comment. But it makes the explanation shorter while still conveying the correct meaning in the end.




Consider applying for YC's Summer 2025 batch! Applications are open till May 13

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: