+61-413 786 465

[email protected]

 Algebra Math Calculus Physics Chemistry Biology Earth Science Physiology History Humanities English Sociology Nursing Science

Home >> Math

Clarity, succinctness, writing your name and Netid:

1 Indistinguishability

1. 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. 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.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/2n2 b. 1/2nc. 1/nloglog n d. n-3 e. n-log log log n f.2n g. nlog log n

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

(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) + 203942e. g1(n) + 2n f. g1(n)100 g.2 g1(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 0l(|s|)

b. G'(s1 || s2) = G(s1) ⊕ G(s2), where |s1| = |s2| = λ

c. G'(s1 || s2) = G(s1) ∨ G(s2), where |s1| = |s2| = λ

d. G'(s1 || s2) = s1 || G(s2), where |s1| = |s2| = λ

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

3.2 Pseudorandom Functions

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 G = {gk} k∈{0,1}, where gk is a function from 0, 1 defined as follows:

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

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| = 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 ∈ G', 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(Mb) 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 ←\$ Zp, 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' = ga2

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

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' := ga2 does P send to V. What else does P send V?

2. Round 2 (challenge): V sends the challenge c to P where c ←Zp\{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 ←\$ Zp, b ←\$ Zp; A(1λ, ga, gb) = gab]

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

- (Decisional Diffie Hellman): Distinguish

{a ←\$ Zp, b ←\$ Zp : (ga, gb, gab )}

{a ←\$ Zp, b ←\$ Zp, r ←\$ Zp : (ga, gb, gr)}

(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"

• Category:- Math
• Reference No.:- M93130660
• Price:- \$80

Guranteed 48 Hours Delivery, In Price:- \$80

Have any Question?

## Related Questions in Math

### Questions -q1 prove the following identitiesa sinx y sinx

Questions - Q1. Prove the following identities a. sin(x + y) + sin(x - y) = 2 sin x cos y b. sec(x - y) = cos(x + y)/(cos 2 x - sin 2 y) c. tan 2 x - sin 2 x = (tan x sin x) 2 Q2. Solve the following equations for x ∈ [0 ...

### Maths assignment - 1 analysis of a data setusing a

Maths Assignment - 1. Analysis of a data set Using a continuous data set you are requested to collect in the types of data and gathering data section, perform a statistical analysis on your data. You have opportunities t ...

### Questions - provide solution to the following questionsq1

Questions - Provide solution to the following questions: Q1. Evaluate the following: ∫xsin3xdx Q2. If , then for what value of α is A an identity matrix? Q3. The line y = mx + 1 is a tangent to the curve y 2 = 4x. Find t ...

### Assessment taskpractical investigation- question 1 requires

Assessment Task Practical Investigation - Question 1 requires selecting reference points from the graph. It is expected that each student will choose different reference points to other students. Take note of the criteri ...

### 1 suppose that n 10088821 is a product of two distinct

1. Suppose that n = 10088821 is a product of two distinct primes, and Φ(n) = 10082272. Determine the prime factors of n. 2. It is easy to show that the converse of Fermat's Theorem does not hold; i.e., the congruence a n ...

### Assignment -question 1 let t and or 0 1 be a boolean

Assignment - Question 1. Let (T, ∧, ∨,', 0, 1) be a Boolean Algebra. Define ∗ : T × T → T and o : T × T → T as follows: x ∗ y := (x ∨ y)' x o y := (x ∧ y)' (a) Show, using the laws of Boolean Algebra, how to define x ∗ y ...

### Assignment - provide solution to the following questionsq1

Assignment - Provide solution to the following questions: Q1. Evaluate the following: ∫xsin3x dx Q2. If , then for what value of α is A an identity matrix? Q3. The line y = mx + 1 is a tangent to the curve y 2 = 4x. Find ...

### Question 1 what is the nth order approximation using taylor

Question: 1. What is the nth order approximation using Taylor series? 2. What is Error Propagation? 3. Please explain what the total numerical error is? Please illustrate how the change of step size will affect the total ...

### Mathematics- algebraic geometry problemlet k denotes an

Mathematics- Algebraic Geometry Problem Let K denotes an algebraically closed field and let P 1 be constructed as in Example 5.5(a) in Gathmanns notes, i.e. P 1 is the gluing of X 1 = A 1 and X 2 = A 1 along  the open su ...

### Mathematics- algebraic geometry problemlet k denotes an

Mathematics- Algebraic Geometry Problem Let K denotes an algebraically closed field and let P 1 be constructed as in Example 5.5(a) in Gathmanns notes, i.e. P 1 is the gluing of X 1 = A 1 and X 2 = A 1 along  the open su ...

• 13,132 Experts

## Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

### Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

### Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

### Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of \$ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

### Compute the present value of an 1150 payment made in ten

Compute the present value of an \$1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

### Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of \$ 699 per year for 19 years, given a discount rate of 6 percent per annum. As