Re: The End of the Golden Age of Crypto

[Tyler Durden]

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

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

From: Tim May <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED]
Subject: Re: The End of the Golden Age of Crypto
Date: Tue, 12 Nov 2002 09:48:27 -0800

On Tuesday, November 12, 2002, at 07:13  AM, Tyler Durden wrote:

This may be true, but the conclusion that might easily be reached isn't. According to the number theorists (particularly post-Godel), factorization may easily be one of those things that...
1) Is inherently dificult
2) and the fact that it is inherently difficult is unprovable.

Yeah, a restatement of his point. It would be nice to have crypto systems based on at least problems which have been shown to be NP-complete.

This may mean that not only is there no "hard evidence", there may never be. This being the case (and it most probably is), then we may always have to live with this uncertainty....and ain't that life?

(I believe that the non-existence of the "last" prime number is also unprovable.)

I don't follow you here. The Greeks knew the proof that there is no largest prime, a proof which can be written down in a paragraph. (If one believes in excluded middle proofs as opposed to constructivist proofs, which in this context is a reasonable belief.)



--Tim May

_________________________________________________________________
Add photos to your messages with MSN 8. Get 2 months FREE*. http://join.msn.com/?page=features/featuredemail