Q3.   (10 points) A good pseudorandom generator G : {0, 1}k  → {0, 1}2k  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 have another pseudorandom generator that takes 2k-bit seed to extend to 3k. 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. Briefly explain G1  is still a secure PRG; (2) Would G1 still 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 Hk (x) = G(k) ⊕ x, where k ∈ {0, 1}n and x ∈ {0, 1}m , is Hk ( ·) 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 to help the police cars to identify who is real police, and briefly explain.