Cryptography – Homework 1

1 Perfect Secrecy
We have the following two definitions.

Definition 1.1 (Shannon)

A SKE scheme Π = (Enc, Dec) has (Shannon) perfect secrecy if
∀m ∈ M, ∀c ∈ C, Pr [M = m | C = c] = Pr [M = m] .

Definition 1.2 (Eav)

Π,A : A ←→ C be defined as follows:
Let Π = (Enc, Dec) be a SKE scheme and let Gameeav
1. the challenger C picks k ← $K and b ← ${0, 1};
2. the adversary A chooses (m0 , m1 ) ∈ M × M;
3. C computes c = Enc(k, mb ) and gives c to A ;
4. A chooses a bit b0 ;
5. the game outputs 1 if and only if b = b0 .
We say that Π has (EAV) perfect secrecy if
 1
Pr Gameeav

Π,A = 1 = .
2

Applying Shannon’s Theorem, the Definition 1.1 is equivalent to require that

∀m0 , m1 ∈ M, ∀c ∈ C, Pr [Enc(K, m0 ) = c] = Pr [Enc(K, m1 ) = c] .

Claim 1.3
Definition 1.1 ⇒ Definition 1.2.

Proof
Let B be the (uniformly distributed) random variable associated to b ← ${0, 1} and let
B 0 be the random variable associated to the choice of b0 from the adversary A . Then,
proving the formula in the Definition 1.2 is equivalent to prove that
1
= Pr [B 0 = B] ,
2
where K is the (uniformly distributed) random variable associated to k ← $K.
Splitting in the two cases B = 0 and B = 1 and using the Bayes formula, we obtain
Pr [B 0 = B] = Pr [Enc(K, mB 0 ) = Enc(K, mB )]
= Pr [Enc(K, mB 0 ) = Enc(K, mB ) ∧ B = 0]
+ Pr [Enc(K, mB 0 1 ) = Enc(K, mB ) ∧ B = 1]
= Pr [Enc(K, mB 0 ) = Enc(K, mB ) | B = 0] Pr [B = 0]
+ Pr [Enc(K, mB 0 ) = Enc(K, mB ) | B = 1] Pr [B = 1] .

1
 Now remember that B is uniformly distributed over {0, 1}, thus
1
Pr [B = 0] = Pr [B = 1] = ,
2
and the above formula becames
1 1
Pr [B 0 = B] = Pr [Enc(K, mB 0 ) = Enc(K, m0 )] + Pr [Enc(K, mB 0 ) = Enc(K, m1 )] .
2 2
Call
C0 = Enc(K, m0 ), C1 = Enc(K, m1 )
and split the two probabilities over all the possible choiches of c ∈ C: we obtain
X
Pr [Enc(K, mB 0 ) = Enc(K, m0 )] = Pr [Enc(K, mB 0 ) = C0 ∧ C0 = c]
c∈C
X
= Pr [Enc(K, mB 0 ) = C0 | C0 = c] Pr [C0 = c]
c∈C
X
= Pr [Enc(K, mB 0 ) = c] Pr [C0 = c]
c∈C

and
X
Pr [Enc(K, mB 0 ) = Enc(K, m1 )] = Pr [Enc(K, mB 0 ) = C1 ∧ C1 = c]
c∈C
X
= Pr [Enc(K, mB 0 ) = C1 | C1 = c] Pr [C1 = c]
c∈C
X
= Pr [Enc(K, mB 0 ) = c] Pr [C1 = c] .
c∈C

Apply now Definition 1.1:

Pr [C0 = c] = Pr [C1 = c] .

We obtain that the two above probabilities are equal:

Pr [Enc(K, mB 0 ) = Enc(K, m0 )] = Pr [Enc(K, mB 0 ) = Enc(K, m1 )] ,

or, in other words,

Pr [B 0 = 0] = Pr [B 0 = 1] ,
therefore B 0 is uniformly distributed over {0, 1} and, for all b, b0 ∈ {0, 1},
1
Pr [B = b ∧ B 0 = b0 ] = .
4
We get the event B = B 0 if and only if b = b0 and that happens in two out of four equally
distributed cases, thus
1
Pr [B = B 0 ] = .
2

