SECRET SHARING USING NC GROUPS AND THE SHORTLEX ORDER 3

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 eﬃciently 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,

1}k

which

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

alphabet

X±1

that define the group Gi = X|Ri .

• Randomly generates the shares si ∈ {0,

1}k

for i = 1, · · · , n − 1 and

sn = s −

∑n−1

j=0

sj where the addition is bitwise addition in

F2.k

• 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 eﬃciently 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

X±

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