Re: Collision resistant encryption scheme

silentser@gmail.com wrote:
> 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

I don't think a PRP-ideal construction would gurantee that though. The
likely hood can be low but over all permutations there are (2^w - 1)!
possible perms that collide (e.g. share a co-domain value for the same
domain input).

The likelyhood of having no collisions is basically nill though over
all keys. It may be possible to generate a useful sized subset of
permutations which have no collisions but I seriously doubt any modern
block cipher sports that "feature" over all keys.

Why do you need such a design?

Tom
Received on Tue Feb 7 21:00:06 2006