Re: Collision resistant encryption scheme

Sergei wrote:
>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?
[...]
>No, again it is not a homework problem.

Ok, sorry to be paranoid. It just sounded like the kind of question
I can imagine assigning.

No, it is not possible for an IND-CPA scheme to have non-negligible
probability of this happening. Suppose we have a plaintext x such that
p = Pr[D_k'(E_k(x))=x] is large, where the probability is taken over the
choice of k,k' chosen independently at random. Then consider the following
find-then-guess adversary:
   A("find"):
   1. Let m_0 = x. Pick m_1 randomly.
   2. Output (m_0,m_1).

   A("guess", c):
   1. Pick k' randomly.
   2. If D_k'(c) = x, then output 0, else output 1.
In the find-then-guess setting, a referee takes the output (m_0,m_1)
of A("find"), chooses k randomly, chooses a bit b \in {0,1} randomly,
runs A("guess", E_k(x)), and checks whether A's output matches b; A wins
if it correctly guesses b, and loses otherwise.

Notice that A("guess", E_k(x)) outputs 1 with probability at least p.
In other words, the advantage of A at breaking E is at least p/2, which
is non-negligible. This contradicts the assumption that E is IND-CPA
secure.

So the IND-CPA condition is not sufficient to ensure that your bad case
cannot happen. In contrast, I believe the IND-CCA2 condition would suffice
(though it is not necessary).
Received on Tue Feb 7 21:00:11 2006