# Does Enc and Dec need to be a pseudo-random function for a scheme to be CPA secure?

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.

• 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? Dec 18, 2021 at 16:45
• 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? Dec 18, 2021 at 16:55
• @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. Dec 18, 2021 at 17:00
• @Morrolan Ohh, makes sense for b), thank you! Dec 18, 2021 at 17:01
• @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. Dec 18, 2021 at 17:09

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?