a set of words R F (X) we define R as the smallest normal subgroup of F (X)
containing R and define the group G = X|R = F (X)/ R . We call R the set of
relators of G.
A group G = X|R has a solvable word problem if there exists an algorithm to
determine if any word w G is trivial. Habeeb-Kahrobaei-Shpilrain (HKS) secret
sharing [7] uses a group with an efficiently solvable word problem to create an
(n, n) threshold scheme which can be extended to a (k, n) threshold scheme using
the method of Shamir.
4.1. (n, n) Threshold. In this case the secret, s, is an element of {0,
we view as a column vector. The setting is initialized by making a set of generators
X = {x1, · · · , xn} public. To distribute the shares the dealer does the following:
Distributes to each Pi over a private channel a set of words Ri in the
that define the group Gi = X|Ri .
Randomly generates the shares si {0,
for i = 1, · · · , n 1 and
sn = s
sj where the addition is bitwise addition in
Publishes words wji over the alphabet X±1 such that a word wji is trivial
in Gi if sji = 1 and non-trivial if sji = 0.
Since the Gi have efficiently solvable word problem, the participant Pk can deter-
mine which of the wjk are trivial or non-trivial and can independently recover sk.
To recover the secret, the Pi add the si and find s. Note that even though the wji
are sent over an open channel, the shares remain secure since the Ri are private.
Therefore no other participant can recover si from the wji since only Pi knows Gi.
4.2. (k, n) Threshold. One can extend the above scheme to a (k, n) threshold
via Shamir’s scheme. As is the case with Shamir’s scheme, the secret s is an element
of Zp and the shares, si, correspond to points on a polynomial of degree k 1 with
constant term s. The shares are distributed and reconstructed in an identical
manner as above by viewing the si in their binary form. The trivial and non-
trivial words are sent to each Pi so that they reconstruct each si in its binary form.
After recovering their shares any element of the access structure can use polynomial
interpolation to find s:
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 converts each si = f(xi) into binary. And thus, each si can
be viewed as a column vector of length l = log2 p + 1.
As was the case in the (n, n) scheme, the dealer distributes the si over an
open channel by sending each Pi the words w1i, · · · , wli over the alphabet

such that wji is trivial in Gi if sji = 1 and non-trivial if sji = 0.
The participants reconstruct their own si and can recover the secret using
polynomial interpolation.
Some advantages this secret sharing scheme has over Shamir’s scheme include the
fact that after the Ri are distributed, one can still use them to send out and
reconstruct more secrets rather than having to privately distribute new shares each
time a different secret is picked. Private information has to only be sent once
initially for an arbitrary amount of secrets to be shared due to the method of
distributing the shares. Despite this, the scheme is vulnerable to an adversary
Previous Page Next Page