Re: Provably "Secure" Crypto (was: IPG Algorithm Broken!)

[The Deviant <deviant@pooh-corner.com>]

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