Re: Provably "Secure" Crypto
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
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`
participants (2)
-
Adam Back -
nobody＠cypherpunks.ca