Claim 1.4
Definition 1.1 ⇐ Definition 1.2.

2
Proof
This is easier to prove: assume that Π is a SKE scheme for which the Definition 1.1 does
not hold; in particular, let m0 , m1 ∈ M, c0 ∈ C be such that
Pr [Enc(K, m0 ) = c0 ] > Pr [Enc(K, m1 ) = c0 ] .
Then, the adversary A can choose exactly m0 and m1 to challenge C and act as follows:
• if C outputs C = c0 , A outputs b0 = 0;
• if C outputs C 6= c0 , A outputs b0 ← ${0, 1}.
Now the probability of winning the game is
0 0
Pr Gameeav eav eav
     
Π,A = 1 = Pr GameΠ,A = 1 ∧ C = c + Pr GameΠ,A = 1 ∧ C 6= c ,

where
0 0 0
Pr Gameeav eav
   
Π,A = 1 ∧ C 6= c = Pr GameΠ,A = 1 C 6= c Pr [C 6= c ]
1
= Pr [C 6= c0 ]
2
and
0 0 0
Pr Gameeav eav
   
Π,A = 1 ∧ C = c = Pr GameΠ,A = 1 C = c Pr [C = c ] .

Similarly,
0 0
Pr Gameeav eav eav
     
Π,A = 0 = Pr GameΠ,A = 0 ∧ C = c + Pr GameΠ,A = 0 ∧ C 6= c ,

where
0 0 0
Pr Gameeav eav
   
Π,A = 0 ∧ C 6= c = Pr GameΠ,A = 0 C 6= c Pr [C 6= c ]
1
= Pr [C 6= c0 ]
2
and
0 0 0
Pr Gameeav eav
   
Π,A = 0 ∧ C = c = Pr GameΠ,A = 0 C = c Pr [C = c ] .

Now, if we compute the difference we obtain

Pr Gameeav eav
   
Π,A = 1 − Pr GameΠ,A = 0
0 0
= Pr Gameeav
 
Π,A = 1 C = c Pr [C = c ]
0 0
− Pr Gameeav
 
Π,A = 0 C = c Pr [C = c ]
0 0
= Pr Gameeav eav
Pr [C = c0 ]
   

Π,A = 1 C = c − Pr GameΠ,A = 0 C = c
= (Pr [Enc(K, m0 ) = c0 ] − Pr [Enc(K, m1 ) = c0 ]) Pr [C = c0 ]
> 0,
therefore
Pr Gameeav eav
   
Π,A = 1 > Pr GameΠ,A = 0
and, being the sum equal to 1,
 1
Pr Gameeav

Π,A = 1 > .
2

Applying both Claim 1.3 and Claim 1.4, we can conclude that Definition 1.1 and Definition
1.2 are equivalent.

3
2 Universal Hashing
Definition 2.1
A family H = {hs : X → Y }s∈S of hash functions is called t-wise independent if for
all sequences of distinct x1 , . . . , xt ∈ X and for any sequence y1 , . . . , yt ∈ Y ,
1
Pr [hs (x1 ) = y1 ∧ . . . ∧ hs (xt ) = yt | s ← $S] = t.
|Y |

Proposition 2.2
For any t ≥ 2, if H is t-wise independent, then it is also (t − 1)-wise independent.

Proof
Let H be t-wise independent and fix a sequence of distinct x1 , . . . , xt−1 ∈ X and a
sequence y1 , . . . , yt−1 ∈ Y . Fix x ∈ X \ {x1 , . . . , xt−1 } and write
Pr [hS (x1 ) = y1 ∧ . . . ∧ hS (xt−1 ) = yt−1 ]
X
= Pr [hS (x1 ) = y1 ∧ . . . ∧ hS (xt−1 ) = yt−1 ∧ hS (x) = y]
y∈Y
X 1
= t
y∈Y
|Y |
|Y |
=
|Y |t
1
= .
|Y |t−1
Then, the Proposition holds because x is arbitrary in X \ {x1 , . . . , xt−1 }.

