On Tuesday, November 12, 2002, at 10:22 AM, Tyler Durden wrote:
Well, my main point was that the fact that we are not certain about the difficulty in factorization is not necessarily due to our current lack of knowledge about the issue (and to be rectified one day as we look back and laugh at our previous naivety). In this case I was trying to reference Godel and the notions of unprovability...it is possible that factorization is inherently difficult and that the difficulty is a fact that is innately unprovable. (Yeah, I goofed on the larget prime issue...when I try to pull something out of pure memory my hit rate isn't very high....)No, this was a non-issue.
In a sense, this IS a restatement of his original point, but with an emphasis on the fact that our "faith" in the difficulty of factorization may be more than wishful thinking. This is an issue that a huge number of very smart mathematicians have tackled and see no real traction on. So our collective "intuition" on this issue may have reality on our side. (In which case we will never "look back and laugh".)
As for finding a process that has already proven to be innately difficult, I do find that an interesting notion. Certainly many such processes exist and have been identified...was factorization chosen because the encryption process used very little hardware (back when that mattered)?
Fact is, nobody has found a way to get what I'll call the "trapdoor/asymmetry" property with known NP-complete problems such as the Hamiltonian cycle problem (and a slew of NP-complete problems which are of course in a sense the same problem).
Why this may be the case is unknown (to me, at least). There are many books on complexity, NP-completeness, and algorithms. I like David Harel's "Algorithmics" a lot (he later re-issued it in a different form, but I favor the earlier version). Oded Goldreich has a new book on crypto...my copy is floating around somewhere here in my house, so I can't check it right now.
The point is that R, S, and A found factoring worked for the trapdoor/asymmetric (easy in one direction, very hard in the other) properties needed. Factoring has not been proved to be NP-complete.
There are problems even "harder" than NP-complete, of course.
Fame awaits anyone who finds a way to use the Hamiltonian cycle, polynomial satisfiability, etc., or one of the domino tiling (harder than NP-complete) classes of problems for crypto in general.
(There are famous examples of using Hamiltonian cycles for giving zero knowledge proofs. I wrote one up here for the list about 10 years ago...it may be findable by searching on the right keywords. But using one of the NP-complete problems to produce a ZK certificate is not the same as something like RSA encryption...though one would think there _must_ be a way to make it so....like I said, fame awaits someone who figures this out.)
Look, I have no idea what your background is, beyond the fact that you're new to the list and are obviously neither Edward Norton nor Brad Pitt. I suggest you take a look at some of the books on algorithms, especially the Harel book. Garey and Johnson is the classic on NP-completeness, but it's way too dry and technical to start out on.
I would also steer clear of issues of Godelian undecidability at this point. The types of "intractability" at issue here are a lot less "complex" in the hierarchy.
--Tim May
