I am currently going through past finals' questions as exercises for my exam and there are no solutions provided.

The question I am currently doing is:

Let ∏ = (Enc, Dec, Gen) be a CPA-secure Encryption Scheme. Prove or disprove the following two statements: a) Enc must be a pseudo-random function. b) Dec must be a pseudo-random function.

For a), intuitively I know it must be pseudorandom but I am not sure how to go about proving it in a formal way. Since the adversary has access to an encryption oracle, we want to make sure they can't distinguish between the different messages and does not learn any useful information about the scheme. And since pseudorandom is indistinguishable from random, then it is necessary?

For b), I don't think it is true, just because on the basis of CPA attacks, they dont really involve decryption, so there's no use for it to be a pseudorandom function. However, if Enc is pseudorandom, wouldn't it need a pseudorandom function to decrypt?

Can anyone let me know if this thinking is on the right track , if not could you please provide an explanation?

Thank you.

  • $\begingroup$ Your intuition for a) is pretty much correct. I assume you have formalized IND-CPA-security by means of a 'game' which is played by the adversary? If so - consider your scheme's encryption function was fully deterministic, that is $Enc_{k}(m)$ (by means of the encryption oracle) would always yield the same result for a fixed key $k$ and message $m$. Can you then define an adversary $A$ which has a non-negligible advantage in winning the game? $\endgroup$
    – Morrolan
    Commented Dec 18, 2021 at 16:45
  • $\begingroup$ For b), consider what would happen if the scheme's decryption function was non-deterministic. That is, $Dec_k(c)$ would not always yield the same result for a fixed key $k$ and ciphertext $c$. Would such a scheme be useful? Specifically, how would it affect e.g. the correctness property of the scheme? $\endgroup$
    – Morrolan
    Commented Dec 18, 2021 at 16:55
  • $\begingroup$ @Morrolan We defined it as P(success)<= 1/2 + negl(n). If it was deterministic then the Adversary would just always receive same ciphertext for same message from the oracle, then there is more than 1/2 chance for adversary to distinguish the different plaintexts. In class, we didn't really model it as a game, so I'm not too sure about that part. $\endgroup$ Commented Dec 18, 2021 at 17:00
  • $\begingroup$ @Morrolan Ohh, makes sense for b), thank you! $\endgroup$ Commented Dec 18, 2021 at 17:01
  • $\begingroup$ @Morrolan Would the same apply for IND-CCA security? I'm not sure since for CCA, adversary has access to a decryption oracle, would Dec need to be PRF but that doesn't really make sense since we dont want to get a mishmashed message. So Enc would still need to PRF since in the context of CCA security, we saw it in a Public key setting and if there no randomness, then it becomes deterministic. $\endgroup$ Commented Dec 18, 2021 at 17:09

1 Answer 1


Some hints:

A pseudorandom function must be a deterministic function from its key and input to its output. Moreover, the outputs should “appear random and independent” when the key is chosen randomly (and fixed) and the inputs are chosen by the attacker.

For (a): in a CPA-secure encryption scheme, can Enc be deterministic in this way? Why or why not?

For (b): in a CPA-secure encryption scheme with a random $sk$, must the outputs of $\text{Dec}_{sk}(\cdot)$ appear random and independent as the attacker varies the input? Why or why not?

  • $\begingroup$ ohhh, ok thank you! $\endgroup$ Commented Dec 20, 2021 at 21:06

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.