COMP0025: Introduction to Cryptography
Practice Exam
Department of Computer Science
University College London
Question 1: Hash Functions [25 marks]
(a) Consider the hash function H : {0, 1}256` → {0, 1}256 defined by H(m1, . . . ,m`) = m1⊕. . .⊕m`.
Describe an adversary that on input m = (m1,m2) performs a successful second-preimage attack.
[5 marks]
(b) SnakeOil Ltd is suggesting a super fast hash function H : {0, 1}? → {0, 1}100 defined by H(x) =
7x+5 mod 2100. Describe an attack that finds a second-preimage for any message x. [5 marks]
(c) Given a collision-resistant compression function f : {0, 1}512 → {0, 1}256, we define a hash
function H : {0, 1}? → {0, 1}256 as follows:
(a) On input x pad it with 0 . . . 0 such that it has length 256n.
(b) Let xi be the ith 256-bit block of the padded x ‖ 0 . . . 0.
(c) Let z0 = 0
256 and zi = f(zi?1 ‖ xi) for i = 1, . . . , n.
(d) Return zn as the output H(x).
Is this construction collision-resistant? Why or why not? [5 marks]
(d) Let p, q be two large prime numbers such that p = 2q + 1 and let g, h be two random group
elements in Z?p. The function H : Zp?1 × Zp?1 → Z?p defined by
H(x, y) = gxhy mod p
is a hash function mapping (p? 1)2 possible inputs to p? 1 possible outputs. Unfortunately, H
is not collision-resistant. Argue why not. [5 marks]
Hint: You may use the fact that half of the elements in Z?p have order q.
(e) Let p, q bet two large prime numbers such that p = 2q + 1 and let g, h ∈ Zp bet two random
generators for the order q subgroup G ? Z?p. Define the hash function H : Zq × Zq → G by
H(x, y) = gxhy mod p
Show that H is collision-resistant if the discrete logarithm is hard in G. [5 marks]
1
Question 2: Message Authentication Codes [25 marks]
(a) Consider the following one-time message authentication code for 10-bit messages.
Key generation: The secret key is sk = (a, b) where a, b $←? Z1031 are picked at random
(1031 is a prime).
Authentication: To authenticate a message m compute the authentication tag t = am+
b mod 1031.
Verification: To verify an authentication tag t on a message m check whether t = am +
b mod 1031.
Consider an adversary that does not know anything about the secret key but does learn one pair
(m, t) of an arbitrary message and its corresponding authentication tag. What is the probability
that the adversary can find a different message m′ and its corresponding tag t′? [5 marks]
(b) Consider the following message authentication code for 128-bit messages built from AES encryp-
tion function E.
Key generation: Pick a 128-bit secret key k.
Authentication: Given a message m compute the authentication tag t = Ek(m).
Verification: To verify an authentication tag t on message m check whether t = Ek(m).
Assume Ek were a truly random permutation of 128-bit strings. Suppose the adversary learns
pairs of messages and authentication tags (m1, t1), . . . , (m1024, t1024) for 1024 different messages
of its own choosing. What is the probability that it can find a new message m /∈ {m1, . . . ,m1024}
and guess the corresponding message authentication tag t? [5 marks]
(c) Recall that NMAC and HMAC are message authentication codes built from a Merkle-Damgard
type hash function such as for instance SHA256. HMAC computes the message authentication
code as HMAC(k,m) = H(k⊕ opad ‖ H(k⊕ ipad) ‖ m) whereas NMAC computes the message
authentication code as NMAC(k,m) = Hk1(Hk2(m)) with k = (k1, k2). What is an advantage
of NMAC over HMAC and an advantage of HMAC over NMAC? [5 marks]
(d) Consider CBC-MAC for 128`-bit messages with fixed `. We use AES as the underlying block
cipher with 128-bit keys. Let E be the AES encryption function.
Key generation: Pick a 128-bit secret key k.
Authentication: Given a message m = m1 ‖ · · · ‖ m` where m1, . . . ,m` are 128-bit
blocks define t0 = 0 and compute t1, . . . , t` recursively as ti = Ek(ti?1 ⊕mi). Output the
authentication tag t = t`.
Verification: To verify an authentication tag t on a 128`-bit message m compute t` as
above and accept if t = t`.
Suppose we modify CBC-MAC to allow for both 128-bit messages and 256-bit messages by
outputting t = t1 or t = t2. Show that it is possible to forge an authentication tag on a 256-
bit message by combining the authentication tags for two adaptively chosen 128-bit messages.
[5 marks]
(e) Give a formal definition of existential unforgeability for message authentication codes under adap-
tive chosen message attacks. Explain in your own words what the definition means. [5 marks]
2
Question 3: Digital Signatures [25 marks]
(a) A digital signature scheme (Gen,Sign,Verify) is said to be secure if for all probabilistic polynomial
time adversaries A we have
Pr[(vk, sk)← Gen(1λ); (m,σ)← ASignsk(·)(vk) : m /∈ Q ∧ Verifyvk(m,σ) = 1] = negl(λ)
where Q is the set of messages that has been queried to the signing oracle Signsk(·). What is the
name of the security definition? Explain in non-mathematical terms what the goal of the adversary
is in the security definition. Explain in non-mathematical terms what access the adversary has to
the signature scheme in the security definition. [5 marks]
(b) We say p is a safe prime if p = 2p′ + 1 and both p and p′ are primes. Consider an RSA modulus
N = pq where p = 2p′+1 and q = 2q′+1 are two different safe primes. The group of quadratic
residues QRN are the elements y ∈ Z?N for which there exists a z such that y = z2 mod N . The
size of QRN is p′q′. What is the size of Z?N? Show that Z?N is not cyclic. Show that QRN is
cyclic. [5 marks]
Hint: You may want to use the Chinese Remainder Theorem and the fact that Z?p and Z?q are
cyclic when p and q are prime.
(c) Camenisch and Lysysanskaya proposed a signature scheme in 2002. A variant of the CL signature
scheme for `m-bit messages works as follows (for suitable choices of `e > 2λ and `r defined in
their paper):
Gen(1λ): Pick two random λ-bit safe primes p and q. Let N = pq and pick at random
a, b, c ∈ QRN . Return the verification key vk = (N, a, b, c) and the secret key sk = (p, q).
Sign(sk,m): To sign an `m-bit message m pick at random a prime 2`e < e < 2`e+1
and additional randomness r
$←? {0, 1}`r . Compute a value s ∈ QRN such that se =
abmcr mod N . Return the signature σ = (e, r, s).
Verify(vk,m, σ): To verify a signature σ on an `m-bit message m check that e > 2`e is a
prime, check that r ∈ {0, 1}`r and check that se = abmcr mod N .
Let vk = (77, 4, 9, 25) be a CL signature scheme verification key. Find the secret key and compute
a CL signature on m = 3 using randomness (e, r) = (103, 8). [5 marks]
Hint: To speed up the calculations, do them modulo p and modulo q and use the Chinese
Remainder Theorem.
(d) Show that if you can guess in advance the number of signing queries t that the adversary will
make, then you can simulate the verification key and simulate the signatures without knowing
the factorization of N . [5 marks]
Hint: Given N pick at random y = z2 mod N . Generate t random primes e1, . . . , et ∈
{2`e , . . . , 2`e+1}. Define E = ∏tj=1 ej and Ei = E/ei. Pick at random α, β $←? {0, 1}3λ.
Let a = yαE mod N , b = yβE mod N , and c = yE mod N .
(e) The strong RSA assumption says that given a safe prime RSA modulus N and a random element
y ∈ QRN , it is hard to find an x ∈ Z?N and an exponent e > 1 such that y = xe mod N .
Consider an adversary At that obtains exactly t signatures (e1, s1, r1), . . . , (et, st, rt) on messages
m1, . . . ,mt in adaptive chosen message attacks and then forges a CL signature σ = (e, s, r) on
a message m /∈ {m1, . . . ,mt} using a prime e /∈ {e1, . . . , et}. Show that such an adversary can
be used to break the strong RSA assumption. [5 marks]
Hint: Write α = α′p′q′ + [α mod p′q′] over the integers. Observe that no information about α′
is leaked when simulating signatures given that gcd(e, α+ βm+ r) = 1 with high probability.
3
Question 4: Private Information Retrieval [25 marks]
In Private Information Retrieval (PIR) a server holds a database of n bits (x1, . . . , xn) and a client
wants to learn the bit xi without revealing the queried index i to anybody else. A naive way to do PIR is
to have the server sending the entire database (x1, . . . , xn) to the client. The client can then extract xi
without revealing the index i to anybody. However, the naive solution requires n bits of communication.
This question is about the Gentry-Ramzan PIR protocol that allows the client to privately extract a bit
from the database using less than n bits of communication with the server.
(a) Let p = 2pir + 1, q = 2s+ 1, and N = pq where 2, pi, r, s, p, and q are different primes. What
is the size of the multiplicative group Z?N? What is the maximal order an element g ∈ Z?N can
have? [5 marks]
(b) Define pi1, . . . , pin to be the first n primes larger than 2n. The Gentry-Ramzan PIR protocol
works as follows:
Query(1λ, i): Send (N, g) to the server, where N is a λ-bit RSA modulus and g ∈ Z?N is a
random element of order piit.
Respond(N, g, x1, . . . , xn): Compute x so that x = xj mod pij for all 1 ≤ j ≤ n. Send
c = gx mod N to the client.
Extract(c): Return 0 if 1 = ct mod N otherwise return 1.
Show that the Gentry-Ramzan protocol is correct, i.e., if both the client and the server are honest,
then the client outputs the desired xi in the extraction steps. [5 marks]
(c) In the protocol given above, the client computes ct mod N which in the worst case requires
approximately 2λ multiplications modulo N . Suggest a way to speed up the client’s computation
in the extraction phase. [5 marks]
(d) We say the protocol is computationally private if for all probabilistic polynomial-time adversaries
A we have
|Pr[i← A(1λ); (N, g)← Query(1λ, i) : A(N, g) = 1]
Pr[i← A(1λ); (N, g)← Query(1λ, 1) : A(N, g) = 1]| ≤ negl(λ)
where A outputs 1 ≤ i ≤ n. What access does the adversary have to the client’s desired index?
What is the adversary’s goal in this definition? How does the definition capture the notion of
privacy for the client? [5 marks]
(e) The client may without the server’s knowledge modify the Query and Extract protocols such that
it can extract two bits xi, xj from the database. How can this be done? [5 marks]