Hacker News Reader

Comment by Ono-Sendai | Hacker News Reader

Since the paper claims to give an algorithm for solving an NP-hard problem, e.g. it's a constructive proof, not just an existence proof, then presumably the author should be able to reduce some other problems to this one (2-Maxsat) and solve them as a demonstration.

View on HN

I'd be more inclined to believe their P=NP claim if they used it to grab all of Satoshi's bitcoins. That should be the first order of business for anyone finding an efficient algorithm for the ECDLP (Elliptic Curve Discrete Log Problem), as implied by their constructive proof.

Only works if they have been moved. Addresses start out as hashes of ECC keys, not the keys themselves

The problem of "find a series of bytes that is a valid transaction sending these bitcoins to me" is an NP problem. When you can solve arbitrary "find satisfying input" problems, details like "the public key is hashed" don't matter. It's adjusting what it means to be valid, not changing the nature of the problem to be out of scope of "find satisfying input".

Besides, Satoshi's coins are P2PK (Pay to Public Key), not P2PKH (Pay to Public Key Hash), so the point is moot.

A proof that P=NP doesn't necessarily mean that NP-hard problems are solvable in any practical sense. The time complexity claimed by the paper, O(n^2 * m^3), grows quickly, and the constant factors may be high. In fact, I'd go so far as to say it's very unlikely that a P=NP proof would make any difference in practice, since SAT solvers are so good for real-world problems.

(I'm leaving aside the fact that cryptocurrency theft is a crime that most people would be disinclined to commit, as well as the extraordinarily high likelihood that this proof is incorrect.)

> cryptocurrency theft is a crime

If you know the private key, then you own the coins.

At least that's the whole basis that crypto currency is founded on...

Except most legal systems don’t see it that way. When you say this, they hear “if you have a copy of the key to a house/car/etc, then you also own it”. Cryptocurrency theft is a crime by the basic definitions of the legal system.

That is not how the law works. It's equivalent to knowing your bank account number and routing number and making an unauthorized transaction.

That's just not how keys work. If someone finds the key to my house and uses it to open the door and take something, it's still theft.

The decision problem for ECDLP is not known to be NP-complete, in fact it's likely not NP-complete but rather NP-hard and therefore proving that P = NP would not provide any insight into finding a polynomial time solution for it.

Having an efficient algorithm for SAT (or any NP complete problem) immediately gives you an efficient algorithm for ALL problems in NP, including ECDLP.

It is not known if the decision problem for ECDLP is in NP, in fact it's likely not in NP.

NP-hard does not mean NP, it means a problem that is ATLEAST as hard as NP. NP-hard problems that are in NP are known as NP-Complete.

Finally ECDLP itself is not a decision problem, so even if the decision problem for ECDLP is in NP and P = NP, that does not mean that ECDLP itself has a polynomial time solution.

NP, NP-Complete, NP-Hard etc... only refer to decision problems, not to general purpose computations.

The decision problem for ECDLP

  { (Curve_spec, P, x) : x is a prefix of the discrete log of point P on the specified elliptic curve }

is trivially in NP.

I think you're mixing up quite a lot of things here. For one, apart from the impreciseness of your statement of the decision problem, it wouldn't be a decision problem for ECDLP but rather for the more general discrete logarithm problem (DLP). ECDLP is assumed to be in a higher complexity class than DLP.

With that said, even if the decision problem for ECDLP is in NP and P = NP, that does not mean that a solution to ECDLP is in P.

A decision problem as used to define the classes NP and P is of the form: does there exist an x such that F(x) = 1, where F is a P-time computable function.

If you can solve that problem in P-time then you can also solve the functional version (find an x for which F(x) = 1) in P-time simply by setting each bit to a value for which the decision problem is satisfiable, one by one.

> ECDLP is assumed to be in a higher complexity class than DLP.

No, it's not. All instances of DLP, including ECDLP, are just asking for an x such that b^x = a, as Wikpedia will tell you [1]. They only differ in the choice of group, but exponentiation within the group is assumed to be an efficient operation.

> With that said, even if the decision problem for ECDLP is in NP, that does not mean that a solution to ECDLP is in P.

It trivially does. You simply start with an empty prefix x and extend it 1 bit at a time by repeatedly asking if (Curve_spec, P, x0) is in the language. If so you continue with x0, if not you continue with x1.

[1] https://en.wikipedia.org/wiki/Discrete_logarithm

There is an upper bound in the number of private keys available even if it isn't an issue in practice.

You can target anyone's wallet in O(1) time, no proofs needed :^)

If I read the paper correctly the 2-MAXSAT problem is usually referred to as MAX-2-SAT

https://en.wikipedia.org/wiki/2-satisfiability#Maximum-2-sat...

Such a reduction is known to exist, but that doesn't mean it's necessarily easy to implement. It would suffice to find some large instances of 2-maxsat and solve those.

Only if they're (i) conjectured hard instances (ii) for which we can verify that a given solution is indeed optimal. Which in many cases is itself is a Gödel prize worthy task.

Technically (and depending on the problem, practically), giving large instances isn't a good test.

For some problems, you can pick easy instances (even if large), or there can be ways to go backwards and generate an instance you know the answer to (prime factorization comes to mind).

I believe that there's problems where it's difficult to even find a hard instance, it's just also difficult to prove that no difficult instances exist either. SAT might be one if I remember correctly, solvers actually do really well.

>I believe that there's problems where it's difficult to even find a hard instance

Sure, but encoding the factorization of a large prime into 2-MAXSAT would necessarily imply constructing a hard instance of the latter. It follows that it isn't any more difficult to construct a hard instance of any NP-hard problem than it is to encode a more easily constructible problem into the same.

As for verifying the solution, that would be different, since it is not necessarily easy to verify the solution to a problem in OptP. I had not considered that part. But you probably don't have to go as far as importing integer factorization.

> Sure, but encoding the factorization of a large prime into 2-MAXSAT would necessarily imply constructing a hard instance of the latter.

That should work if you pick something like one of the unsolved RSA challenges or something.

The RSA challenges are very easy to generate - just generate large random numbers, check if they pass a primality test like Miller-Rabin (this doesn't take long even with a naive implementation). Then multiply two of those that do pass the test (distinct ones!), and you're done.

Sure, but presumably they're difficult to solve. I'm saying that if they can _solve_ an unsolved one using this algorithm, that would certainly be compelling.

Right - to elaborate, my point was that since:

1- it's easy to generate RSA-like challenges for factoring, a product of two large primes.

2- it's easy to turn these RSA-like challenges into instances of the SAT problem (the canonical NP-complete problem).

3- SAT problems can be reduced to any NP-complete problem.

4- these reductions are known, because the typical proof of NP-completeness is to provide a reduction from another NP-complete problem, which will ultimately end up with SAT if you follow the chain for long enough.

... it follows that it's not too hard to generate hard instances of any NP-complete problem, assuming that factoring itself is a hard problem.

Reply on news.ycombinator.com