Private-Key Encryption using PRG and PRF

From CRYPTUTOR

We can use pseudorandom generators and pseudorandom functions to construct private-key encryption schemes with different levels of security.

[edit]

One-time encryption scheme

In one-time pad, the key must be as long as the message. However, if we use a pseudorandom generator to expand a small key into a larger one, the scheme can be made more efficient.

Let $n$ be a security parameter, and $G:\{0,1\}^n \to \{0,1\}^{\ell(n)}$ be a PRG. Consider the following one-time encryption scheme for $\ell(n)$ -bit messages:

Key Generation: Pick a random key $k \gets \{0,1\}^n$ .
Encryption: $\mathsf{Enc}_k(m) = m \oplus G(k)$ .
Decryption: $\mathsf{Dec}_k(c) = c \oplus G(k)$ .

Now, depending on the stretch of $G$ , we can encrypt messages that are larger than the key by any polynomial factor. Because a computational hardness assumption is used ( $G$ is a PRG), this scheme does not have perfect secrecy. However, it achieves a definition of security similar to IND-onetime security, but against PPT adversaries (and allowing for negligible advantage). Intuitively, using $G(k)\,$ as a mask instead of a truly random $\ell(n)$ -bit mask is equivalent when considering polynomial-time adversaries.

[edit]

Stateful encryption scheme

If we want to send multiple messages, we can use a PRG with very large stretch and keep using bits from it to mask our messages. Let $G$ be a PRG with very large stretch, and consider the following encryption scheme:

Key Generation: Pick a random key $k \gets \{0,1\}^n$ .
Encryption: To encrypt a message $m$ , "mask" (XOR) it with the next $|m|\,$ unused bits of $G(k)\,$ .
Decryption: To decrypt a ciphertext $c$ , XOR it with the next $|m|\,$ unused bits of $G(k)\,$ .

Note that the encryption and decryption algorithms must keep track of state (a position in the long string $G(k)\,$ ), and as a result, the sender and receiver must be synchronized. This scheme achieves a variant of SIM-CPA security for stateful encryption schemes.

Instead of using a PRG which outputs a string of fixed length, a stream cipher could be used to allow sending an a priori unbounded number of messages.

[edit]

Full CPA security

The previous construction used a long pseudorandom string to generate message masks. Because this access was sequential, we needed to keep track of state.

One interpretation of the definition of pseudorandom functions is that a PRF gives random access to an exponentially long pseudorandom string. This is the last piece we need to achieve full SIM-CPA security. Let $F:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$ be a PRF, and consider the following encryption scheme for $n$ -bit messages:

Key Generation: Pick a random key $k \gets \{0,1\}^n$ .
Encryption: To encrypt a message $m \in \{0,1\}^n$ under key $k$ , choose a random $\sigma \gets \{0,1\}^n$ and output $(\sigma, m \oplus F_k(\sigma))$ .
Decryption: $\mathsf{Dec}_k(\sigma, c) = c \oplus F_k(\sigma)$ .