I read the Wikipedia Page on ciphertext indistinguishability. Here it gives the following outline of the IND-CPA game:

  1. The challenger generates a key pair PK, SK based on some security parameter k (e.g., a key size in bits), and publishes PK to the adversary. The challenger retains SK.
  2. The adversary may perform a polynomially bounded number of encryptions or other operations.
  3. Eventually, the adversary submits two distinct chosen plaintexts $M_0,M_1$ to the challenger.
  4. The challenger selects a bit $b\in \{0, 1\}$ uniformly at random, and sends the challenge ciphertext $C = E(PK, M_b)$ back to the adversary.
  5. The adversary is free to perform any number of additional computations or encryptions.
  6. Finally, the adversary outputs a guess for the value of b.

From the first step, it seems that the challenger only generates a secret key once. That means that the same secret key is used throughout the entire game.

However, then it says this:

Although the adversary knows $M_0,M_1$ and PK, the probabilistic nature of E means that the encryption of $M_{b}$ will be only one of many valid ciphertexts, and therefore encrypting $M_0,M_1$ and comparing the resulting ciphertexts with the challenge ciphertext does not afford any non-negligible advantage to the adversary.

I think that 'the probabilistic nature of E' means that $E$ depends implicitly on the secret key. Then if the secret key is different every time, we could view $E$ as a probabilistic algorithm. However, we earlier saw that the secret key should be fixed for the entire game. Then how can $E$ be probabilistic?

I also looked at this question. The answer doesn't say anything about the probabilistic nature of $E$.

As a follow-up, I would also like to know if (and how) the decryption function $D$ is deterministic or probabilistic.

  • $\begingroup$ Of course it is. 1. Challenger: 𝐾𝐸,𝐾𝐷 = KG(security parameter). This is the first step and key was set. If the key is changing what is the advantage of asking queries? The probabilistic nature is due to the probabilistic encryption what we mostly achieve by nonce/IVs. ECB doesn't have one so non Ind-CPA, CBC and CTR has so Ind-CPA secure. $\endgroup$
    – kelalaka
    Oct 24, 2023 at 13:59
  • $\begingroup$ So this nonce/IVs is not part of the secret and/or public key? $\endgroup$
    – Riemann
    Oct 24, 2023 at 14:07
  • $\begingroup$ And does the decryption algorithm need to know the nonce/IVs that was used for encryption? $\endgroup$
    – Riemann
    Oct 24, 2023 at 14:09

1 Answer 1


Converting the comment into an answer;

In the first step, the Challenger selects uniform random keys using $Key\_Gen$ with the security parameter $\lambda$ applied. During the whole Ind-CPA game, the Challenger never changes the key. Changing the key is not a realistic game, since the attacker want to distinguish the current setup.

The probabilistic nature of the Encryption algorithm comes from the fact that the encryption may be probabilistic encryption as first appeared in;

  • Shafi Goldwasser and Silvio Micali, Probabilistic Encryption, Special issue of Journal of Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, April 1984

Well, for block ciphers ECB mode is not probabilistic, and therefore it is not Ind-CPA secure while CTR, CBC, and the other archive modes are Ind-CPA secure.

The probabilistic encryption is not achieved with a new key (and running a new key schedule), it is achieved with nonce/IV. This is not part of the game, it is part of the encryption scheme under investigation. If the encryption scheme fails, it will not be Ind-CPA secure.

In public key, the randomization has been achieved in different ways. In RSA, it is encoded into the padding, in the Paillier it is the $\lambda$, and in LWE noise $e$.

During the Ind-CPA game, the Challenger returns encryption of the asked values, this includes the IV/nonce.

During the Inc-CCAx games, the adversary may request the decryption of some ciphertext that must include the IV/nonce ( and may be tagged, too, if an AEAD scheme is used). The Challenger keep states, however they cannot know which IV/nonce is intended by the adversary.

Keep in mind that we consider the IV/nonce as part of the ciphertext. This is the reason we talk about the size increase on the ciphertext and this may include the authentication tag, too.

Of course, we prohibit them from querying the send $C$ to the adversary by the Challenger.

Decryption function 𝐷 is deterministic or probabilistic.

Decryption is, in general, deterministic since we want our message back correctly. Though, there are schemes that benefit this.


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.