"Such cryptography is based on faith, much like tea-leaf reading. We have absolutely no hard mathematical evidence that factoring is any harder than multiplying or taking square roots, or of the existence of easily computed functions with computationally intractable inverses"
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.
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.)
As for arguments concerning "short cuts" that occur from Ramanujan-like flashes of human insite, you have now wandered into some very difficult waters...I suspect that some of the AI folks would argue that your pi example is the result of much deeper algorithmic processes that occur in the brain, and that we can't observe yet. SOme (such as Penrose) would disagree, and argue that human creativity leverages very deep connections between the brain and the quantum world...this would always be beyond even very powerful silicon (though non-Quantum) machines.
From: Mike Duvos <[EMAIL PROTECTED]> To: [EMAIL PROTECTED] Subject: The End of the Golden Age of Crypto Date: Sun, 10 Nov 2002 16:45:21 -0800 (PST)Tim May wrote: > So, in these four areas real code is being generated. These get > mentioned on the list...one just has to notice them, and remember. > My main point is to refute the defeatism that often is clothed in the > language of cynicism and ennui. Much is still being done. It isn't > getting the attention of the press, which is probably a good > thing. (They have moved on to other topics. And nobody is being > threatened with jail, so crypto is no longer as edgy as it was when PRZ > was facing prosecution, when crypto exports were illegal, when Clipper > was in the news.) Crypto export has been decriminalized, and cryptanalysis programs are now illegal "circumvention devices" under the DMCA. I am hard pressed to view this as an improvement. If DECSS and Advanced eBook Processor produce an exhaltation of prosecutors bent on putting the authors in jail, I doubt we'll be hearing if someone invents DE-SSH or DE-AES. This greatly reduces my faith in the robustness of ciphers, particularly those that have been around to have their tires kicked for a decade or two. Break a code, go to jail. Even a silly code, like XOR. The 90's were the Golden Age of public access to crypto, largely driven by public key cryptography and the need for people to do secure communication over the Internet without physically meeting to exchange keys. The 00's will be the Golden Age of something else. Superintelligent AI perhaps. > Even Rivest, Shamir, and Adleman knew essentially no number > theory. One of them got the idea that maybe the difficulty of factoring > could be used as the core for what they were doing...I have also heard > that the idea came from another on the staff at MIT, but I won't get > into that right now. Then they "crammed" and learned what they needed > to learn about stuff like Euler's totient function, methods for finding > primes, etc. It was enough. Such cryptography is based on faith, much like tea-leaf reading. We have absolutely no hard mathematical evidence that factoring is any harder than multiplying or taking square roots, or of the existence of easily computed functions with computationally intractable inverses. We infer the existence of such things solely from the observation that the human mind has not yet produced solutions to such problems. If they were really easy, we conjecture, someone would have figured out the answer by now. Well, maybe. Evidence is begining to emerge which suggests that such a view may be fundamentally flawed, and just as most humans cannot multiply 100 digit numbers in their heads, so there are countless wonderful and simple formulas whose derivation from scratch is so complex that no one will ever find them simply by trying to derive them directly. Are hard problems hard because they have no simple solutions, or simply because their simple solutions lie slightly beyond the range of our current deductive radar? Are they hard, or are we simply bad programmers? Compelling evidence for the latter explanation is beginning to mass. Consider, for instance, the following simple power series (Bailey,Borwein,Plouffe) for Pi as a sum of inverse powers of 16. Multiply by a power of 16 and take the fractional part, and you can compute hexadecimal digits of Pi starting anywhere. Pi = sum[0,infinity] [4/(8n+1) - 2/(8n+4) - 1/(8n+5) - 1/(8n+6)] * 1/16^n Now it's pretty easy to verify that this does indeed compute Pi, with a symbolic integrator, a pile of scratch paper, and much cancellation. Going in the other direction, however, is virtually impossible, unless you already know precisely what you are looking for. Given the task of locating a rapidly convergent series for Pi in inverse powers of 16, suitable for calculating arbitrary hexidecimal digits of Pi, one might very well bumble around calculating forever, without stumbling across it. The derivation is simply too difficult, and exists in a forest of equally difficult derivations which don't produce Pi. So how, one might inquire, did we come into possession of this handy formula? Well, it wasn't derived in a conventional sense. Instead, a computer program, PSLQ, a polynomial time numerically stable algorithm for finding relationships between real numbers, was used to examine all such formulas, and see if any of them produced Pi. One did. It is likely our ability to generate algorithms by a direct "grep" of all formulas having a specific form, and perhaps in the near future, all formulas under a certain length, will uncover many simple but difficult to directly derive formulas that do useful things. It is this ability which poses the greatest threat to cryptography in the current decade, as we find to our surprise that many of the things we thought were hard, like factorization, were merely obtuse, like trying to multiply big numbers in your head. I think there's a very good chance that by the end of the decade, we will all be laughing hysterically at how we ever could have thought public key cryptography and block ciphers were secure, and "crypto" will mean exchanging CD-ROM's of your one-time-pad at midnight in a fast food restaurant parking lot. There is a third reason I think the fat lady has sung for crypto as we know it, in addition to the prosecutions for cryptanalysis of commercial products, and our blind faith in the computational intractability of everything historically unsolved. Selling crypto to the masses has always been based on the envelope metaphor. Just as you wouldn't use postcards for all your private communications, so you wouldn't send them in cleartext across the public Internet. Encryption is to digital messages, what envelopes are to paper ones. It should be noted that envelopes only work if everyone uses them. If everyone who doesn't have anything to hide uses postcards, and people who have things to hide use envelopes, then it's pretty easy to know where to apply the rubber hose. Envelopes only work to hide secrets if they are mixed in with millions of indistinguishable envelopes which do not contain secrets. Unfortunately, we have had a complete failure in the area of making encryption the standard for all data transmitted over public networks. Ten years after the start of the crypto movement, virtually no one has encryption software, and virtually no one encrypts their email. People who want to encrypt their email can't, because the people they are sending it to don't have the software to read it. People have demonstrated that they will not choose privacy if it results in even the slightest amount of inconvenience, which means that encrypted messages still stand out like a sore thumb in the data stream. It also means that were there any movement towards the ubiquitous use of crypto, the government could disintentivize it instantly, by simply dangling some free gift or convenience before the masses. After all, these are people who eagerly sign up for Safeway club cards. "Delete PGP, Win a Free Turkey," "Cleartext, the anti-Osama," or whatever. So, ten years after the founding of Cypherpunks, we reach the following crossroads. 1. Export all the crypto you want, but breaking even stupid crypto will get you prosecuted. 2. Our faith in the mathematical underpinnings of some crypto may be fundamentally misplaced. 3. The public won't use crypto anyway, so why do we even bother? Anything encrypted stands out in the bitstream like a giant red flag with a smiling Saddam on it. Yes, folks. It's the End of the Golden Age of Crypto. Time to move on to the Golden Age of something else. -- Mike Duvos $ PGP 2.6 Public Key available $ [EMAIL PROTECTED] $ via Finger $
_________________________________________________________________
Protect your PC - get McAfee.com VirusScan Online http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963
