0
$\begingroup$

I'm a bit confused about the relationship between CCA/CPA-security and PRFs and particularly when do we think of encryption and decryption as a PRF. Assume we have an encryption scheme $\Pi = (Enc, Dec, Gen)$ to be a CPA-secure. Can we say that:

  • $Enc$ must be a PRF?
  • $Dec$ must be a PRF?

What about the case when $\Pi$ is CCA-Secure?

My intuition is that we can have $Dec$ to be a PRF for both cases since it's deterministic, but not sure if that is actually required?

For $Enc$, it cannot be a PRF since otherwise, $\Pi$ won't be CPA-secure.

Thanks!

$\endgroup$
  • $\begingroup$ "when do we think of encryption and decryption as a PRF. " - We never do that. $\endgroup$ – Maeher Apr 17 '18 at 1:47
  • $\begingroup$ Can a PRF be non-injective? Can an encryption scheme be non-injective? Does any pair of participants in this conversation have the same birthday? $\endgroup$ – Squeamish Ossifrage Apr 17 '18 at 1:58
1
$\begingroup$

IND-CPA/CCA encryption schemes do imply PRFs: Does IND-CPA imply PRF?

But the above result does not mean Enc or Dec must be a PRF. From its definition, a PRF is indistinguishable from a random function for polynomial-time attackers. We can easily make Enc look non-random but still secure. For instance, you can append some 0 bits to the end of the ciphertexts. As for Dec, its domain is not easy to get. If the encryption scheme satisfies the integrity of ciphertext (INT-CTXT), then you cannot even find valid ciphertexts and almost always get nothing from Dec.

Btw, as you noticed, PRFs are deterministic, so you should consider the "random tape" inside Enc when comparing them.

$\endgroup$
  • $\begingroup$ I would add that not only does CPA/CCA secure encryption imply PRFs, but the reverse is also true. I.e., PRFs imply CCA secure encryption. The two are existentially equivalent. (But of course neither is an encryption scheme a PRF nor is a PRF an encryption scheme.) $\endgroup$ – Maeher Apr 17 '18 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.