Instructions Work the problems below, prepare your answers in electronic form, and submit your solutions to Canvas as usual. As always, you must properly cite all resources that you use to solve the problems.

Problem 1: Zero knowledge (4 points)

Alice used a zero knowledge proof of knowledge of a square root to convince Bob that her publicly posted number v is a quadratic residue modulo n, where n is the product of distinct odd primes. (n is also public.) In the course of their conversation, they generated a transcript of 20 triples (x_i,b_i,y_i), i = 1,…,20.

Bob is excited to learn that Alice was telling the truth when she told him that not only is v a quadratic residue, but she also knows a square root of it. He tells his friend Charlie that Alice really was truthful and that Charlie should trust Alice. To convince Charlie, Bob forwards him a copy of the transcript.

Charlie isn’t convinced of anything and still doesn’t trust Alice. Why not? Explain!
[Hint: Show how Bob could have constructed the transcript with knowing Alice’s secret (and without even talking to Alice).]

Problem 2: Cryptographically strong PRSG (3 points)

Happy’s roommate, Naive Nelson, is building a pseudorandom sequence generator. He has found a PRSG G that takes a 128-bit seed s and outputs a bit string x of length 1000. Naive wants to generate bit strings of length ℓ = 100,000, so he creates a new generator G′ that works in stages. His idea is to use G repeatedly, obtaining 1000 bits each time. To avoid getting repetitions of the same 1000-bit string, he uses the last 128 bits of each block as a seed for the next block.

Here is his algorithm for computing G′(s):

In this notation, λ denotes the empty string, || denotes concatenation, and last(k,x) returns the last k bits of x.

Explain in words why G′(s) is not cryptographically strong.
[Hint: Describe how knowing some of the pseudorandom output bits allows the rest to be easily predicted.]

Problem 3: Shamir Secret Splitting (13 points)

Alice is leaving for a year of study abroad. She has surprising news that she wants to share with 12 friends, but she doesn’t want to tell them before she leaves home since she would feel embarrassed to be present when they learn her secret. Although she trusts her friends, they are naturally curious. Moreover, she’s concerned that the parents of two of her friends might discover their shares, and she really doesn’t want the parents to find out what her surprise is.

She decides to split her secret into 12 shares and give one to each friend so that any three or more friends can cooperate to discover the secret, but two are not enough. She uses the (τ,k) threshold scheme that she learned in crypto and distributes the shares before leaving. Unfortunately, unknown to everyone, one of the shares gets corrupted in transit.

By the time she leaves, three of her friends have gone home to Santa Monica, four have gone on a trip to Las Vegas, and the remaining five are still in New Haven.

Each of the three groups of friends then gets together in person and uses the algorithm presented in class to recover the secret.

1. [1 point] What values should Alice choose for τ and k?
2. [1 point] Following lecture 20, Alice needs to choose a polynomial f(x) with coefficients in Z_p. What are the requirements on p for the scheme to work and be secure?
3. [1 point] What degree should f(x) be?
4. [1 point] Once Alice has chosen f(x), how should she generate the shares?
5. [3 points] Do all three groups of friends always succeed in recovering a secret? Explain why or why not. [Remember that one share is bad, but nobody knows which one it is, not even the friend who happens to hold the bad share.]
6. [3 points] Of those groups that succeed in recovering a secret, do they all recover the same secret? Explain why or why not.
7. [3 points] The three groups text the results of each group’s recovery attempt to each other, that is, whether or not it failed, and if it did succeed, the secret they recovered. Can everyone now figure out correctly what Alice’s secret is? If so, how? If not, why not?