2 BREN CAVALLO AND DELARAM KAHROBAEI In order to recover the secret, participants can run the algorithm Recover which has the property that for all A A: Recover({si : i A}) = s and if A / A then running Recover is either computationally infeasible or impossi- ble. As such, only groups of participants in A can access the secret. The monotonic- ity of A is also apparent in that if A A and A B then the set of participants in A could also recover the secret for B. A secret sharing scheme is called perfect if ∀A / A the shares si A together give no information about s. 3. Shamir’s Secret Sharing Scheme One of the more common access structures one sees in secret sharing is the (k,n) threshold: A = {A 2{P1,··· ,Pn} : |A| k}. Namely, A consists of all subsets of the n participants of size k or greater. We call a secret sharing scheme that has A as a (k, n) threshold a (k, n) threshold scheme. The problem of discovering a perfect (k, n) threshold scheme was solved indepen- dently by G. Blakely [2] and A. Shamir [15] in 1979. In the Shamir Secret Sharing Scheme, the secret is an element in Zp where p is a prime number larger than the number of participants. Given a secret s, the dealer generates the shares for a (k, n) threshold by doing the following: The dealer randomly selects a1, · · · , ak−1 Zp such that ak−1 = 0 and constructs the polynomial f(x) = ak−1xk−1 + · · · + a1x + s For each participant Pi the dealer publishes a corresponding xi Zp. The dealer then distributes the share si = f(xi) to each Pi over a private channel. Any subset of k participants can then reconstruct the polynomial f(x) by using polynomial interpolation and then finding f(0) = s. This method finds s uniquely as any degree k −1 polynomial is uniquely determined by the k shares. The shares are consistent because each (xi,f(xi)) is a point on the polynomial f(x) and thus any k shares will reconstruct the same polynomial. In order to reconstruct a polynomial f(x) = a0 + a1x + · · · ak−1xk−1 given points (x1,f(x1)), · · · , (xk,f(xk)) one can solve for the coefficients column in the following system of linear equations: ⎜x x1k−1 · · · x1 1 2 k−1 · · · x2 1⎟ . . ... . . .⎟ .⎠ xkk−1 · · · xk 1 ⎞⎛ ⎟⎜ ⎜a ak−1 k−2 . . a0 = ⎜f(x f(x1) 2 )⎟ . . f(xk) . The above method of interpolation demonstrates that Shamir’s scheme is perfect. If there were less than k shares, than the system of equations above would have more equations than unknowns, and there would not be a unique solution for a0. 4. Secret Sharing Using Non-commutative Groups Given a set of letters X = {x1,x2,...,xn} we define the free group generated by X, F (X), as the set of reduced words in the alphabet X±1 = {x±1,...,x±1}, 1 n where a word is reduced if there are no subwords of the form xi −1 xi or xixi −1 . Given
Previous Page Next Page