CAS CS538: Cryptography. Spring 2023
March 15, 2023
Due: Monday 3/20, 10pm
Midterm Exam – take II
Question 1 (20 points):
For each one of the following statements, indicate whether it is correct or incorrect. Pleae explain your choice.
1. (6 points) It is possible to construct encryption schemes that are one time semantically secure and have a fixed (not random) key, as long as the scheme uses additional randomization during encryption.
2. (7 points) If f is a one-way function then there exists a negligible function ν such that for all feasible adversary A = {Aλ}λ∈N and for all large enough λ we have
Prob[x←$ {0,1}λ;r←$ {0,1}λ:Aλ(f(x),r)=⟨x,r⟩]<21+ν(λ)
(where ⟨x, r⟩ denotes the inner product of x and r, namely ⟨x, r⟩ = i=1...λ xiri mod 2, and xi is the ith
bitofxandri istheithbitofr).
3. (7 points) Let P = {Pλ} where Pλ : {0, 1}λ × {0, 1}λ → {0, 1}λ be a strong pseudorandom permutation family (SPRP). Let (Gen, Enc, Dec) be the following encryption scheme: Gen(1λ) outputs a random 2λ-bit key k = (k1,k2), and Enc((k1,k2),m) = r,P(k2,r) ⊕ m, where r = P(k1,m). Then (Gen,Enc,Dec) is SS-CPA secure.
Question 2 (20 points):
For each one of the statements below, state whether it is correct or not, and provide a proof of your claim. That is, either prove that the statement is correct or prove that the statement is incorrect.
1. (10 points) There exists a constant c > 0 and a one way function of the form f : {0, 1}∗ → {0, 1}c (i.e. the output length of f is c bits).
2. (10 points) Let (Gen, Auth, V er) be an EU-CMA MA scheme, where Auth is deterministic. Then it is possible to construct an algorithm V er′ such that (Gen, Auth, V er′) is a strong EU-CMA MA scheme.
Question 3 (30 points): You have two length-doubling functions G1, G2 : {0, 1}∗ → {0, 1}∗.
1. Construct a length-doubling function G3 : {0, 1}∗ → {0, 1}∗ such that G3 is a PRG as long as at least one
outofG1,G2 isaPRG.
2. Prove the validity of your construction by constructing one of more reductions that transform an adversary that breaks the security of G3 into adversaries that break the security of either G1 or G2. Argue why the reductions prove your claims.
Question 4 (40 points): You have three EU-CMA message authentication schemes, (Gen1, Auth1, V er1), (Gen2,Auth2,Ver2) and (Gen3,Auth3,Ver3), all for message domain M.
1. Construct a schene (Gen4 , Auth4 , V er4 ) that withstands a single faulty scheme out of the three. That is, the constructed scheme should remain correct and EU-CMA as long as two of the three underlying schemes are correct and EU-CMA.
2. Prove validity of your construction. (It is stressed that the faulty scheme can be neither correct nor EU- CMA.) Prove the validity of your construction by constructing one of more reductions that transform an adversary that breaks either correctness or EU-CMA of the constructed scheme into adversaries that break the correctness or EU-CMA of two of the underlying schemes. Argue why the reductions prove your claims.
3. bonus (10 points): You now have only two EU-CMA message authentication schemes, (Gen1, Auth1, V er1) and (Gen2 , Auth2 , V er2 ), for message domain M , and you are tasked to Construct a scheme (Gen3 , Auth3 , V er3 ) that remains correct and EU-CMA as long as one of the two underlying schemes is correct and EU-CMA. (The other one can be neither correct nor EU-CMA.)
Code Help, Add WeChat: cstutorcs