Proposition 2.3
Let q be a prime and let n ≥ 2 such that q ≥ n. Then, the family
Hn = hs : Zq → Zq : x 7→ s0 + s1 x + . . . + sn−1 xn−1 s=(s0 ,...,sn−1 )∈Zn

q

is n-wise independent.

To prove this easily, we need a definition and a theorem.

Definition 2.4
A square Vandermonde matrix is a matrix in the form
x20 xn−1
 
1 x0 ··· 0
1 x 1 x 2
1 ··· xn−1
1

Vn =  . ..  .
 
. . ..
 .. .. .. . . 
1 xn−1 x2n−1 · · · xn−1
n−1

In other words, Vn is a square Vandermonde matrix if it is square and every row forms a
geometric progression starting from 1.

Theorem 2.5
Let Vn be a square Vandermonde matrix. Using the same notation as in Definition 2.4,
if x0 , . . . , xn−1 are all distinct, then Vn is invertible1 .
1 In particular, the inverse form is known, so Vn−1 is efficiently computable.

4
Let’s prove this for n = 3.

Proof (n = 3)
For n = 3, the form of V3 is
x20
 
1 x0
1 x1 x21 
1 x2 x22
and
x20 x20
   
1 x0 1 x0
det 1 x1 x21  = det 0 x1 − x0 x21 − x20 
1 x2 x22 0 x2 − x0 x22 − x20
x20
 
1 x0
= (x1 − x0 )(x2 − x0 ) det 0 1 x1 + x0 
0 1 x2 + x0
x20
 
1 x0
= (x1 − x0 )(x2 − x0 ) det 0 1 x1 + x0 
0 0 x2 − x1
x20
 
1 x0
= (x1 − x0 )(x2 − x0 )(x2 − x1 ) det 0 1 x1 + x0 
0 0 1
= (x1 − x0 )(x2 − x0 )(x2 − x1 ).

Finally, if x0 , x1 , x2 are all distinct, det(V3 ) 6= 0 and V3 is invertible.

Proof (Proposition 2.3)

Given hs ∈ Hn , s = (s0 , . . . , sn−1 ), we can easily evaluate hs in x0 , . . . , xn−1 ∈ Zq
simultaneously by constructing the matrix

x20 · · · xn−1
 
1 x0 0
1 x1 x21 · · · xn−1
1

Vn =  .
 
. . . .
 .. .. .. .. .. 

2 n−1
1 xn−1 xn−1 · · · xn−1

and calculating the product

s0 + s1 x0 + . . . + sn−1 x0n−1 xn−1

      
y0 1 x0 ··· 0 s0
 ..   .
.. . .. .. ..   .. 
 . =  =  ..
 
. . .  . 
yn−1 s0 + s1 xn−1 + . . . + sn−1 xn−1
n−1 1 xn−1 ··· xn−1
n−1 sn−1

or, in short notation,

y = Vn · s
If x0 , . . . , xn−1 ∈ Zq are all distinct, Vn is invertible by Theorem 2.5, thus we can write

s = Vn−1 y.

In particular, Vn represents a bijective map from Znq to itself and we can rewrite the event

hS (x0 ) = y0 ∧ . . . ∧ hS (xn−1 ) = yn−1

as
Vn S = y

5
 or
S = Vn−1 y.
Finally, being S uniform over Znq and being every y mapped into exactly one z = Vn−1 y ∈
Znq and vice versa, we have that

1
Pr [hS (x0 ) = y0 ∧ . . . ∧ hS (xn−1 ) = yn−1 ] = Pr S = Vn−1 y = Pr [S = z] =
 
.
|Zq |n

Corollary
Let q ≥ 3 be a prime. Then, the family

H3 = hs : Zq → Zq : x 7→ s0 + s1 x + s2 x2

s=(s0 ,s1 ,s2 )∈Z3q

is 3-wise independent.

Proof
It is a particular case of Proposition 2.3 with n = 3.

min-entropy.
Let X ∈ {0, 1}n be a (k, n)-source, let l = 128 and ε = 2−80 . By the Leftover Hash Lemma,
if the min-entropy of X is at least k,
 
1
H∞ (X) ≥ k ≥ l + 2 log − 2 = 128 + 2 · 80 − 2 = 286,
ε

