Instructions

Please either 1) typeset your answers in LATEX and submit a PDF file through Piazza, or else 2) write answers by hand and turn in a physical copy in class, 3) write answers by hand and send a scanned PDF file. We prefer to read succinct and precise answers. If you can be precise while being succinct with your answers, please try.

How multiple choice is graded. Multiple choice questions may have multiple correct answers.  If there are N multiple correct answers, then each correct answer is worth 1/N of the total points for the question. You lose 1/N points for every wrong answer you circle. The total cannot go negative.  In code, score = points * max(num correct – num wrong) / total correct

1 Indistinguishability [6 pts]

1. (3 pts) If {X_n}_n is computationally indistinguishable from {Y_n}_n, {Y_n}_n is computationally indistin- guishable from {Z_n}_n, then (select the one that is always correct)

(a) {X_n}_n is computationally indistinguishable from {Z_n}_n

(b) {X_n}_n can be distinguished from {Z_n}_n

(c) Sometimes {X_n}_n can be distinguished from {Z_n}_n, sometimes {X_n}_n is computationally indis- tinguishable from {Z_n}_n

2.  If X_n n can be distinguished from Y_n n, Y_n n can be distinguished from Z_n n, then (select the one that is always correct)

(a) {X_n}_n is computationally indistinguishable from {Z_n}_n

(b) {X_n}_n can be distinguished from {Z_n}_n

(c) Sometimes {X_n}_n can be distinguished from {Z_n}_n, sometimes {X_n}_n is computationally indis- tinguishable from {Z_n}_n

2 Useful Asymptotical Notations [6 points]

(No need to prove throughout this question.)

2.1 [2 pts]

Among the following functions in n, please select all that are negligible functions in n:

a. ¹2 b. 1

c. 1

d. n−3 e. n− log log log n f. 2n g. nlog log n

2n 2n

nlog log n

2.2 [2 pts]

Suppose that f₁(n), f₂(n) are negligible functions in n. Let g(n) denote some fixed polynomial in n. Which of the following must be negligible functions in n:

a. f₁(n) + f₂(n) b. f₁(n)f₂(n) c. f₁(n)g(n) d. g(n) e. √f₁(n) f. f₁(n)^g(n)

2.3 [2 pts]

(Let g₁(n), g₂(n) denote two fixed polynomials in n. Which of the following must be polynomial in n:

a. g₁(n) + g₂(n) b. g₁(n)g₂(n) c. g₁(n)^g2(n) d. g₁(n) + 203942 e. g₁(n) + 2ⁿ f. g₁(n)¹⁰⁰

g. 2g1(n)

3 Pseudorandomness [10 pts]

3.1 Pseudorandom Generators [5 pts]

Let tt : {0, 1}λ → {0, 1}λ be a PRG. Circle all PRGs below. (No need to prove)

a. tt^j(s) = if |s| > 1024 then tt(s) else 0^A(|s|)

b. tt^j(s₁ || s₂) = tt(s₁) ⊕ tt(s₂), where |s₁| = |s₂| = λ c. tt^j(s₁