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?

  • $\begingroup$ For the first part, the adversary can submit any two messages. So one (or both) could be repeated. $\endgroup$
    – mikeazo
    Commented Jul 15, 2014 at 16:17
  • $\begingroup$ This comment as well as the answers, etc might interest you. $\endgroup$
    – mikeazo
    Commented Jul 15, 2014 at 16:20
  • $\begingroup$ 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. $\endgroup$
    – orcking
    Commented Jul 15, 2014 at 16:57
  • $\begingroup$ I guess this is true for any deterministic symmetric encryption. $\endgroup$
    – orcking
    Commented Jul 15, 2014 at 17:17
  • 4
    $\begingroup$ "This is true for any deterministic symmetric encryption" -- you have just shown that an IND-CPA encryption method must be nondeterministic, $\endgroup$
    – poncho
    Commented Jul 15, 2014 at 17:22

1 Answer 1


First off, your definition is not IND-CPA: In the IND-CPA setting, the adversary has access to an encryption oracle. As you have already determined, no deterministic encryption scheme can be IND-CPA secure. I don't think IND-CPA is widely used for symmetric encryption though (although I might be wrong), semantic security might be a better option. For public key schemes, this is the same thing, but for symmetric schemes, it is not.

Semantic security informally says that you can't derive any information from a ciphertext about the underlying plaintext. Formally (from Katz and Lindell: Introduction to Modern Cryptography):

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.

  • $\begingroup$ I don't see why IND-CPA wouldn't be used for symmetric encryption, schemes like CBC already require a randomized IV. NaCL's authenticated symmetric encryption specifically advertises it's as meeting "standard notions of privacy and authenticity", which I understand to include IND-CPA: nacl.cr.yp.to/secretbox.html $\endgroup$ Commented Jul 24, 2014 at 7:20

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.