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:

⎛

⎜

⎜x2k−1

⎜

⎝

x1k−1 · · · x1 1

· · · x2 1⎟

.

.

.

...

.

.

.

.⎟

.

.⎠

xkk−1

· · · xk 1

⎞⎛

⎟⎜ak−2⎟

⎜

⎜

⎝

ak−1

.

.

.

a0

⎞

⎟

⎟

⎠

=

⎛

⎜ ⎜f(x2)⎟⎟

⎜

⎝

f(x1)

.

.

.

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 = {x1

±1,

. . ., xn ±1},

where a word is reduced if there are no subwords of the form xi

−1

xi or xixi

−1

. Given