Secret sharing:-
Suppose you have a secret message m (a number) that you wish to divide among n people, so that the message can be determined by any t members of the group, but not by any subgroup of less than t members. This can be done as follows:
(a) Select a prime number p larger than any m that might be used.
(b) Select t - 1 coefficients s1,s2, ... ,st-1 and form the polynomial
![](https://book.transtutors.com/qimg/29ec8b30-d323-4981-a895-6b04f4462806.png)
(c) Index people from 1 to n, and tell them all the number p. Tell person with index k the value s(k) mod p. Any group of t people can reconstruct the (t -1)th order polynomial from their information by using the Lagrange interpolation formula. Let T be the set of indices of t people. That group can determine m as
![](https://book.transtutors.com/qimg/eb509f37-1729-4718-8e07-e54782fc9484.png)
Where T /k denotes every index in T except k. For example, for determination by three out of five people, suppose the message is 17, p = 43, and s(x) = 17 + 24x + 36x2. Then the five individuals would be told p, and each would be given a result according to this list:
![](https://book.transtutors.com/qimg/84eb98e8-0f4e-4ce7-b114-67048ddb3795.png)
Suppose that persons 2, 3, and 5 share their information. They compute
![](https://book.transtutors.com/qimg/f957e4e8-f2e0-4bb0-bdf5-cc6ec8797394.png)
Suppose on another day, the group is told p = 57 and persons 1, 3, and 4 are told the values 54, 48, 39 respectively. What is the message?