# Ciphertext indistinguishability (IND-CPA) for symmetric cryptography

My understanding are these steps are necessary for symmetric cryptography to be IND-CPA:

1. The adversary submits two distinct $M_0$, $M_1$ plain-texts to the challenger.
2. The challenger selects one of them at random and encrypts it with the symmetric key and gives cipher-text C.
3. The adversary has to guess which message was encrypted based on C with a probability greater than 1/2 for the cipher-text to be distinguishable.

If the adversary wants to play the game again can he do $M_0$ and $M_2$? Or do they have to be new plain-texts?

Also I have an encryption algorithm that I am trying to apply IND-CPA test on it. How do I go about finding the probability mathematically, any hints or steps should I take?

• For the first part, the adversary can submit any two messages. So one (or both) could be repeated. Commented Jul 15, 2014 at 16:17
• This comment as well as the answers, etc might interest you. Commented Jul 15, 2014 at 16:20
• Thanks, for the first part, what if I do M0,M1 then M0,M2 then M1,M2 . This way I would figure out which plain-texts were encrypted. Commented Jul 15, 2014 at 16:57
• I guess this is true for any deterministic symmetric encryption. Commented Jul 15, 2014 at 17:17
• "This is true for any deterministic symmetric encryption" -- you have just shown that an IND-CPA encryption method must be nondeterministic, Commented Jul 15, 2014 at 17:22

A private-key encryption scheme is semantically secure if for every PPT (= probabilitsitc polynomial-time) algorithm $\mathcal A$ there exists a PPT algorithm $\mathcal A'$ such that for all efficiently sampleable distributions $X = (X_1, \dots)$ and for all polynomial-time computeable functions $f$ and $h$, there exists a negligible function $negl$ such that $\vert Pr[\mathcal A (1^n, Enc(k, m), h(m)) = f(m)] - Pr[\mathcal A'(1^n, h(m)) = f(m)]\vert \leq negl(n)$, where $m$ is chosen according to distribution $X_n$ and the probabilities are taken over the choice of $m$ and the key $k$, and any random coins used by $\mathcal A$, $\mathcal A'$ and the encryption process.
If you look closely, you see that $\mathcal A$ has access to an encryption of $m$ where $\mathcal A'$ does not. The requirement is that this gives $\mathcal A$ no advantage, because for any function $f(m)$, the two do just as well.
Unfortunately, proving this kind of security is rather ugly, which is why (in public key cryptography, where both are the same) the IND-CPA notion is usually used. How to prove security for your scheme depends on your scheme, without further details, it will be hard for anyone to help you with that. The approach is generally to show something along the lines of "If an adversary $\mathcal A$ can break my system, I can construct an algorithm $\mathcal B$ (which calls up $\mathcal A$) that breaks problem $X$, but problem $X$ is considered hard". For example, ElGamal reduces to the decisional Diffie-Hellman problem this way, which is related to (and a stronger assumption than) the Discrete Log problem.