From: Adam Back <aba@dcs.ex.ac.uk>
Date: Tue, 26 Nov 1996 15:21:06 -0800 (PST)
To: nobody@cypherpunks.ca
Subject: Re: Provably "Secure" Crypto
In-Reply-To: <199611261737.JAA14215@abraham.cs.berkeley.edu>
Message-ID: <199611251503.PAA00381@server.test.net>
MIME-Version: 1.0
Content-Type: text/plain



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

Adam
--
print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`