so X has a min-entropy of 286 bits and an entropy loss of 2 log(1/ε) − 2 = 158 bits.

Suppose now that k = 238; the maximal amount of uniform randomness we can extract
from X with statistical error ε = 2−80 is
   
1
l ≥ k − 2 log − 2 = 238 − 158 = 80
ε

bits.
Missing: extension to 320 bits with computational assumptions.

3 One-Way Functions
Warning: I got 23/25, but I don’t remember what was wrong here (I assume something
imprecise or not well explained).
One-wayness of a PRG Let G : {0, 1}λ → {0, 1}λ+1 be a PRG with one-bit stretch and
prove that G is a OWF.

Use reduction to show that if G is not a OWF then it is not a PRG.

Suppose that a PPT adversary A owf can invert G with non negligible probability (i.e., G
is not a OWF). In particular, if the input to A owf is y = G(x), the output 0

will be x such
0 λ
that G(x ) = G(x) with non negligible probability and if y ∈ / G {0, 1} , the output will
be a symbol  ∈ / {0, 1}λ with non negligible probability.
Now construct an adversary A prg as follows: redirect every output from the challenger to
A owf . If A owf outputs some x ∈ {0, 1}λ , then A prg outputs “PRG” to the challenger (i.e.
he thinks that the number is generated from G); otherwise, A prg outputs “RAND” to the

6
challenger (i.e. he thinks that the number is truly random).

If the z received from the challenger is an output from G, A owf can invert G with non
negligible probability finding some x ∈ {0, 1}λ , then A prg can guess it to be an output
from G with non negligible probability. Otherwise, z is truly random and can be inverted
only about half of the times:


 λ

λ+1
 #G {0, 1}λ 1
Pr z ∈ G {0, 1} z ← ${0, 1} = = + ν(λ)
#{0, 1}λ+1 2
with ν ∈ negl(λ) (otherwise, G(Uλ ) could be distinguished from Uλ+1 ).
1
In conclusion, the output z = G(x) can be guessed with probability near to p(λ) and the
λ+1 1
output z ← ${0, 1} can be confused with z = G(x) with probability near to 2p(λ) and,
1 1
being p(λ) − 2p(λ) still not negligible, G would not be a PRG.

Therefore, an adversary A owf cannot exist and G is also a OWF.

Non-secrecy of a OWF On the other hand, let f : {0, 1}n → {0, 1}n be a OWF: then
the function
g : {0, 1}n+log(n) → {0, 1}n+log(n)+1 : (x, hji) 7→ (f (x), j, xj )
is also a OWF: given g(x), if a PPT adversary A could invert g finding (x0 , hj 0 i) such
that g(x, hji) = g(x0 , hj 0 i), A would have found in particular x0 such that f (x0 ) = f (x),
inverting the OWF f .

Now that we constructed the OWF g, for all i ∈ {1, . . . , n + log(n)} we can construct an
algorithm Ai as follows:
1. Ai gets the challenge to find x0 = x || hji given g(x0 );
2. if i > n, Ai outputs (g(x0 ))i = ji−n = x0i ;
3. if i ≤ n but i = j, Ai outputs (g(x0 ))n+log(n)+1 = xj = xi ;
4. if i ≤ n and i 6= j, Ai outputs b ← $({0, 1}).
Thus, for i > n, the probability to win for Ai is exactly 1; on the other hand, for i ≤ n we
have
Pr [Ai (g(X || hJi)) = x0i ]
= Pr [Ai (g(X || hJi)) = x0i ∧ i = J] + Pr [Ai (g(X || hJi)) = x0i ∧ i 6= J]
= Pr [Ai (g(X || hii)) = x0i ] Pr [J = i] + Pr [Ai (g(X || hJi)) = x0i | i 6= J] Pr [J 6= i]
1 1 2log(n) − 1
=1· +
2log(n) 2 2log(n)
1 1 11
= + −
n 2 2n
1 1
= + .
2 2n
Putting the two together, for all i ∈ {1, . . . , n + log(n)} it is possible to construct a PPT
algorithm Ai such that
1 1
Pr [Ai (g(X || hJi)) = x0i ] ≥ + ,
2 2n
thus breaking the randomicity of g (i.e. it is not possible to claim that every OWF hides
at least one specific bit of the input).

