Re: Collision resistant encryption scheme

Paul Rubin wrote:
> Mike Amling <nospam@foobaz.com> writes:
> > > Actually all shift cyphers (Caesar cyphers) have this feature. Ie,
> > > C(R,M)=M+R mod(2^blocklength) have the property that for every R
> > > (the key) C(R,M)!= C(R',M)
> >
> > Same for XOR, C(R,M)=M^R, a standard implementation of a One-Time Pad.
>
> Neither of these schemes is IND-CPA secure. There are trivial known
> plaintext attacks against both.

For IND-CPA security the following modification of one-time pad cipher
can be used: E_k(x) = (a, x xor f_k(a)). For that cipher the
probability of collision is indeed negligible.

> Real-world ciphers tend not to be designed against related key
> attacks. They also sometimes have properties like the DES key
> complementation property. Can the application be broken only be a
> real, full collision, or is it bad enough if some relationship between
> keys can be pushed through to a relationship between ciphertexts?
>
> Anyway, the usual remedy is to use hash function outputs as keys.

I know that such collisions are inevitable so I just want to make them
improbable: I'm looking for a sufficient condition that would
guarantee the negligible probability of such collision for any
plaintext.
A relationship between keys, actually, wont hurt. I only care about
full collision.
Received on Tue Feb 7 21:00:10 2006