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:


⎜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
Previous Page Next Page