Re: Collision resistant encryption scheme

David Wagner wrote:
> 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.

   Either I don't understand this or "outputs 1" should be "outputs 0".

> 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).

--Mike Amling
"There's no wrong reason to give a monk rice."
Received on Tue Feb 7 21:00:13 2006