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 coeﬃcients 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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2015 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.