There's an IND-CPA SKE scheme-1 with $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ algorithms. Scheme-2 is defined as $(\mathsf{Gen}', \mathsf{Enc}', \mathsf{Dec}')$, where $$\begin{align*}\mathsf{Gen}' &= \mathsf{Gen}\\ \mathsf{Enc}'(k, m) &= \begin{cases} 0\|\mathsf{Enc}(k, m) & \text{if}\;m\ne k\\ 1\|k &\text{if}\; m=k \end{cases}\\ \mathsf{Dec}'(k, 0\|c) &= \mathsf{Dec}(k, c)\\ \mathsf{Dec}'(k, 1\|c) &= c \end{align*}$$

How do I go about proving that the scheme-2 is IND-CPA secure?

I'm also having trouble understanding if the adversary can guess the correct bit on a chosen plaintext pair given the ciphertext, given that when $m = k$, the ciphertext always starts with $1$, but for the scheme to be IND-CPA secure I know that the adversary should only be able to guess with negligible probability. What am I missing here?


1 Answer 1


A CPA on the second scheme is exactly the same thing as a CPA on the first one, provided that the attacker never calls the encryption oracle on a message which equals the key. But the latter can happen only with negligible probability, otherwise the first scheme would not be CPA-secure since it has the same key generation algorithm.

Thus, for any CPA attack against the second scheme, the exact same CPA attack will succeed with almost the same probability on the first scheme after accounting for the negligible possibility that the attack calls the encryption oracle on a message quich equals the key.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.