1. Let F : {0, 1}
n × {0, 1}
n → {0, 1}
n be a keyed pseudorandom permutation (the first
argument is the key). Consider the keyed function F
0
: {0, 1}
n × {0, 1}
2n → {0, 1}
2n
defined for all x, x0 ∈ {0, 1}
n by
F
0
k
(xkx
0
) = Fk(x)kFk(x ⊕ x
0
).
(a) [1 point] Prove that F
0
k
is a permutation for all k ∈ {0, 1}
n
.
(b) [4 points] Prove that F
0
k
is not a pseudorandom permutation.
2. [5 points] Let F : {0, 1}
n × {0, 1}
n → {0, 1}
n be a pseudorandom permutation. Suppose messages of size dn bits have to be encrypted where d 1. The message m is
divided into d blocks of n bits each where mi
is the ith block. Consider the mode
of operation in which a uniform value ctr ∈ {0, 1}
n
is chosen, and the ith ciphertext block ci
is computed as ci
:= Fk(ctr + i + mi). The value ctr is sent in the
clear, i.e. the eavesdropper observes ctr, c1, c2, c3, . . . , cd. The sum ctr + i + mi
is
calculated modulo 2n
ensuring that the argument of Fk belongs to {0, 1}
n
. Show
that this scheme does not have indistinguishable encryptions in the presence of an
eavesdropper.
