Foundations of Cryptography (CS60088)
Spring 2026
Tutorial 2: Computational secrecy and pseudorandom objects
1. Let G be a pseudorandom generator (PRG) that stretches n-bit strings to 2n-bit strings. For
s ∈ {0, 1}n , write
G(s) = G0 (s) ∥ G1 (s),
where G0 (s) denotes the first n bits of G(s) and G1 (s) denotes the last n bits. Define a new
generator G′ that stretches n-bit strings to 4n-bit strings as
G′ (s) = G(G0 (s)) ∥ G(G1 (s)).
Prove or disprove that if G is a secure PRG, then G′ is also a secure PRG.
2. Suppose G1 and G2 are PRGs mapping {0, 1}n to {0, 1}ℓ . Define a new generator
G : {0, 1}n × {0, 1}n → {0, 1}ℓ
by
G(s1 , s2 ) = G1 (s1 ) ⊕ G2 (s2 ).
Show that if either G1 or G2 is secure (we may not know which one), then G is a secure PRG.
3. (a) Formally define (using a security game) the notion of perfect secrecy under chosen-
plaintext attacks, also called perfect IND-CPA security, for symmetric encryption schemes.
Your definition should be analogous to perfect secrecy in the presence of an eavesdropper.
(b) Show that there cannot exist an encryption scheme that achieves perfect IND-CPA
security.
4. Let E1 = (Gen1 , Enc1 , Dec1 ) and E2 = (Gen2 , Enc2 , Dec2 ) be two symmetric encryption
schemes over message spaces M1 , M2 , key spaces K1 , K2 , and ciphertext spaces C1 , C2 , re-
spectively. You are given that exactly one of E1 or E2 is IND-CPA-secure, but you do not
know which one.
Assume M1 = M2 = {0, 1}n . Construct an encryption scheme
E = (Gen, Enc, Dec)
from E1 and E2 that is guaranteed to be IND-CPA-secure. Prove that your construction is
indeed IND-CPA-secure.
5. Let G : {0, 1}n → {0, 1}ℓ be a pseudorandom generator, and define G′ (s) to be the first n
bits of G(s). Consider the keyed function Fk : {0, 1}n → {0, 1}n defined by
Fk (x) = G′ (k) ⊕ x,
where k ∈ {0, 1}n . Is the family {Fk } pseudorandom? Justify your answer.
1
6. Let F = {Fk : {0, 1}n → {0, 1}n }k∈{0,1}n be a pseudorandom function family, and let G be
a pseudorandom generator with input length n and output length ℓ = n + 1. In each of the
U
− {0, 1}n .
following schemes, the shared key k is chosen as k ←
For each scheme, state whether it is IND-EAV-secure and whether it is IND-CPA-secure.
Justify your answer.
(a) To encrypt m ∈ {0, 1}2n+2 , parse m as m1 ∥ m2 with |m1 | = |m2 |, and output
⟨G(k) ⊕ m1 , G(k + 1) ⊕ m2 ⟩.
U
(b) For m ∈ {0, 1}n+1 , choose r ←
− {0, 1}n and output
⟨r, G(r) ⊕ m⟩.
(c) Encrypt m ∈ {0, 1}n as
m ⊕ Fk (0n ).
U
(d) Parse m ∈ {0, 1}2n as m1 ∥ m2 with |m1 | = |m2 |, choose r ←
− {0, 1}n , and output
⟨r, m1 ⊕ Fk (r), m2 ⊕ Fk (r + 1)⟩.
7. Let F be a length-preserving pseudorandom function. For each of the following constructions
of a keyed function
F ′ : {0, 1}n × {0, 1}n−1 → {0, 1}2n ,
state whether F ′ is a pseudorandom function. If it is, prove it; otherwise, describe an explicit
attack.
def
(a) Fk′ (x) = Fk (0 ∥ x) ∥ Fk (1 ∥ x).
def
(b) Fk′ (x) = Fk (0 ∥ x) ∥ Fk (x ∥ 1).
8. Prove unconditionally the existence of a pseudorandom function
F : {0, 1}∗ × {0, 1}∗ → {0, 1}∗
with key length ℓkey (n) = n and input length ℓin (n) = O(log n). Hint: Implement a uniform
function with logarithmic input length.
9. Let G be a pseudorandom generator with expansion factor ℓ(n) > 2n. In each of the following
cases, determine whether the function G′ is necessarily a pseudorandom generator. If yes,
give a proof; if not, provide a counterexample.
(a) Define
def
G′ (s) = G s1 · · · s⌈n/2⌉ ,
where s = s1 s2 · · · sn ∈ {0, 1}n .
2
(b) Define
def
G′ (s) = G 0|s| ∥ s .
(c) Define
def
G′ (s) = G(s) ∥ G(s + 1),
where s + 1 denotes addition modulo 2n .