CPA-Secure Ciphers from PRF

Definition

A CPA-secure cipher from a PRF is an encryption scheme built using a pseudorandom function such that, for any efficient adversary who can adaptively choose plaintexts and obtain their encryptions, the adversary cannot distinguish encryptions of chosen messages better than guessing.

Core definition terms

PRF (Pseudorandom Function)

• A keyed function family $F_k(\cdot)$ such that no efficient attacker can distinguish it from a truly random function.

CPA (Chosen-Plaintext Attack) security

• A security notion where the adversary may query an encryption oracle on plaintexts of its choice and still should not be able to distinguish which of two messages was encrypted.

Cipher / Encryption scheme

• A pair of algorithms, typically:
• Enc: encryption
• Dec: decryption

Formal intuition

If a scheme uses a PRF to generate a pad or mask from the message or a nonce, then the resulting ciphertext should look random to an attacker, provided the PRF behaves like a random function.

A classic example is:

• Choose secret key $k$
• Encrypt message $m$ as $c = (r,\, m \oplus F_k(r))$, where $r$ is a fresh random nonce/IV

Here, $F_k(r)$ acts like a one-time pad derived from a pseudorandom source.

---

Main Content

1. Pseudorandom Function (PRF)

Meaning and role

• A PRF is a deterministic function family indexed by a secret key.
• For a fixed key $k$, the function $F_k$ is easy to compute by the legitimate user, but should appear random to any efficient outsider.
• It is the cryptographic workhorse used to simulate randomness in encryption.

Why PRFs matter in encryption

• Encryption often needs a mask, pad, or keystream that looks unpredictable.
• A PRF provides this unpredictability without requiring true randomness for every message.
• If a PRF output is indistinguishable from random, then using it to hide plaintext can make ciphertexts secure under chosen-plaintext attacks.

Example intuition

• Suppose $F_k$ maps a nonce $r$ to a 128-bit string.

• For encryption, the system computes: $$c = (r, m \oplus F_k(r))$$

• To an attacker who does not know $k$, the mask $F_k(r)$ should look random, so $m$ becomes hidden.

Important property

• The PRF must be secure against efficient distinguishers.
• Even if the attacker sees many input-output pairs, the function should still look random.

---

2. CPA Security

What CPA means

• CPA stands for Chosen-Plaintext Attack.
• In this setting, the adversary can ask the encryption oracle to encrypt any plaintexts it wants.
• The attacker’s goal is to learn something meaningful about the encryption of a target message.

Security game view

• The adversary can submit two messages $m_0, m_1$ of equal length.
• The challenger picks a hidden bit $b\in\{0,1\}$ and encrypts $m_b$.
• The adversary receives the ciphertext and tries to guess $b$.
• A scheme is CPA-secure if no efficient adversary can do significantly better than random guessing.

Why this is strong

• Even if an attacker can freely request encryptions of messages of its choice, the scheme should not reveal which message was selected in the challenge.
• This is stronger than merely hiding the plaintext from passive eavesdroppers.

Key intuition

• A secure encryption scheme under CPA should make ciphertexts of equal-length messages computationally indistinguishable.
• This is the modern standard for semantic security in symmetric encryption.

---

3. Constructing a CPA-Secure Cipher from a PRF

Basic construction

• Let $F_k$ be a secure PRF.
• To encrypt a message $m$, choose a fresh random nonce $r$.

• Compute: $$c = (r,\, m \oplus F_k(r))$$

• To decrypt: $$m = (m \oplus F_k(r)) \oplus F_k(r)$$

• Since XOR with the same string twice cancels out, decryption works correctly.

How it provides confidentiality

• The mask $F_k(r)$ acts like a pseudorandom pad.
• If $r$ is unique or randomly chosen each time, the same message encrypts to different ciphertexts.
• This prevents an attacker from spotting repeated plaintexts by comparing ciphertexts.

Why the scheme is CPA-secure

• In the ideal world, if $F_k$ were replaced by a truly random function, then the mask would be uniformly random for each fresh $r$.
• Then the ciphertext component $m \oplus F_k(r)$ would be information-theoretically hidden.
• Since the real PRF is computationally indistinguishable from random, the real scheme is computationally indistinguishable from the ideal secure scheme.

Example

• Let $m = 10110010$
• Suppose the PRF output for nonce $r$ is $11001100$

• Then ciphertext body is: $$10110010 \oplus 11001100 = 01111110$$

• The transmitted ciphertext is $(r, 01111110)$

• Without knowing the key, the attacker cannot recover the message.

Why randomness or nonce freshness is essential

• If the same $r$ is reused, the same mask repeats.
• Then attackers can compare ciphertexts and derive relationships between plaintexts.
• Fresh nonces or IVs are therefore crucial.

---

Working / Process

1. Key generation and setup

• The sender and receiver share a secret key $k$.
• This key is used to evaluate the PRF $F_k$.
• The PRF is chosen from a secure family, such as one built from block ciphers or HMAC-like constructions.

2. Encryption process

• For each message $m$, generate a fresh random nonce $r$.
• Compute a pseudorandom mask $F_k(r)$.

• XOR the mask with the message: $$c_2 = m \oplus F_k(r)$$

• Output the ciphertext: $$c = (r, c_2)$$

3. Decryption process

• Extract the nonce $r$ from the ciphertext.

• Recompute the mask using the same key: $$F_k(r)$$

• Recover the plaintext by XORing: $$m = c_2 \oplus F_k(r)$$

• If the ciphertext was not altered and the nonce is valid, the original message is recovered exactly.

Visual flow

Message $m$ + nonce $r$ + key $k$

$$\text{Encryption: } m \xrightarrow{\oplus\,F_k(r)} c_2,\quad c=(r,c_2)$$

$$\text{Decryption: } c=(r,c_2) \xrightarrow{\oplus\,F_k(r)} m$$

Why the process is secure

• The attacker sees the nonce $r$, but not the key $k$.
• The attacker cannot compute $F_k(r)$.
• Without the mask, the XORed message part is useless.
• Therefore the ciphertext hides the plaintext under CPA assumptions.

Important caveat

• This construction provides confidentiality only.
• It does not automatically guarantee integrity or authenticity.
• An attacker may still modify ciphertexts unless a message authentication mechanism is added.

---

Advantages / Applications

Strong confidentiality under chosen-plaintext attacks

• The scheme protects against attackers who can encrypt messages of their choice.
• This is a practical and widely accepted baseline security requirement.

Simple and efficient design

• Encryption and decryption are computationally lightweight.
• XOR operations and PRF evaluations are fast, making the scheme efficient for real systems.

Foundation for modern cryptographic protocols

• PRF-based encryption is a building block for many real-world systems.
• It is used conceptually in secure messaging, session encryption, randomized encryption schemes, and hybrid constructions.

Useful in protocol design

• Nonces, counters, and key-derived masks appear frequently in secure communication protocols.
• PRFs help generate unpredictable keystreams in a structured and analyzable way.

Easy to analyze formally

• The proof technique is elegant: replace the PRF with a truly random function, then argue confidentiality.
• This makes it ideal for theoretical study and for understanding reduction-based security proofs.

---

Summary

• CPA-secure ciphers aim to hide messages even when attackers can request encryptions of chosen plaintexts.
• A PRF can be used to generate a pseudorandom mask that hides the message under XOR.
• Fresh nonces or IVs are essential so that repeated encryptions do not reuse the same mask.
• The construction is secure because a PRF is computationally indistinguishable from a truly random function.
• Important terms to remember: PRF, CPA security, nonce, XOR masking, encryption oracle