-----BEGIN PGP SIGNED MESSAGE----- On Mon, 25 Nov 1996, Dana W. Albrecht wrote:
Our friend Don Woods seems to have inadvertently sparked what could be a useful and serious discussion regarding "provably secure cryptography."
Not to be confused with the usual "unbreakable" snake oil we see peddled so often, I refer to systems for which rigorous mathematical proof that "there are no shortcuts" exists. To my knowledge, no such systems, with the exception of a real one-time pad, exist today. However, I also
As I have argued many times, that is correct. OTP, with real random numbers, and no-reusage, etc, etc, is the only "perfect" cryptosystem, and even it has its problems (like key exchange, for instance).
Rigorous proofs of the non-existence of an algorithm are not new. Neither are rigorous proofs that any algorithm which can solve a given problem requires a minimal running time. Or, in an even stronger sense,
Hrmmm... I seem to see a problem (namely Moore's first law) in assigning anything a "minimal running time". Perhaps "minimal instruction count" would be more suited to your example. Because if you're talking about time, it essentially boils down to "the longer something takes the less time it takes".
that a particular known algorithm for a given problem is indeed a (provably) optimal algorithm for that problem.
Never happen. It just won't. As a rule, there's _always_ a faster way.
Turning once again to cryptography, there is presumably an "optimal" algorithm for factoring a "general" number in the "worst" case. Of
Ok, now I have to pose a question: If cryptographers actually beleive this, why continue to search for a faster one.
course, known algorithms for factorization seem to regularly improve and no one has even suggested that any current algorithm is (provably) the "optimal" algorithm. Worse case bounds on running time for currently known algorithms can certainly be produced, but no one currently knows if these are the best algorithms.
Again I say, there's _always_ a faster way.
However, just as one can say, "How do you know that tomorrow some brilliant mathematician will not produce a polynomial time factorization algorithm?" one can also say, "How do you know that tomorrow some brilliant mathematician will not provide a rigorous proof that all factorization algorithms --- in the worse case --- require some specified minimal running time?"
Again I say, it just won't happen. It can't, and I can't prove that for the same reasons that it can't happen.
Obviously, discussion on this topic is unrelated to such security problems as implementation mistakes, fault analysis, outright theft of keys, etc. I hope that I've been careful to explain what I mean by "provably secure" and that it's not interpreted to include these types of attacks.
Yes, I must commend you on your amazing tact in asking this incredebly irrevelant question.
Comments, anyone?
Dana W. Albrecht dwa@corsair.com
--Deviant PGP KeyID = E820F015 Fingerprint = 3D6AAB628E3DFAA9 F7D35736ABC56D39 Unix is the worst operating system; except for all others. -- Berry Kercheval -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQEVAwUBMppmkTCdEh3oIPAVAQF50wf+J2Gz8P7stqKD4sesCHmWWYNZX1vf2zU0 nBQhkDABuE2fjJnNpUijc13Vls5K6owkL4LeWEHW2mvwCU1tqseRJSUm8m8ckEh1 M/CBu7lJplFj2QYcK+vFvg1+dOpuZycvhROKb0VO6zbB3PTLi9Cc4iJpwIhqDyDG zCurg4Ccc1cW7I7lTSfeSlRVVqF5FfCTP0GmqS1lcr+NWSPdHIqgZRGHq5n2+nUU y16ksaIKJMGJ8bzCFb8Q02ii7JUJF3JyYbgsGRWQMHxN+W0mx2E3Crh3+q4ieK/R ehGnKh4ZjOPY4RRDLQJfuLTvBBccdoKvSimyKHRoybZYIjTra9jYHQ== =9qjq -----END PGP SIGNATURE-----