4 ms·
That looks similar to factoring - in a sense that it is “hard to solve, easy to verify”. Could this be a new basis for asymmetric cryptography?
by mynegation 6y ago
That looks similar to factoring - in a sense that it is “hard to solve, easy to verify”. Could this be a new basis for asymmetric cryptography?
- metalliqaz 6y agoNot unless there is proof that any number has one and only one set of three cubes. I don't think that is true.
- vbezhenar 6y agoWhy do you need that property?
- exged 6y agoWhat 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.
- Kenji 6y agoAll problems in NP seem to be hard to solve and easy to verify. This is actually a really common property.
- metiscus 6y agoThis comment was dead and I couldn't understand why it was flagged as it didn't seem to violate any rules. Moreover in my experience I tend to agree that most NP problems do seem to have this property. Can someone who downvoted/flagged or is otherwise knowledgeable about the subject chime in and correct/ teach me something new?
- grzm 6y agoIt wasn't flagged. It looks like Kenji is banned. Their comments are [dead], not [flagged][dead].
- metiscus 6y agoThat's an interesting point. I looked at the comment history after you mentioned it, and saw that too. Thanks for replying!
- solveit 6y agoFwiw, NP includes P, so it's not true that problems in NP are hard to solve, easy to verify. You want to limit the statement to NP-complete problems. Even then, it's only true that solving the problems in full generality is (conjectured) hard. Individual instances can be easy, and in some applications, it may be the case that all/most problems that occur in practice are easy. Even SAT can be easy in practice, and modern SAT solvers solve instances with millions of variables every day.
- deleted 6y ago[deleted]
- bawolff 6y agoWhile all problems that are NP-hard (to be pedantic different from just NP) have that property, for crypto you want things to be uniformly hard (i.e. a randomly generated instance is hard). That's a much rarer property.