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



At 7:03 AM 11/25/1996, Adam Back wrote:
>deGriz (sic) wrote:
>> At 4:18 AM 11/26/1996, Peter M Allan wrote:
>> >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.  
>
>Agreed.  However you _can_ instantly verify once you have guessed.
>This makes the algorithm cryptographically secure, but _not_ perfectly
>secure as is the case with a OTP with a truly random pad.
>
>I think we agree, it is just a distinction in definitions of terms.

We are in agreement.  I would add, for the benefit of others, that it
is a good idea to keep in mind that the focus of our work is to build
physical systems which are secure.  For instance, we determine the
primality of numbers using probabilistic methods.  This is not
"perfect" in the sense that a OTP is, but it is certainly good enough
to bet somebody else's life on it.  ;-)

OTPs, for that matter, are engineering problems, too.  It is difficult
to find a random number generator in which we have complete
confidence.  If we buy a board from somebody, how do we know there
isn't a back door?  How do we know they did a good job?  Many
commercially available hardware random number generators are of
shockingly poor quality.  Caveat emptor.

diGriz