INFR11131 INTRODUCTION TO MODERN CRYPTOGRAPHY
April 2020
13:00 to 15:00
现代密码学代考 Give a definition of a PRF using this experiment, and prove that your defi- nition is equivalent to the definition of a PRF presented in class
INSTRUCTIONS TO CANDIDATES
- Answerany TWO of the three If more than two questions are answered, only QUESTION 1 and QUESTION 2 will be marked.
- Allthree questions carry equal total weight of 25 marks.
- Thisis an OPEN BOOK examination
THIS EXAMINATION WILL BE MARKED ANONYMOUSLY
1. Symmetric-key Cryptography 现代密码学代考
1.1(Pseudorandom Functions) Let Fkbe a keyed function and consider the [10 marks] following experiment:
Definition 1 The PRF indistinguishability experiment PRFA,F (n):
1 A uniform bit b ∈ {0, 1} is chosen.
If b = 1 then choose uniform k ∈ {0, 1}n.
2 A is given 1nfor input.
If b = 0 then A is given access to a uniform function f . 现代密码学代考 If b = 1 then A is instead given access to Fk.
3 A outputs a bitbj.
The output of the experiment is defined to be 1 if bj= b, and 0
Give a definition of a PRF using this experiment, and prove that your defi- nition is equivalent to the definition of a PRF presented in class:
Definition 2 F is a pseudorandom function if Fk, for uniform key k 0, 1 n, is such that for all PPT distinguishers A:
|Prk←{0,1}n [AFk (·) = 1] − Prf←Fn [Af(·) = 1]| ≤ s(n)
1.2(Mode of Operation) Does CTR mode of operation yield a CCA-secure en- [5 marks] cryption scheme (assuming that the underlying PRF F is secure)? Proveor give an attack. 现代密码学代考
1.3(Message Authentication Codes) Let F be a PRF. Let Gen output a uniform [10marks]k 0, 1 n and let n be even. By i denote an n/2-bit encoding of the integer i. Consider the following MAC: to authenticate a message m = m1, . . . , ml, where mi ∈ {0, 1}n/2, choose uniform r ← {0, 1}n, compute
t = Fk(r) ⊕ Fk((1)||m1) ⊕ . . . ⊕ Fk((l)||ml),
and let the tag be (r, t). Is this a secure MAC? Prove or demonstrate an attack.
2. Public-key Cryptography 现代密码学代考
2.1(ElGamal)
Consider the following modification of the ElGamal encryption scheme. The key generation algorithm is as in ElGamal: a group generation algorithm on input 1n outputs the description of a cyclic group G, its order q and a generator g. For a uniformly chosen x Zq the private key is (G, q, g, x) and the public key is (G, q, g, h), where h := gx.
A message M is encrypted by choosing a uniform r ∈ Zq and computing
c = (gr, hr · gM ) .
(a)How can the receiver compute gMfrom c? [5 marks] 现代密码学代考
(b)Computing discrete logarithms is hard relative to . In general, the receiver is not able to recover M from gM. Assume the sender only sends messages from the set 1, . . . , 100 . Show that the receiver can recover M . [8 marks]
(c)Supposec1 = (gr1 , hr1 gM1 ) is a ciphertext for unknown message M1 and c2 = (gr2 , hr2 · gM2 ) is a ciphertext for unknown message M2. Find a ciphertext c for a message M = M1 + M2 mod q using c1 and c2. [5 marks]
2.2(Keyexchange) Consider the following key-exchange protocol: [7 marks]
(1)Alice chooses uniform k, r ∈ {0, 1}r, and sends s := k ⊕ r to Bob.
(2)Bob chooses uniform t ∈ {0, 1}n, and sends u := s ⊕ t to Alice.
(3)Alicecomputes w := u ⊕ r, and sends w to Bob.
(4)Alice outputs k and Bob outputs w ⊕t.
Show that Alice and Bob output the same key. Analyze the security of the scheme (i.e., either prove its security or show a concrete attack).
3. Symmetric-key and Public-key Cryptography 现代密码学代考
3.1 (EAV- and CPA-secure encryption) Let F be a PRF, and G a PRG with [4 marks] expansion factor l(n) = n + For each of the following encryption schemes,state whether the scheme is: (1) EAV-secure and (2) CPA-secure, while providing supporting arguments (not necessarily a proof). In each case, the shared key is a random k ∈ {0, 1}n.
(a)To encrypt m ∈ {0, 1}n+1, choose uniform r ∈ {0, 1}n and output c = (r, G(r) ⊕ m) as the ciphertext.
(b)To encrypt m ∈ {0, 1}n, output the ciphertext m ⊕Fk(0n).
3.2 (a) (Hash functions) Let (Gen, H) be a collision-resistant hash function. Is [4marks] (Gen, Hˆ ) defined by Hˆ (x) = H(H(x)) necessarily collision resistant?
Prove or demonstrate an attack. 现代密码学代考
(b) (Pseudorandom Functions) Consider the following keyed function F : for [7 marks] security parameter n, the key is an n n boolean matrix A and an n-bit
boolean vector b. Define:
FA,b : {0, 1}n ›→ {0, 1}n : FA,b(x) = Ax + b ,
where all operations are done modulo 2. Is F a PRF? Prove or give an attack.
3.3(Keyexchange) Diffie-Hellman (DH) is a key exchange protocol for two par- [10 marks] ties, that works in one round. Describe a two-round key exchange protocol for three parties based on the same idea as DH. Namely, the three par- ties A, B, C choose private values x, y, z respectively, and at the end of the protocol execution they all agree on a key gxyz.
