Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CSEC5619: Homework 1
It will be highly suggested to use LaTeX or MS Word to type in your answer; if you have to scan your handwriting, please ensure it is clearly recognizable.
Q1. (10 points) Let Enc(k, m) be a perfect secure encryption, define Enc′
((k1, k2), m) := (Enc(k1, k2), Enc(k2, m)). Whether it is still perfect secure? Briefly explain.
Q2. (5 points) Decide whether the following functions are suitable to characterize small failure prob ability in cryptographic schemes, and explain briefly.
(a) 1000−99999
(b) 1000− log2n
(c) n89347/3n
(d) e − log2n1000
(e) n − log2n
Q3. (10 points) A good pseudorandom generator G : {0, 1}
100 → {0, 1}
200 is used to stretch a short random seed to be a longer pseudorandom string. (1) Due to the nice property of pseudorandomness, we can easily adapt it to another pseudorandom generator that extends 200-bit seed to 300 bits. For example, for a uniform bit string x = x0∥x1 where x0 and x1 are k-bit strings and ∥ denotes string concatenation, define G1(x) := G(x0)∥x1. G1 is not a secure PRG. Is it correct? (2) Would G1 be a secure PRG if the seed is not uniform? If yes, briefly explain. If not, could you give a counter-example?
Q4. (10 points) A one-way function is a function F : {0, 1}
n → {0, 1}
n that is easy to compute but hard to invert. Namely, for any polynomial-time adversary A, given y = F(x) where x is uniformly chosen, the probability of A finding x
′ ∈ {0, 1}
n such that F(x
′
) = y is negligible. Given a one-way function F : {0, 1}
n → {0, 1}
n and an arbitrary function G : {0, 1}
n → {0, 1}
n not one-way, decide whether G(F(X)) is a one-way function and briefly explain. How about F(G(X))?
Q5. (10 points) G : {0, 1}
n → {0, 1}
m is a PRG (n < m). We define Fk(x) = G(k) ⊕ H0(x), where k ∈ {0, 1}
n, x ∈ {0, 1}
m, and H0(·) is to apply a complex function, such as a hash, and mapping an m-bit to a longer 2m-bit, and then output the first half m bits. Is Fk(·) a PRF? If yes, explain why; if not, give an explicit attack (a PPT adversary that violates the definition)
In practice, it is often the case that good block ciphers such AES (or some carefully designed hashes such as SHA256) are assumed to be a PRF. However, block cipher, by name, works on a fixed length of blocks, e.g., AES works on 128-bit messages only. The following are two possible ways to adjust the input/output length of a PRF:
Q6. (10 points) Given a PRF E : K × {0, 1}
n → {0, 1}
m, we construct F1 : K × {0, 1}
n−1 → {0, 1}
2m as follows: F1(K, x) := E(K, x∥0)∥E(K, x∥1). Is F1(K, ·) still a PRF? If yes, give a brief proof; if not, give a brief attack showing the violation of the PRF definition.
Q7. (10 points) Given a PRF E : {0, 1}
n × {0, 1}
n → {0, 1}
m, we construct F2 : {0, 1}
2n × {0, 1}
2n → {0, 1}
m as follows: F2(K, x) := E(K1, x1)⊕E(K2, x2), where K = K1∥K2 and x = x1∥x2. Is F2(K, ·) still a PRF? If yes, give a brief proof; if not, give a brief attack showing the violation of the PRF definition.
Q8. (10 points) Friend-or-Foe. Suppose one Sydney police auto-drive car is racing with a criminal that drives a car looks the same (the criminal car was painted so as camouflage), the policy department is sending other auto-drive police cars to block the criminal, and they see two police cars rushing towards them, they need to shoot at the tires of the criminal car to stop him. Assume all the real police cars of Sydney pre-installed a same master key k, the criminal’s car only looks similar but does not have this key. Design a simple identification protocol, e.g., challenge-response using some tool you have studied so far (one of PRG, PRF, SE, OTP) to help the police cars to identify real police, and briefly explain.
Q9. (15 points) Consider the following situation, a movie/content distribution center needs to gener ate a secret key for each subscriber (user), so that the distribution center can select any subset of users to send encrypted copies of the movie/content according to user’s subscription plan.
The movie server as a key distribution center first chooses a uniformly random master key mk ← K, from a key space K. For subscriber i, suppose his user name is idi (assuming it is unique), and the movie server will use some method to generate a secret key ki for him. If user i paid and obtained the subscription key ki
, the movie distribution center will use ki as the secret key and encrypt the movie to user i for what he subscribed.
(1) Design an efficient key distribution method so that (i) the key distribution center only keeps one master secret key mk; (ii) subscriber i cannot decode the content sent to subscriber j. And briefly explain why it is secure. (Hint: use one cryptographic tool that we introduced that suits this purpose.)
(2) Suppose the content distribution center only deals with 100 CDN servers (as intermediary proxy), which directly face real users and distribute both contents and keys. How could we improve the above design to support this two-level key distribution while still keeps every entity (center and CDN servers) to store only one secret key? (Note that the center never share its mk.)
Q10. (10 points) In some settings, the movie distribution center may only delegate the subscriber management (i.e., the user key distribution) to some proxies. However, since the master secret of the movie distribution center is critical for the security of the whole system, delegating it to a single proxy is a bit too risky (as the proxy can simply get the secret key and decrypt everything).
Can you generalize your idea in Q9 and design a key derivation method such that there are three proxy servers, and only when a user obtains shares from at least two of them user i can obtain a valid secret key ki? But any single share (or any single proxy) is not sufficient. Also, users can never reconstruct the secret keys of either the proxy or the content distribution center. Moreover, please pair the key derivation with a proper encryption algorithm to actually enable the secure content distribution to users (the movie distribution server encrypts/encodes the movie and sends some ci to the user i), and describe the ci generation procedure, assuming you have some secure encryption library Enc(key, message) to use already.