3 ms·
What you want for asymmetric cryptography is "always hard to solve, easy to verify". Only a very small number of problems are believed to fall in this category,
by exged 6y ago
What you want for asymmetric cryptography is "always hard to solve, easy to verify". Only a very small number of problems are believed to fall in this category, including factoring and discrete logarithm.
It's far more common to have problems that are "sometimes easy to solve, sometimes hard to solve, easy to verify". That describes this problem as well as most NP-hard problems that with good heuristic solutions. The problem is those "sometimes easy to solve" cases break your cryptography!
- xmprt 6y agoHow do elliptical curves fit into this?
- pdpi 6y ago“Discrete logarithm” in this context alludes to the problem of calculating discrete logarithms for elliptic curves over finite fields.
- ColinWright 6y agoNot necessarily, the term "discrete logarithm" also alludes to calculating them in other contexts such as modulo p for p prime. It's not always on elliptic curves, and when I started in this field it was never on ECs. But your comment is largely true, this is a minor point ... I make it only for completeness, and for people who later find this comment.
- gautamcgoel 6y agoThe proper term is "elliptic curve", just FYI.
- tromp 6y agoElliptic curves are uniformly hard. If you could solve the elliptic curve discrete log problem (ECDLP) on any non-negligible fraction of inputs, then you'd break a lot of cryptography. In fact, the use of Pedersen commitments is based on nobody knowing the logarithm log(H) of a specific curve point H with respect to the standard base G. An efficient algorithm for solving ECDLP on a non-negligible fraction of inputs, could fail on input H, but one would eventually work on some random input r * H for a randomly picked scalar r, giving log(H) as log(r * H) / r.