Re: Collision resistant encryption scheme

"silentser@gmail.com" <silentser@gmail.com> writes:

>Hi, Is it possible for a secure encryption scheme (I mean IND security)
>to have such a plaintext x, that for randomly chosen keys k, k' the
>probability that D_k'(E_k(x))=x is non-negligible with respect to the
>length of the key? I think that in general it is possible, but I need a
>scheme that is resistant to such collisions. Probably there are exist
>sufficient conditions that can guarantee that such plaintext does not
>exist and the scheme is collision resistant?
>Sergei

This is probably impossible. Most encryption schemes have a finite block
size, and they take all elements in that block to elements in the same
block size. If that mapping is more or less "random" then there is a high
probability that for any two keys, there will be x such that x maps to the
same encrypted text. In fact, it was the non-mapping of elements into
themselves ever on the enigma machines that was one of the keys to breaking
the cypher. Ie, such an encryption scheme is weaker than one which doe have
such mappings.

Ie, if you found such a scheme, so that for no two keys any collisions
existed, you would have a weak encryption scheme.
Received on Tue Feb 7 21:00:07 2006