As for my background it's Optics/Physics/EE, and for the last 8 years worked with Erbium Doped Fiber Amplifiers, DWDM and SONET (ie, optical telecom). (Interestingly, my work in Telecom did once cause me to enter the only joint classified/unclassified NSA facility, as well as DARPA and DISA.) In case it matters, I've got a sack of papers and patents in that area, and was fairly well-known in those circles. After experiencing a couple of layoffs over the last year, I retreated to the relative sanctity and security of Wall Street, where I now work (and no, I'm not Pitt/Norton but my nome d'plume gives you a hint of the kind of company I work for, and it ain't insurance!)
The references are well-appreciated, but wrt the complexities of the algorithmic issues, I am more interested in knowing what the basic issues are (as well as what may not be known). At this stage, and for various reasons, I find that the potential social implications are what I am most interested in, but the "newbie" in me is trying to sort out what low-level details must be known in this context, while hopefully making an interesting point or two along the way.
As for "Godelian intractability", I didn't see that as necessarily an issue of complexity. Godel showed that given any formal system, there are statements that will certainly exist that are true but unprovable from within that system (mathematical "truth" is often confused with "provability"). Factorization may simply be one of those things that is difficult, but unprovably so, in which case it will forever and always be such. This may mean that we will end up living with factorization for a long time and yet never know if it's actually "difficult" or not.
Again, sorry to all for being a little chatty and clumsy at this point.
From: Tim May <[EMAIL PROTECTED]> To: [EMAIL PROTECTED] Subject: Re: The End of the Golden Age of Crypto Date: Tue, 12 Nov 2002 11:04:32 -0800On 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
_________________________________________________________________
The new MSN 8: advanced junk mail protection and 2 months FREE* http://join.msn.com/?page=features/junkmail
