Clarity, succinctness, writing your name and Netid:

1 Indistinguishability

1. 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.1 Useful Asymptotical Notations

(No need to prove throughout this question.)

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

a. 1/2n² b. 1/2ⁿc. 1/nloglog n d. n^-3 e. n-^{log log log n} f.2ⁿ g. n^{log log n}

2.2 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)

(Let g1(n), g2(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)g₂(n) d. g₁(n) + 203942e. g₁(n) + 2n f. g₁(n)100 g.₂ g₁(n)

3 Pseudorandomness

Pseudorandom Generators

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

a. G'(s) = if |s| > 1024 then G(s) else 0^l(|s|)

b. G'(s₁ || s₂) = G(s₁) ⊕ G(s₂), where |s₁| = |s₂| = λ

c. G'(s₁ || s₂) = G(s₁) ∨ G(s₂), where |s₁| = |s₂| = λ

d. G'(s₁ || s₂) = s₁ || G(s2), where |s₁| = |s₂| = λ

e. G'(s) = s || G(s)

3.2 Pseudorandom Functions

Let the collection of functions F = {f_k}_k∈{0,1}∗ be a PRF family where f_k is a function from {0, 1}^λ → {0, 1}^λ when |k| = λ. Define G = {g_k} k∈{0,1}, where g_k is a function from 0, 1 defined as follows:

g_k(x) = f_k(x) ⊕ f_k (REVERSE(x)), → {0, 1}λ

when |k| = λ and

gk(x) = fk(x) ⊕ fk(REV ERSE(x)),

where REV ERSE(x) means the reversed version of the string x.

Prove that G is not a PRF family.

You need to construct an adversary D that for every λ can tell apart a random function selected from from a random function selected from the set of all functions from {0, 1}^λ →{0, 1}^λ. Recall that an adversary only gets input/output access to the function and by appropriately querying the function on certain inputs, it should be able to distinguish gk from a truly random function.

Hint: For any k, find two inputs on which gk's output will be the same. Then you can conclude that the same can not hold for a truly random function except with very small probability and hence the distinguisher can tell apart gk from a random function by just querying these points and checking if they are equal.

4 Group Theory

Identifying Groups

Which of the following are groups? Circle them. (No need to prove.)

a.( {0, 1}^λ, ||), where {0, 1}λ is the set of λ-bitstrings and || denotes concatenation

b.( R^λ×λ, ), where Rλ×λ is the set of all λ λ matrices over real numbers, and the operation is matrix multiplication

c.( Z - {0}, ×), where Z - {0} is all the integers except for 0

d.( A×B, *), where (A, +) and (B, ×) are groups, A×B is their cartesian product, and (a₁, b₁)>(a₂, b₂) = (a₁ + a₂, b₁ × b₂)

4.2 Subgroups

ED25519 is a popular elliptic curve used in cryptography. Let's define G as the group of points (x, y) lying on this curve. The order of ED25519 is not prime. Instead, |G| = 2³.p, where p is a large prime number. We usually do cryptography in a prime-order subgroup Gj, where |Gj| = p.

1. Suppose you are given a point g ∈ G. Give an efficient algorithm to determine the order of g, and prove it works for any g. (Hint: Use Lagrange's theorem to discuss the possible values of |g|.)

2. Bob and Mallory are going to use Diffie-Hellman key exchange. Bob's secret is b. Mallory convinces Bob that her public key is M. Bob forgets to check whether M ∈ G', and in fact Mallory chose M so that the order is actually |M| = 8. Bob sends Mallory an encrypted message, c = hello⊕PRF_k(1) where k = H(M^b) is the shared secret, H is a hash function, P RF is a pseudorandom function. Show how Mallory can learn a few bits of information about b. (Hint: look up "small subgroup attack")

5 Interactive Proofs

This question involves a variant of the Sigma protocols for Zero Knowledge Proofs discussed in class. You'll have to work through the protocol construction, definitions, and proofs.

Alice knows a secret key a ←$ Z_p, such that her public key is A = ga. (Assume that Alice posted A publicly on Piazza, and that everyone knows and agrees that A is hers.) In terms of the Crypto Egg bonus game, if you've been playing along, Alice's Crypto Egg public key is A.

The game master, Bob, asks Alice to reveal a little bit of information about her secret key. In particular, Alice has to reveal the group element: A' = g^a2

Alice also has to prove to Bob that she computed the group element Aj correctly. To do this, she'll use an interactive Zero-Knowledge proof scheme.

To be more explicit, let G_λ be a family of groups in which the discrete log problem is hard, and the order of each group in the family is |G_λ| = pλ = 2^poly(λ).

5.1

Illustrate an ideal functionality below that could carry out this protocol:

5.2

Write the goal for the necessary ZK proof scheme using Camenisch-Stadler notation. ZK{( ) : }

Feel free to simplify or rearrange at this point.
1. What is the witness?
2. What is the predicate?

5.3 Finish constructing the protocol (P, V ) below, where P is the prover and V is the verifier, such that P (1^λ, a) ↔ V (1^λ, A) emulates the ideal functionality .

1. Round 1 (commit): Let's assume that in the very first message, P sends A' := g^a2 does P send to V. What else does P send V?

2. Round 2 (challenge): V sends the challenge c to P where c ←Z_p\{0}

3. Round 3 (response): What does P send to V in response?

4. Verification: What does V do with the response?

5.4 Define the "Zero Knowledge" (aka "Simulatable") property for this scheme, in terms of ViewP and ViewV . Be sure to explain what the views consist of.

Give a construction for the simulator and prove it satisfies the definition.

5.5 Define the "Extractability" property.

Give a construction for the extractor E and prove it extracts correctly with non-negligible probability.

6 Reductions and Hard Problems

Which of these problems reduces to the others?
- (Computational Diffie Hellman): [a ←^$ Z_p, b ←^$ Z_p; A(1^λ, g^a, g^b) = g^ab]

- (Discrete Logarithm): [X ←^$ G, x ← A(1^λ, X) : g^x = X]

- (Decisional Diffie Hellman): Distinguish

{a ←^$ Z_p, b ←^$ Z_p : (g^a, g^b, g^ab )}

{a ←^$ Z_p, b ←^$ Z_p, r ←^$ Z_p : (g^a, g^b, g^r)}

(Hint: you should prove two reductions)

7 Commitments

Alice and Bob play a rock paper scissors game over a broadcast channel (Piazza) using the following protocol:

1. Alice: Generates random a. A = H(a), publish A

2. Bob: Generates random b. B = H(b), publish B

3. (Optional) We check that both values A, B are distinct.

4. Alice: Reveals a.

5. Bob: Reveals b.

6. Alice wins if ( a + b)mod2 = 1, otherwise Bob wins.

7.1

What happens if the Optional Step 3 is omitted? Give an explicit adversarial strategy for Bob, that deviates from the protocol and enables Bob to always win the game if Step 1 is removed.

7.2

Consider the following claim in a security analysis. "This protocol is secure for any choice of hash function H, as long as H is one-way (preimage resistant) and collision-resistant."

This claim doesn't work. Preimage resistance and collision resistance are not enough. To show this, it suffices to give a counterexample of a hash function that allows Bob to win, even with Step 3 in place.

Here's one such counterexample: consider what would happen if we instantiated hash with the elliptic curve function operation H(a) = ga, using the secp256k1 elliptic curve and generator g. Discrete log is thought to be hard in this group - it's exactly the same as the one-way property in this group.

But the protocol is still broken! Give a strategy for Bob that allows him to always win in this case.

8. Design Questions

Nancy is launching an e-commerce company called Nancy's Swole Academy (NSA) that connects people looking to find gym memberships with gyms around the nation. To celebrate the grand opening of NSA, Nancy is giving out a limited-supply of digital tokens called Fitcoins, which are valid at partnering gyms. Consumers can purchase Fitcoins and redeem them at one of the partnering gyms for a reduced-price gym membership.

To prevent bankrupting her partners, each Fitcoin should only be redeemed a single time, i.e., partnering gyms should be able to verify that a Fitcoin is valid and unspent. Unfortunately, consumers aren't comfortable divulging too much information about themselves to NSA. They are comfortable with NSA knowing that they have bought a Fitcoin, but not at which gym they have redeemed it. Can Nancy use cryptography to satisfy her consumers and her partners?

You can use any of the cryptographic primitives we have discussed so far in the semester (e.g., zero-knowledge proofs, key exchange, symmetric/asymmetric encryption, digital signatures, commitments, oblivious transfer, garbled circuits). You can assume that all parties (Nancy, the partners, and the consumers) will behave semi-honestly (i.e., parties follow your protocol and they won't collude, but they will try to learn as much information as possible).

9. Bonus

Write a short cryptography joke :)

Note: for full points, the joke must be both original and funny.

Ineligible jokes include: any pun about "salt"