From: peter.allan@aeat.co.uk (Peter M Allan)
Date: Tue, 26 Nov 1996 04:18:32 -0800 (PST)
To: cypherpunks@toad.com
Subject: Re: Provably "Secure" Crypto
Message-ID: <9611261218.AA06559@clare.risley.aeat.co.uk>
MIME-Version: 1.0
Content-Type: text/plain




 Dana W. Albrecht originally wrote:

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

 > For a (non-cryptographic) example of a proof of the first sort --- that 
 > is, that "there exists no algorithm" --- consider the famous "Halting 
 > Problem" for Turing machines.  (I believe someone else has also 
 > mentioned this.)  There are many proofs such as this one, often related, 
 > though the Halting Problem itself is perhaps the most famous example.
 > 
 > For an (again, non-cryptographic) example of a proof of the second sort 
 > --- that is, that "any algorithm that solves a given problem requires a 
 > minimal running time" --- consider the proof that the "minimal" number 
 > of key comparisons in the worst case required to sort a random list of 
 > elements for which only an ordering relationship is known is O(nlog(n)).  
 > See Knuth, Volume 3, section 5.3.  For a simpler example, a standard 
 > "binary" search which requires O(log(n)) comparisons to find a given 
 > element in the worst case is provably the optimal algorithm for this 
 > task.

 Dana W. Albrecht (dwa@corsair.com) replies to
 The Deviant <deviant@pooh-corner.com> like this:
 
> Which part of this have you failed to understand?  Look in section 5.3.1
> of Volume 3 of "The Art of Computer Programming" by Knuth.  You will find
> there a rigorous proof that the "information theoretic lower bound" of
> an algorithm which sorts by comparison of keys is O(nlg(n)).


That is a bound on a _reliable_ algorithm.  A faster one is to shuffle
the elements and present it as sorted.  Lightning fast, but only with
low probability of correctness.  That is what we are up against in a key
search attack.  The other guy just might guess my 100 bit key first time,
millionth time or whatever - early enough anyway.

So to get a lower bound you have to show that a lucky guess cannot be
distinguished from an unlucky one - and if you do that without a one
time pad I take my hat off.

 
 -- Peter Allan    peter.allan@aeat.co.uk