CS 171 2021 Midterm 1 Solutions. Questions and answers complete solved solution

CS 171 2021 Midterm 1 Solutions. Questions and answers complete solved solution UC Berkeley — CS171 : Undergraduate Cryptography Midterm I Prof. Sanjam Garg September 22, 2021 Midterm I Name: SID: • Try to answer all questions. Not all parts of a problem are weighted equally. Before you answer any question, read the problem carefully. Be precise and concise in your answers. • You may consult at most 10 sheets of notes. Apart from that, you may not look at books, notes, etc. Calculators, phones, computers, and other electronic devices are NOT permitted for looking up content. However, you may use an electronic device such as a tablet for writing your answers. • You have 80 minutes: there are 5 questions on this exam worth a total of 100 points. • You are allocated 90 minutes and the extra 10 minutes are provided for the submission of the exam on Gradescope. You must submit/upload the exam on time. Note that late submissions will not be accepted. • DSP Students must submit the exam in time as per your accommodation. Thus, if you are allowed 1.5× (resp., 2×) the exam time then you must submit it within 80 ∗ 1.5 + 10 (resp., 80 ∗ 2 + 10) mins, i.e. 130 (resp., 170) mins. Please make your submission via email to both and using the subject “CS 171: Midterm 1 DSP Submission.” • The exam must be submitted before 8 PM PT on Feb 22nd, 2021. No exams later than this time will be accepted regardless of when you start the test. • We will not be answering questions during the exam. If you feel that something is unclear please write a note in your answer. 1 True/False (20 points) Bubble in the right answer. No explanation needed. +2 points for correct answer and -1 points for wrong answers! If you leave a question unan- swered, then there is no penalty. This part will be graded automatically. Please mark your answer clearly. 1. Let f : {0, 1}n×{0, 1}n → {0, 1}n be a pseudorandom function. Then, fkJ (x, y) = fk(x)ǁx ⊕ fk(y) is a pseudorandom function. True False 2. f (n) = 2− log2 n n is odd 2−n n is even is a non-negligible function. True False 3. Consider an encryption scheme where ciphertexts contain no information about the secret key. Then, the scheme must be CPA-secure. True False 4. A mult-secure encryption scheme is also CPA-secure. True False 5. Consider a variant of the mult security definition called mult-(+1) where the adversary is additionally allowed a single phase-2 encryption query. Any encryption scheme that is mult secure is also mult-(+1) secure. True False 6. The number of permutations from {0, 1}n to {0, 1}n is (2n)!. True False 7. There exists a perfectly secure encryption scheme such that Enc(k, m) = m with non-zero probability. True False 8. Let g : {0, 1}l → {0, 1}m, f : {0, 1}m → {0, 1}n be two functions such that one of them is a pseudorandom generator. Then, f (g(•)) is a pseudorandom generator. True False 9. Let gk : {0, 1}l → {0, 1}l, fs : {0, 1}l → {0, 1}l be two functions such that one of them is a pseudorandom function and the other one is a permutation (i.e., a bijective function). Then, fs(gk(•)) is a pseudorandom function. True False 10. Let gk : {0, 1}l → {0, 1}m be a pseudorandom function and f : {0, 1}m → {0, 1}n be a pseudorandom generator. Then, f (gk(•)) is a pseudorandom function. True False 2 Pseudorandom Generators (25 points) Let g : {0, 1}n → {0, 1}n+1 be a psuedorandom generator with stretch 1 (that is, its output is 1 bit longer than its seed). We will show how to construct from g a PRG f : {0, 1}n → {0, 1}n+2 with stretch 2. First, we will show an insecure attempt at expanding the stretch, and then you will be asked to demonstrate a secure method of expanding the stretch. 1. Consider the following attempt at defining f . On input seed s ∈ {0, 1}n, f computes t := g(s) and then outputs (t1, g(t1,...,n)) ∈ {0, 1}n+2, where t1 is the first bit of t, and t1...,n are the first n bits of t. We will construct a PRG g for which f as defined above is not a PRG. (a) Using a PRG h : {0, 1}n−1 → {0, 1}n, construct a g : {0, 1}n → {0, 1}n+1 for which f as defined above is not secure. Below, write a description of g, and argue that the resulting f is not a secure PRG. (5 points) (b) Prove that the g you specified above is a secure PRG, assuming that h is a secure PRG. (5 points) 2. Now, assuming that g : {0, 1}n → {0, 1}n+1 is a PRG, define and prove the security of a PRG f : {0, 1}n → {0, 1}n+2. (15 points) 3 CPA Security (20 points) Consider the following variants of CPA security. Weak-1-CPA is the same as CPA security, except that the adversary is only allowed exactly 1 phase-1 query. Weak-2-CPA is the same as CPA security, except that the adversary is only allowed exactly 2 phase-1 queries. Assuming the existence of a CPA-secure scheme (Gen, Enc, Dec), construct a scheme (GenJ, EncJ, DecJ) that provably satisfies Weak-1-CPA security but does not satisfy Weak-2-CPA security, 1. Define your scheme (GenJ, EncJ, DecJ) and argue that it does not satisfy Weak-2-CPA security. (10 points) 2. Prove that your scheme satisfies Weak-1-CPA security. (10 points) 4 Double Encryption (20 points) 1. Give an example of an PrivKeav secure scheme (Gen, Enc, Dec) such that the scheme (GenJ, EncJ, DecJ) is not PrivKeav secure, where GenJ = Gen, EncJ(k, m) = Enc(k, Enc(k, m)), and DecJ(k, c) = Dec(k, Dec(k, c)). (10 points) 2. Prove that for any CPA-secure scheme (Gen, Enc, Dec), the scheme (GenJ, EncJ, DecJ) where GenJ = Gen, EncJ(k, m) = Enc(k, Enc(k, m)), and DecJ(k, c) = Dec(k, Dec(k, c)) is also CPA- secure. (10 points) 5 Fill in the Blanks (15 points) 1. How many functions are there from log2(n) bits to n2 bits? (5 points) 2. Let Π = (Gen, Enc, Dec) be a CPA-secure encryption scheme. Construct a CPA-secure en- cryption scheme ΠJ that is not CCA-secure. Do not use any other crytographic primitives (e.g. PRG,PRF) in your construction. Provide a brief explanation for why the scheme is not CCA-secure. (5 points) 3. Show that CBC mode encryption is not CCA-secure. (5 points)