7
4 Pseudorandom Generators
Let G1 , G2 : {0, 1}λ → {0, 1}λ+l be two deterministic functions mapping λ bits into λ + l
bits (l ≥ λ + 1) and let at least one of G1 , G2 be a secure PRG. Then, we can construct a
secure PRG G∗ : {0, 1}2λ → {0, 1}λ+l by putting
G∗ (x1 , x2 ) = G1 (x1 ) ⊕ G2 (x2 ).
In fact, if G1 is a PRG, then
G∗ (Uλ , Uλ0 ) = G1 (Uλ ) ⊕ G2 (Uλ0 ) ≈c Uλ+l ⊕ Y ≈c Uλ+l ,
where Y = G2 (Uλ0 ). Otherwise, G2 must be a PRG and
G∗ (Uλ , Uλ0 ) = G1 (Uλ ) ⊕ G2 (Uλ0 ) ≈c X ⊕ Uλ+l ≈c Uλ+l ,
where X = G1 (Uλ0 ).
We cannot improve this particular construction to get a λ bit seed PRG because we don’t
know anything about the relation between G1 and G2 ; in particular, if G1 = G2 (or, more
in general, G1 and G2 have some bits in common), we get G∗ (x) = G1 (x) ⊕ G2 (x) = 0 (or,
more in general, the bits that G1 and G2 have in common will be 0 after the XOR).

5 Pseudorandom Functions
This answer contains only the idea of the solution because I am late for the due.
Missing: first part of the exercise is poorly explained.
Let F be a PRF family and consider a computationally unbounded distinguisher D. In
particular, D “knows” (can precompute) fk (x) for every x ∈ {0, 1}n , for everyk ∈ {0, 1}λ
and for every fk ∈ F.
The idea is that with a polynomial number of queries, D can restrict the domain (roughly
halfing it) and try to guess k if C is playing the RealF ,D game, thus answering Real;
otherwise (i.e. if D could not find a k), D answers Rand.

1. Let G be a λ to λ+l PRG and let G0 be the truncation of the output from G such that
G0 : {0, 1}λ → {0, 1}λ . Then, we can ask to compute Fk (0λ ) = G0 (k) ⊕ 0λ = G0 (k)
and then, for every other message m, Fk (m) = G0 (k) ⊕ m = Fk (0λ ) ⊕ m and, knowing
Fk (0λ ), we can recover the message m and distinguish Fk from a true random function.
2. Let Fs : {0, 1}λ → {0, 1}λ be a PRF for every s ∈ {0, 1}λ and consider Fx (k). The
idea is to construct a particular PRF family properly indexed to show that Fk (x) is
secure but Fx (k) is not, thus making not secure the construction.
3. Let Fk0 (x) = Fk (x || 0) || Fk (x || 1). Trying to break Fk0 consists in trying to break both
Fk (· || 0) and Fk (· || 1), thus if a distinguisher D 0 for Fk0 exists, we can construct a
distinguisher D for Fk as follows:
(a) D 0 sends x to D;
(b) D sends x || 0, receiving z0 , and x || 1, receiving z1 , to C ;
(c) D computes z = z0 || z1 and returns it to D 0 ;
(d) this is repeated a polynomial number of time;
(e) finally, D 0 responds either Real or Rand and D redirects the answer to C .
Now if D 0 can guess with non negligible probability between Fk0 and random, D can
guess with non negligible probability between Fk and random, thus breaking the PRF
Fk . Therefore, this construction is secure.

8
6 Secret Key Encryption
Both CBC and OFB have the same problem: flipping one bit in one ciphertext block, say
ck , can compromise the plaintext block mk and, eventually, mk+1 , but mk+2 and all the
following blocks will remain intact.

Let m = (m0 , m1 , m2 ), let k ← ${0, 1}λ and let h = 10n−1 (i.e. a block in which only the
first bit is set to 1).

Compute CBC.
Generate a random Initialization Vector c0 ← ${0, 1}n and compute

