当前位置:天才代写 > 作业代写 > ECE Midterm代写 pseudorandom function代写 hash function代写

ECE Midterm代写 pseudorandom function代写 hash function代写

2020-12-01 16:03 星期二 所属: 作业代写 浏览:134

ECE Midterm代写

ECE498AC Midterm

ECE Midterm代写 Please either 1) typeset your answers in LATEX and submit a PDF file through Piazza, or else 2) write answers by hand and turn

Instructor: Andrew Miller October 10, 2018

Name  NetID  

Instructions ECE Midterm代写

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.ECE Midterm代写

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].ECE Midterm代写

1  Indistinguishability [6pts]

  1. (3pts) 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}nis computationally indistinguishable from {Zn}n

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

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

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

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

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

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

Useful Asymptotical Notations [6 points] ECE Midterm代写

(No need to prove throughout this question.)

Pseudorandomness [10 pts]ECE Midterm代写

3.1 Pseudorandom Generators [5 pts]

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

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:

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.ECE Midterm代写

You need to construct an adversary D that for every λ can tell apart a randomfunction 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.

ECE Midterm代写
ECE Midterm代写

Group Theory [10 pts]

4.1 Identifying Groups [4 pts]

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

  1. ({0,1}λ, ||), where {0, 1}λ is the set of λ-bitstrings and || denotes concatenation
  2. (Rλ×λ,    ), where Rλ×λ  is the set ofall λ λ matrices over real numbers, and the operation is matrix multiplication
  3. (Z − {0}, ×), where Z − {0}is all the integers except for 0
  4. (A×B,>), where (A, +) and (B, ×) are groups, A×B is their cartesian product, and (a1, b1)>(a2, b2) = (a1 + a2, b1 × b2)ECE Midterm代写
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.ECE Midterm代写

  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 valuesof |g|.)
  2. Boband Mallory are going to use Diffie-Hellman key  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”)

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 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.ECE Midterm代写

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]ECE Midterm代写

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 thewitness?
  2. What is thepredicate?
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 .ECE Midterm代写

  1. Round 1 (commit): Let’s assume that in the very first message, P sends Aj:= ga

does P send to V ?

  1. Round 2 (challenge): V sends the challenge c to Pwhere

c $  Z \{0}

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

 

4.Verification: What does V do with theresponse?

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.ECE Midterm代写

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.

Reductions and Hard Problems [10pts]

Which of these problems reduces to the others?

ECE Midterm代写
ECE Midterm代写

(Hint: you should prove two reductions)

Commitments [10pts]

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), publishA
  2. Bob: Generates random b. B = H(b), publishB
  3. (Optional) We check that both values A, B are
  4. Alice: Revealsa.
  5. Bob: Revealsb.
  6. Alice wins if (a + b)mod2 = 1, otherwise Bob
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.ECE Midterm代写

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.

Design Questions [10 pts]ECE Midterm代写

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?ECE Midterm代写

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).ECE Midterm代写

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”

ECE Midterm代写
ECE Midterm代写

更多其他:C++代写 考试助攻 C语言代写 计算机代写 project代写 数学代写 java代写 程序代写 algorithm代写 C++代写 北美代写 代写CS 代码代写 金融经济统计代写 function代写

合作平台:天才代写 幽灵代写 写手招聘 Essay代写

 

天才代写-代写联系方式