SECRET SHARING USING NC GROUPS AND THE SHORTLEX ORDER 5

Utilizing the the shortlex ordering, we can modify the HKS (k, n) threshold as

follows:

• The dealer publishes the letters X and over a private channel sends a set

of words, Ri in

X±1

to each Pi such that Gi = X|Ri is a group with

an eﬃcient algorithm to reduce words with respect to the Ri or compute

normal forms.

• The dealer chooses a secret s ∈ Zp for some large prime p n and

generates a random polynomial, f in Zp[x] with constant term s.

• The dealer assigns a public xi ∈ Zp to each participant, computes f(xi),

and finds si ∈ F (X) such that si is the

f(xi)th

word in F (X). Note that

xi is not a generator of G, but rather the x-coordinate associated to each

participant’s share.

• The dealer publishes a word wi that reduces to si in Gi. This can be

done eﬃciently by interspersing conjugated products of relators between

the letters of si.

• Each participant Pi computes their share by reducing wi to get si and

then computing its position in F (X).

• Using their shares they find the secret using polynomial interpolation.

The main advantage of this new method is that participants need only reduce

one word rather than a number of words corresponding to the length of the secret.

In general, being able to reduce words is more general than being able to solve the

word problem in a finitely presented group and in some cases may be more complex.

It is important to note the following about this scheme:

• Given an algorithm that reduces words, each wi must reduce uniquely to

si. This implies that if our reduction algorithm does not terminate at si,

then it is not a viable share for this scheme. In that case, if a random f(xi)

does not correspond to a fully reduced word or a word in normal form,

the dealer can always assign Pi a different xi. It may also be necessary to

check that each wi reduces to si give the reduction algorithm before the

shares are distributed.

• Some reduction algorithms can be done in multiple ways given the same

initial conditions and can terminate at different words. As such, it is

important to fix a protocol so that whatever process Pi uses to reduce wi

terminates at si.

4.5. Platform Group. For this variant of the HKS secret sharing scheme,

we also propose C (

1

6

) groups. Additionally, we propose the parameters |X| =

40, |R| = 4, and |r| = 9 for all r ∈ R. We find that with such parameters,

generating a single C (

1

6

) group can be done in roughly 1 second in GAP [6] by

generating random relators of the given length and then checking that the set of

relators satisfies the small cancellation condition. In order to reduce the wi to si,

participants can use Dehn’s algorithm which terminates in linear time [3]. It is not

guaranteed in general that Dehn’s algorithm will reduce each wi to si, as such it

is necessary to check that each wi reduces to si. In order to test the eﬃcacy of

Dehn’s algorithm in C (

1

6

) groups for the purposes of this secret sharing scheme,

we performed the following tests in GAP [6]:

• Generate 10 small cancellation groups using the parameters from the first

paragraph of this section.