c1 = Pk (c0 ⊕ m1 ), c2 = Pk (c1 ⊕ m2 ), c3 = Pk (c2 ⊕ m3 ).

Suppose an attacker decides to alter the ciphertext as follows:

c00 = c0 , c01 = c1 ⊕ h, c02 = c2 , c03 = c3 .

Then, the decryption algorithm computes

m01 = Pk−1 (c01 ) ⊕ c00 , m02 = Pk−1 (c02 ) ⊕ c01 , m03 = Pk−1 (c03 ) ⊕ c02 ,

that is

m01 = Pk−1 (c1 ⊕ h) ⊕ c0 , m02 = Pk−1 (c2 ) ⊕ c1 ⊕ h, m03 = Pk−1 (c3 ) ⊕ c2 .

Now, m01 is completely destroyed since Pk is a PRP, but m02 = m2 ⊕ h and m03 = m3 .

CCA to CBC.
It suffices to generate the two messages m∗0 = (0n , 0n , 0n ) and m∗1 = (1n , 1n , 1n ) to get the
ciphertext c∗ from the challenger; then, ask the challenger to decrypt c0 = c∗ ⊕ (h, 0n , 0n ).
Finally, choose b0 corresponding to the message m∗b0 that has the third block unchanged
(i.e. choose b0 = 0 if c0 = (·, ·, 0n ) and b0 = 1 otherwise).

Compute OFB.
Generate a random Initialization Vector c0 ← ${0, 1}n and compute

c1 = m1 ⊕ Fk (c0 ), c2 = m2 ⊕ Fk (Fk (c0 )).

Suppose an attacker decides to alter the ciphertext as follows:

c00 = c0 , c01 = c1 ⊕ h, c02 = c2 .

Then, the decryption algorithm computes

m01 = c01 ⊕ Fk (c00 ), m02 = c02 ⊕ Fk (Fk (c00 )),

that is
m01 = c1 ⊕ h ⊕ Fk (c00 ), m02 = c2 ⊕ Fk (Fk (c0 )).
Now we have m01 = m1 ⊕ h, that is m1 with one bit flipped, and m02 = m2 .

CCA to OFB.
It suffices to generate the two messages m∗0 = (0n , 0n ) and m∗1 = (1n , 1n ) to get the
ciphertext c∗ from the challenger; then, ask the challenger to decrypt c0 = c∗ ⊕ (h, 0n ).
Finally, choose b0 corresponding to the message m∗b0 that has the second block unchanged
(i.e. choose b0 = 0 if c0 = (·, 0n ) and b0 = 1 otherwise).

9
7 Message Authentication
Let Π = (Tag, Vrfy) be a MAC and consider the following game:
Gameuf-cmva
Π,A (1λ ) : A −→ C

1. C chooses a random key k ← $K.

2. A can query any (polynomial in λ) number of times C in the following way:

• A can ask C to tag a particular message m (i.e. can ask Tagk (m));
• A can ask C to verify a particular couple (m, φ) (i.e. can ask Vrfyk (m, φ)).
3. A then decides to send (forge) a fresh couple (m∗ , φ∗ ) to C .

4. The output is 1 if and only if Vrfyk (m∗ , φ∗ ) = 1.

Definition 7.1
A MAC Π has unforgeability under chosen message and verification attacks if
h i
Pr Gameuf-cmva
Π,A (1λ ) ≤ ν(λ),

where A is a PPT adversary and ν is a negligible function in λ.

Theorem 7.2
If Π has unique tags (i.e. for every key k there is only one valid tag φ for each message
m), then UF-CMA and UF-CMVA are equivalent.

Proof
The implication UF-CMVA ⇒ UF-CMA is trivial; let’s prove that UF-CMA ⇒ UF-
CMVA under unique tag assumption.
Suppose Π to be UF-CMA but not UF-CMVA and suppose an adversary A trying to
Π,A . Use reduction: consider A
break Π playing Gameuf-cma v
able to break Π playing
GameΠ,A v and interfacing with A :
uf-cmva

A v ←→ A ←→ C uf-cma .

Let A v make all the queries:

• if A v asks for a Tag query, m is sent from A v to A , which redirects m to C obtaining

