The Hong Kong Polytechnic University · FACULTY OF COMPUTER SCIENCE

COMP5563 Chap.2 Stream Ciphers and Semantic Security

- one subject, every graph, every model, every mark
6 Chapters4-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 2 of 5 · COMP5563

Stream Ciphers and Semantic Security

Expand a short secret

A pseudorandom generator deterministically expands a uniform short seed into a longer string that efficient tests cannot distinguish from uniform.

XORing this output with a message produces a stream cipher whose security is computational rather than perfect.

Test the game

Next-bit unpredictability and whole-string indistinguishability express the same objective from different directions. Semantic security lets an adversary choose equal-length messages and challenges it to identify which was encrypted.

Repeated keystreams expose plaintext XOR relations, while ordinary stream ciphertext remains malleable even without reuse, so authentication is still required.

Build the distinguisher

A useful test targets a prefix, parity condition, repeated half or predictable next bit. State its decision rule and compute acceptance on generator output and on a uniform string. Their absolute difference is the advantage.

Visual irregularity matters only when an efficient computation turns it into a probability gap.

Interpret negligible advantage

Negligible advantage falls below every inverse polynomial as the parameter grows. A fixed small decimal is not negligible merely because it sounds unlikely, and an inverse-polynomial improvement remains significant.

Name the parameter and separate an asymptotic proof from a concrete estimate at one key size.

Separate reuse from malleability

Nonce reuse repeats a keystream and leaks relations between plaintexts. Malleability lets an attacker alter one plaintext predictably even with fresh state. Unique nonce-key pairs address the first problem; message authentication addresses the second.

Financial records need both controls.

In this chapter

What this chapter covers

  • 01

    Pseudorandom generator definition

  • 02

    Efficient distinguishers and advantage

  • 03

    Next-bit unpredictability

  • 04

    Two-time pads and nonce reuse

  • 05

    Ciphertext malleability

  • 06

    Semantic security and hybrid reductions

Worked example · free

Distinguish a duplicated generator output

Q [6 marks]. AskSia-authored practice. A generator outputs r concatenated with r for uniform 32-bit r. Give an efficient test and its distinguishing advantage. The marks shown are an AskSia study allocation and are not the University's marking scheme.
The generator replaces an impractically long random pad.The generator replaces an impractically long random pad. Correctness comes from reproducing the same keystream; confidentiality comes only if that output is computationally indistinguishable from uniform. From short secret to encrypted stream secret seeds PRGG(s) keystreamlong pseudorandom bits ciphertextm XOR G(s) message m XOR only after generation
The generator replaces an impractically long random pad. Correctness comes from reproducing the same keystream; confidentiality comes only if that output is computationally indistinguishable from uniform.
  • 2Define the equality test on the two halves.
  • 2Compute acceptance on generator output.
  • 2Compute acceptance on a uniform 64-bit string and subtract.
Accept when the halves match. Generator output always passes. A uniform string passes with probability 2^-32, so the advantage is 1-2^-32, which is not negligible.
Sia tip — A distinguisher is a program plus two probabilities; write both before using the word insecure.
Glossary

Key terms

Pseudorandom Generator
A deterministic expansion whose output is indistinguishable from uniform to efficient algorithms.
Next-Bit Security
No efficient predictor guesses a later output bit from its prefix with non-negligible improvement.
Semantic Security
Chosen equal-length messages remain computationally indistinguishable after encryption.
FAQ

Stream Ciphers and Semantic Security FAQ

How can deterministic output be pseudorandom?

Pseudorandomness compares what an efficient observer can detect, not whether the generation process used fresh randomness for every output bit. The seed is random, and determinism lets both parties reproduce the same keystream.

What exactly goes wrong when a stream nonce repeats?

The same key and nonce reproduce the same keystream. XORing the two ciphertexts cancels it and exposes the XOR of the plaintexts. Known headers or one known message can then reveal the other.

Why does semantic security require equal-length messages?

Ordinary encryption usually reveals ciphertext length. Equal-length challenge messages remove that trivial channel so the experiment measures content leakage. A protocol needing length privacy must add and analyse fixed-size records or padding.

How does the hybrid proof support stream encryption?

The proof replaces generator output with a truly uniform pad. An adversary that notices this replacement distinguishes the generator; in the uniform-pad world, one-time-pad reasoning hides the chosen message. The argument covers confidentiality under its stated interaction, while message length, malleability and nonce management remain separate protocol concerns.

Study strategy

Exam move

For each proposed generator, search first for a relation that a uniform string satisfies with a calculable probability. Write the test in one line, then compute its acceptance in the real and ideal distributions. Repeat with fixed prefixes, parity relations and repeated blocks. For stream encryption, maintain two separate checklists: keystream uniqueness for confidentiality and message authentication for integrity.

Rebuild the left-or-right game from memory, including the equal-length restriction and the hidden bit. Practise the hybrid proof by replacing generator output with a true random pad and naming the PRG distinguisher created by any encryption adversary. Finish by tracing one ciphertext-bit flip through decryption.

That trace makes clear why secrecy does not imply integrity and why a MAC or authenticated-encryption construction is necessary for financial records. Add one exercise in which a generator has a visible relation but no obvious next-bit predictor, then look for the predictor implied by the distinguishing theorem. State whether each advantage is constant, inverse-polynomial or negligible in the chosen parameter.

For protocol practice, design nonce allocation across two servers and a restart, and show exactly where a duplicate can occur. Pair that state audit with an authenticated-field audit so reuse and malleability never collapse into one diagnosis.

Working through Stream Ciphers and Semantic Security in COMP5563? Sia is AskSia’s AI Computer Science tutor — ask any COMP5563 Stream Ciphers and Semantic Security question and get a clear, step-by-step explanation grounded in how COMP5563 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.

A+Everything unlocked
Unlocks this Bible + all 24 of your subjects at The Hong Kong Polytechnic University, plus 1,000+ more Bibles across the AskSia library.
Sia - your COMP5563 tutor, unlimited, worked the way the exam marks it
The full 4-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works