Hacker News Reader

Comment by mynegation | Hacker News Reader

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?

View on HN

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!

How do elliptical curves fit into this?

Elliptic 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.

The proper term is "elliptic curve", just FYI.

“Discrete logarithm” in this context alludes to the problem of calculating discrete logarithms for elliptic curves over finite fields.

Not 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.

Not unless there is proof that any number has one and only one set of three cubes. I don't think that is true.

Why do you need that property?

All problems in NP seem to be hard to solve and easy to verify. This is actually a really common property.

While 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.

This 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?

Fwiw, 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.

It wasn't flagged. It looks like Kenji is banned. Their comments are [dead], not [flagged][dead].

That's an interesting point. I looked at the comment history after you mentioned it, and saw that too. Thanks for replying!

Reply on news.ycombinator.com