From: nobody@cypherpunks.ca (John Anonymous MacDonald)
Date: Tue, 26 Nov 1996 09:43:14 -0800 (PST)
To: cypherpunks@toad.com
Subject: Re: Provably "Secure" Crypto
Message-ID: <199611261737.JAA14215@abraham.cs.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain



At 4:18 AM 11/26/1996, Peter M Allan wrote:
>> 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.

If the chance of a successful guess is absurdly low, the algorithm can
be considered to be secure.  It is quite unlikely that you will guess
a random 128-bit key.  Hence, you could have a secure algorithm in
which a successful guess can be distinguished from an unsuccessful
one.

diGriz