Suppose you have a secret, namely 5. You want to set up a system where four persons A, B, C, D are given shares of the secret in such a way that any two of them can determine the secret, but no one alone can determine the secret. Describe how this can be done. In particular, list the actual pieces of information (i.e., numbers) that you could give to each person to accomplish this.

Persons $A$, $B$, $C$ participate in a Shamir $(3\text{,}2)$ secret sharing scheme. They work mod 11. $A$ receives the share $(1\text{,}5)$, $B$ receives $(2\text{,}9)$, and $C$ receives $(3\text{,}3)$.

1. Show that at least one of the three shares is incorrect.

2. Suppose $A$ and $C$ have correct shares. Find the secret.

You set up a (2, 30) Shamir threshold scheme, working mod the prime 101. Two of the shares are (1,13) and (3,12). Another person received the share (2, *), but the part denoted by * is unreadable. What is the correct value of * ?

You set up a (2, 10) Shamir threshold scheme, working mod the prime 73. Two of the shares are (1, 10) and (2, 18). A third share is (5, *). What is *?

In a $(3\text{,}5)$ Shamir secret sharing scheme with modulus $p=17$, the following were given to Alice, Bob, and Charles: $(1\text{,}8)$, $(3\text{,}10)$, $(5\text{,}11)$. Calculate the corresponding Lagrange interpolating polynomial, and identify the secret.

In a Shamir secret sharing scheme, the secret $s$ is the constant term of a degree 4 polynomial mod the prime 1093. Suppose three people have the secrets (2, 197), (4, 874), and (13, 547). How many possibilities are there for the secret? (Note: We assume that $0\le s\le 1092$.)

Mark doesn’t like mods, so he wants to implement a $(2\text{,}30)$ Shamir secret sharing scheme without them. His secret is $M$ (a positive integer) and he gives person $i$ the share $(i\text{,}M+si)$ for a positive integer $s$ that he randomly chooses. Bob receives the share $(20\text{,}97)$. Describe how Bob can narrow down the possibilities for $M$ and determine what values of $M$ are possible.

A key distributor uses a $(2\text{,}20)$-threshold scheme to distribute a combination to an electronic safe to 20 participants.

1. What is the smallest number of participants needed to open the safe, given that one unknown participant is a cheater who will reveal a random share?

2. If they are only allowed to try one combination (if they are wrong the electronic safe shuts down permanently), then how many participants are necessary to open the safe? (Note: This one is a little subtle. A majority vote actually works with four people, but you need to show that a tie cannot occur.)

A certain military office consists of one general, two colonels, and five desk clerks. They have control of a powerful missile but don’t want the missile launched unless the general decides to launch it, or the two colonels decide to launch it, or the five desk clerks decide to launch it, or one colonel and three desk clerks decide to launch it. Describe how you would do this with a secret sharing scheme. (Hint: Try distributing the shares of a (10, 30) Shamir scheme.)

Suppose there are four people in a room, exactly one of whom is a foreign agent. The other three people have been given pairs corresponding to a Shamir secret sharing scheme in which any two people can determine the secret. The foreign agent has randomly chosen a pair. The people and pairs are as follows. All the numbers are mod 11.

Determine who the foreign agent is and what the message is.

Consider the following situation: Government A, Government B, and Government C are hostile to each other, but the common threat of Antarctica looms over them. They each send a delegation consisting of 10 members to an international summit to consider the threat that Antarctica’s penguins pose to world security. They decide to keep a watchful eye on their tuxedoed rivals. However, they also decide that if the birds get too rowdy, then they will launch a full-force attack on Antarctica. Using secret sharing techniques, describe how they can arrange to share the launch codes so that it is necessary that three members from delegation A, four members from delegation B, and two members from C cooperate to reconstruct the launch codes.

This problem explores what is known as the Newton form of the interpolant. In the Shamir method, we presented two methods for calculating the interpolating polynomial. The system of equations approach is difficult to solve and easy to evaluate, while with the Lagrange approach it is quite simple to determine the interpolating polynomial but becomes a labor to evaluate. The Newton form of the interpolating polynomial comes from choosing $1\text{,}x-x_1\text{,}(x-x_1)(x-x_2)\text{,}\cdots \text{,}(x-x_1)(x-x_2)\cdots (x-x_t)$ as a basis. The interpolating polynomial is then $p(x)=c_0+c_1(x-x_1)+c_2(x-x_1)(x-x_2)+\cdots +c_t(x-x_1)(x-x_2)\cdots (x-x_t)$. Show that we can solve for the coefficients $c_k$ by solving a system $Nc=y$. What special properties do you observe in the matrix $N$? Why does this make the system easier to solve?

In a Blakley $(3\text{,}w)$ scheme, suppose persons A and B are given the planes $z=2x+3y+13$ and $z=5x+3y+1$. Show that they can recover the secret without a third person.