Semantic Security and Pseudorandom Generators (PRGs)

Definition

Semantic security is a security property of an encryption scheme stating that, given a ciphertext, no efficient adversary can learn any additional useful information about the plaintext beyond what it could already know without seeing the ciphertext.

A pseudorandom generator (PRG) is a deterministic polynomial-time algorithm that stretches a short uniformly random seed into a longer output string that is computationally indistinguishable from a truly random string of the same length.

In simple terms:

Semantic security means “the ciphertext should not leak meaning.”
A PRG means “a short random secret can be expanded into a long string that looks random.”

Main Content

1. Semantic Security

Core idea

An encryption scheme is semantically secure if an attacker, after seeing a ciphertext, cannot effectively determine any meaningful property of the underlying message. This includes not only the exact plaintext but also partial information such as whether the message contains a specific word, whether it is one of two possible messages, or whether it matches a known pattern.

Why it matters

In real systems, secrecy is not just about hiding the entire message. Even small leaks can be dangerous. For example, if encrypting medical records reveals whether a patient has a certain condition, or if encrypted political messages reveal which side a person supports, the encryption is not truly secure.

A more formal way to understand semantic security is through the idea of an attacker choosing two messages and trying to distinguish which one was encrypted. If the attacker cannot do better than random guessing, then the encryption is considered secure under this notion.

Example:
Suppose Alice sends either:

Message M0: “The meeting is at 10 AM”
Message M1: “The meeting is at 6 PM”

If an attacker sees the ciphertext and can tell which one was sent, the scheme is not semantically secure. If the attacker cannot distinguish them with any efficient method, the scheme provides semantic security.

Important intuition:
Semantic security says that ciphertexts should act like “meaningless noise” from the attacker’s viewpoint, even though they are decryptable by the legitimate receiver.

2. Pseudorandom Generators (PRGs)

Core idea

A PRG starts with a small random seed and expands it into a much longer string. Although the output is produced deterministically from the seed, it should appear random to any efficient adversary.

Key properties

A PRG must be:
Efficient: It should run in polynomial time.
Stretching: The output length must be larger than the input seed length.
Pseudorandom: The output should be computationally indistinguishable from true randomness.

A truly random string of length n is fully unpredictable. A PRG output is not truly random because it is generated by a deterministic function, but it is designed so that no efficient algorithm can tell the difference.

Example:
If a seed of 128 bits is expanded to a 1024-bit output, the result may be used to generate encryption keys, masks, or keystreams. Even though the output is derived from a small seed, it should look as if it were selected uniformly at random.

Why PRGs are important:
True randomness is expensive or hard to obtain in large quantities. PRGs allow systems to “stretch” limited randomness into more usable random-looking bits for cryptographic tasks.

3. Relationship Between Semantic Security and PRGs

PRGs help construct secure encryption schemes

Many encryption methods use PRGs to generate random-looking keystreams or pads. If the PRG output is indistinguishable from random, then the resulting ciphertext can be made semantically secure.

Semantic security relies on unpredictability

If the random-looking values used in encryption are predictable, an attacker may recover information from the ciphertext. PRGs provide the computational unpredictability needed for secure encryption.

A classic example is stream encryption, where a message is combined with a pseudorandom keystream generated from a secret seed. If the keystream is indistinguishable from random, then the ciphertext reveals nothing useful about the plaintext.

ASCII diagram for how a PRG supports encryption:

Short secret seed ----> PRG ----> Long pseudorandom output
                                 |
                                 v
Plaintext ------------ XOR -----------------> Ciphertext

Here:

the seed is the secret input,
the PRG generates a keystream,
XOR combines the keystream with the plaintext,
the result is the ciphertext.

If the keystream behaves like truly random bits, then the ciphertext is hard to analyze.

Working / Process

1. Start with a short random seed

A sender or encryption system begins with a small secret seed that is genuinely random.
This seed is kept secret and used as the input to the PRG.
Example: a 128-bit seed chosen from a secure random source.

2. Expand the seed using a PRG

The PRG deterministically transforms the short seed into a longer bit string.
This output is not truly random, but it should be computationally indistinguishable from random.
The output length is typically much larger than the seed length, allowing the system to generate more cryptographic material than the original randomness would normally allow.

3. Use the pseudorandom output in encryption

The generated bits are used as a keystream, mask, nonce-related material, or internal randomness depending on the encryption design.
The plaintext is encrypted with these bits so that the ciphertext hides the message effectively.
If the PRG is secure, then the ciphertext remains semantically secure because the attacker cannot tell whether the encrypted randomness came from a PRG or from a truly random source.

Process illustration:

Seed (secret, random)
        |
        v
   PRG expands it
        |
        v
Pseudorandom bits
        |
        v
Encryption algorithm
        |
        v
Ciphertext that hides the plaintext

Important detail:
If the PRG is weak, the whole encryption system may fail. Even a strong encryption formula cannot stay secure if the randomness it depends on can be predicted.

Advantages / Applications

Efficient generation of random-looking bits

PRGs make it possible to produce large amounts of pseudorandom data from a small random seed, which is extremely useful in practice when true randomness is limited.

Foundation for secure encryption

Semantic security is a major goal of modern encryption, and PRGs are often a key ingredient in achieving it. They support stream ciphers, one-time-pad-like constructions, and randomized encryption schemes.

Broad cryptographic utility

PRGs are used in key generation, masking, nonce creation, simulations, randomized algorithms, and other security protocols where unpredictability is essential.

Summary

Semantic security means encryption should not reveal useful information about the plaintext.
A PRG expands a short random seed into a longer output that looks random to efficient attackers.
PRGs are essential tools for building encryption schemes that achieve semantic security.
Important terms to remember: semantic security, pseudorandom generator, seed, computational indistinguishability, ciphertext, plaintext, keystream