Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CAS CS538: Cryptography
Midterm Exam - take
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⟩] < 1
2
+ ν(λ)
(where ⟨x, r⟩ denotes the inner product of x and r, namely ⟨x, r⟩ =∑i=1...λ xiri mod 2, and xi is the ith
bit of x and ri is the ith bit of r).
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
out of G1, G2 is a PRG.
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, V er2) and (Gen3, Auth3, V er3), 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-CMAmessage authentication schemes, (Gen1, Auth1, V er1)
and (Gen2, Auth2, V er2), for message domainM , 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.)