# If pseudorandom functions (PRFs) are deterministic in nature, how can encryption schemes using PRF be CPA secure?

I am new to crytography. Can anybody tell me what I might be missing here?

## 4 Answers

The common way is to use a PRF for encryption is the CTR mode which is introduced by Whitfield Diffie and Martin Hellman in 1979;

This is a must-read paper that provides insight into the cryptography during 1970s. CTR mode doesn't need a PRP it can be work with a PRF and actually have better security bounds with the PFF( PRF-PRP switching lemma). To use the CTR mode with a PRF;

1. Choose a uniform random key on a key $$k$$

2. Choose a uniform random nonce ( counter-based are ok)

3. Generate the keystream $$s_i$$ as

$$s_i = PRF(key,nonce,i)$$

4. Encrypt the plaintext bit $$p_i$$ as $$c_i = p_i \oplus s_i$$

Like everything in cryptography, the CTR mode has advantages and disadvantages and the golden rule never uses an $$(IV,key)$$ pair again.

A well-known example is the ChaCha20 stream cipher based on the presumed ChaCha20 PRF.

CTR mode is CPA secure. To show the CPA security we need to play the Ind-CPA game.

1. Set the security parameter $$1^n$$
2. Call $$Gen(1^n)$$ to generate a key $$k$$
3. Provide $$1^n$$ to the adversary and Oracle Access to $$E_k(\cdot)$$
4. The adversary outputs the message $$m_1$$ and $$m_2$$ of the same length
5. Uniformly select a bit $$b$$ and send the ciphertext $$c = E_k(m_b)$$.
6. Adversary continue to using the oracle
7. Adversary outputcal_ $$b'$$
8. If $$b=b'$$ then output 1, else output 0.

Then, a scheme $$\pi$$ ( here CTR) is said to have Ind-CPA if

$$\Pr\left[ \operatorname{PrivK}^{CPA}_{\mathcal{A},\pi}\right] \leq \frac{1}{2} + \operatorname{negl}(n)$$

The proof is long to write here. See the Theorem 3.33 on the 3rd edition of Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell

CTR mode is malleable, i.e. it cannot achieve CCA security. For this either use it together with a MAC like HMAC or use it in Authenticated Encryption mode fashion.

If pseudorandom functions (PRFs) are deterministic in nature, how can encryption schemes using PRF be CPA secure?

Yes, they are deterministic, however, the way we use them for encryption and decryption is probabilistic encryption. This is achieved even with the fixed key by using an IV/nonce per message. This is the sole reason that the advantage of the adversary is negligible.

Typically by using the secret key as input to the PRF.

Actually many stream ciphers are somewhat based on the fact that a PRF can be used to extend a key into a longer stream, the keystream, and then that keystream is XORed with the plaintext, à la OTP.

The deterministic nature of the PRF becomes a feature as it allows to easily recover the same keystream if you know the secret key, thus allowing for decryption by XORing the ciphertext with that same keystream to recover the initial plaintext.

## Regarding CPA security

It is important to realize that a deterministic encryption scheme cannot be IND-CPA secure.

So a PRF being deterministic can seem like a bad thing there, but the "usual" workaround is to add randomness to the ciphertext by using a so-called "initialization vector". The initialization vector (IV) is basically a salt which will bring randomness to the process, so that 2 encryption of the same plaintext won't produce the same ciphertext. The IV should usually be a nonce, but only as long as we are reusing the same key.

You may be misunderstanding what "random" and "pseudorandom" mean. The words "random" and "pseudorandom" do not describe the functions themselves but the probability distribution from which the functions are chosen.

Technically, we don't have any definition of a "random" or "pseudorandom" function. What we have is either a "random" distribution of functions or a "pseudorandom" distribution of functions. Informally, a "pseudorandom" distribution of functions from $$A$$ to $$B$$ is defined as indistinguishable, by any polynomial-time algorithm, from a random distribution of functions from $$A$$ to $$B$$.

Mathematically, there's no such thing a "random", "deterministic", or "pseudorandom" function. But we still use those terms and they're understood implicitly.

How can encryption schemes using PRF be CPA secure?

In short, if an encryption scheme is secure using a random distribution of functions, then it's also secure using a "pseudorandom" distribution of functions, because the two are indistinguishable. Any algorithm that can break the scheme with a pseudorandom distribution, can be converted into an algorithm that can distinguish between the random and pseudorandom distributions.

It's true that PRF on its own is deterministic (think of standalone block cipher). This is why you add randomness (in a form of IV or nonce) to an encryption mode to make it IND-CPA.