φ = Tagk (m) and sending it back to A v ;
• if A v asks for a Vrfy query, (m, φ) is sent from A v to A , which sends m to C
obtaining φ0 ; then, A compares φ and φ0 and responds 1 to A v if and only if φ = φ0 .
Note that this is the only operation to do to verify a tag because of tag uniqueness.

Now, A v should be able to forge a tag φ∗ for a message m∗ such that (m∗ , φ∗ ) is fresh and
Vrfyk (m∗ , φ∗ ) = 1 with non negligible probability; sending the pair (m∗ , φ∗ ) to A , the
situation is that A forged a message/tag pair using A v that is valid with non negligible
probability, therefore Π cannot be UF-CMA.

Things are different if Π has not unique tags, i.e. if exists some message m such that φ1 , φ2
are both valid tags but φ1 6= φ2 .

10
Example 7.3
Let Π = (Tag, Vrfy) be a MAC satisfying UF-CMA and construct a new MAC Π0 as
follows.
Let Tag0k (m) = Tagk (m) || 0log(λ) and define Vrfy0k :
• break φ0 = φ || hii, where hii is the binary representation of i;

• compute d0 = Vrfyk (φ);

• if d0 = 0 or i = 0, put d = d0 ;
• if d0 6= 0 and i 6= 0, put d = kj , where kj is the jth bit of k;
• let Vrfy0k (m, φ0 ) output d.

Now try to break Π0 = (Tag0 , Vrfy0 ).

As usual, show that Π0 is UF-CMA by reduction: let A be a UF-CMA adversary against
Π and let A 0 be a UF-CMA adversary against Π0 . The situation is the following:

A 0 ←→ A ←→ C .

For every message m queried by A 0 , A asks C for a tag, appends 0log(λ) to the result
and returns φ0 = φ || h0i to A 0 . Since these are the only queries available for A 0 , the
only other thing it can do is trying to forge a pair (m∗ , φ∗ ) and sending it to A . Note
that to win the game, A 0 must forge a tag such that d0 = 1; otherwise, the output d is
0 and the game is lost. The only possibility for d0 to be 1 is that, given φ0 = φ || h0i,
Vrfyk (m, φ) = 1, thus, if A 0 wins the game with non negligible probability, the same
happens for A and the initial MAC Π is not UF-CMA.

To break Π0 in a UF-CMVA game, it suffices for the adversary to query a message m ob-
taining a tag φ0 = φ || h0i and then asking the challenger to verify the tags (m, φ || hii) for
each i ∈ {1, . . . , n−1}, obtaining di . Since the verification queries are only n−1 ∈ poly(λ),
the adversary can effectively do all these queries. In particular, the adversary obtains
the bits k1 , . . . , kλ−1 . Finally, he can guess the first bit k0 trying to compute the tag for
a fresh message m0 and asking to verify φ00 = Tagk0 ||...||kλ−1 .

Now the adversary knows the key and can forge all the message he wants with probability
of success 1.

CBC-MAC.
Assume having a fixed length CBC-MAC that computes Tag using a PRF Fk as follows:
given a message m = (m1 , . . . , mt ), compute recursively

φi = Fk (mi ⊕ φi−1 ), where φ0 = 0n and i ∈ {1, . . . , t}.

• This MAC can’t be used to authenticate variable-length messages: given two messages
(m1 ) and (m1 , m2 ) and their relative tags φ1 = Fk (m1 ) and φ2 = Fk (m2 ⊕ Fk (m1 )),
it is possible to forge a tag φ∗ = φ2 for the message m∗ = m2 ⊕ φ1 = m2 ⊕ Fk (m1 ).
• A variant in which φ0 is randomized and output with the tag is not secure even for
fixed length messages: one can ask a tag for the message (m1 , . . . , mt ), obtaining
(φ0 , . . .), and forge the tag (φ0 ⊕ m1 , . . .) for the (fresh) message (0n , m2 , . . . , mt ).
Note that this security issue holds for both outputs (φ0 , φt ) and (φ0 , φ1 , . . . , φt ).

Missing: I interpreted this wrong: in the third variant, φ0 is not random but φ0 = 0n .
Anyway, this case is insecure too.

11