数学案例 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.



ECE498AC



Instructor: Andrew Miller October 10, 2018

Name  NetID



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.



Due date: 11:59pm, Oct 18 2018.



Academic integrity reminder: We treat academic integrity very seriously. You are supposed to do this exam individually. You may refer to lecture notes, optional textbooks, or internet searches. However, you should not talk about the problems with peers or ask for help online.



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



Clarity, succinctness, writing your name and Netid: [5 pts].


1 Indistinguishability [6 pts]



1. (3 pts) If {Xn}n is computationally indistinguishable from {Yn}n, {Yn}n is computationally indistin- guishable from {Zn}n, then (select the one that is always correct)

(a) {Xn}n is computationally indistinguishable from {Zn}n

(b) {Xn}n can be distinguished from {Zn}n

(c) Sometimes {Xn}n can be distinguished from {Zn}n, sometimes {Xn}n is computationally indis- tinguishable from {Zn}n

2. (3 pts) If Xn n can be distinguished from Yn n,  Yn  n can be distinguished from  Zn  n, then (select the one that is always correct)

(a) {Xn}n is computationally indistinguishable from {Zn}n

(b) {Xn}n can be distinguished from {Zn}n



(c) Sometimes {Xn}n can be distinguished from {Zn}n, sometimes {Xn}n is computationally indis- tinguishable from {Zn}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.   12 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 f1(n), f2(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. f1(n) + f2(n) b. f1(n)f2(n) c. f1(n)g(n) d. g(n) e. √f1(n) f. f1(n)g(n)

2.3 [2 pts]
(Let g1(n), g2(n) denote two fixed polynomials in n. Which of the following must be polynomial in n:

a.  g1(n) + g2(n) b. g1(n)g2(n) c. g1(n)g2(n) d. g1(n) + 203942 e.  g1(n) + 2n f. g1(n)100

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. ttj(s) = if |s| > 1024 then tt(s) else 0A(|s|)

b. ttj(s1 || s2) = tt(s1) ⊕ tt(s2), where |s1| = |s2| = λ c. ttj(s1 || s2) = tt(s1) ∨ tt(s2), where |s1| = |s2| = λ d. ttj(s1 || s2) = s1 || tt(s2), where |s1| = |s2| = λ

e. ttj(s) = s || tt(s)



3.2 Pseudorandom Functions [5 pts]


Let the collection of functions F = {fk}k∈{0,1}∗  be a PRF family where fk is a function from {0, 1}λ  → {0, 1}λ



when   k   = λ.  Define =   gk  k∈{0,1}∗ ,  where  gk  is  a  function  from   0, 1 defined as follows:

→ {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 [10 pts]


4.1 Identifying Groups [4 pts]


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 (a1, b1)>(a2, b2) = (a1 + a2, b1 × b2)



4.2 Subgroups [6 pts]


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| = 23 · 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 j, and in fact Mallory chose M so that the order is actually M = 8. Bob sends Mallory an encrypted message, c = hello PRFk(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 [20 pts]


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 , such that her public key is A = ga.  (Assume that Alice posted A publicly

p

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:

Aj = ga



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λ = 2poly(λ).



5.1 [4 pts]


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



5.2 [4 pts]


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 [4 pts]


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 Aj := ga

does P send to V ?



2. Round 2 (challenge): V sends the challenge c to P where

to V . What else





c ←$  Z \{0}

p



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



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



5.4 [4 pts]


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 [4 pts]


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 [10pts]


Which of these problems reduces to the others?

• (Computational Diffie Hellman):  Σa ←$  Z , b ←$  Z ; A(1λ, ga, gb) = gabΣ

p

• (Discrete Logarithm):  ΣX ←$  G, x ← A(1λ, X) : gx = XΣ



• (Decisional Diffie Hellman): Distinguish

$ $







a b ab







from

{a ← Zp, b ← Zp : (g

, g , g )}



$ $ $

a b r



{a ← Zp, b ← Zp, r ← Zp : (g

(Hint: you should prove two reductions)

7 Commitments [10pts]

, g , g )}





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 [10 pts]


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 comfort-



able 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 [5 pts]


Write a short cryptography joke ?

Note: for full points, the joke must be both original and funny. Ineligible jokes include: any pun about “salt”