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.

1 Shamir Secret Splitting (10 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 20a, 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. [2 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. [2 points] Of those groups that succeed in recovering a secret, do they all recover the same secret? Explain why or why not.
7. [2 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?