SECRET SHARING USING NC GROUPS AND THE SHORTLEX ORDER 5
Utilizing the the shortlex ordering, we can modify the HKS (k, n) threshold as
• The dealer publishes the letters X and over a private channel sends a set
of words, Ri in
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
• 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
word in F (X). Note that
xi is not a generator of G, but rather the x-coordinate associated to each
• 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 (
) 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 (
) group can be done in roughly 1 second in GAP  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 . 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 (
) groups for the purposes of this secret sharing scheme,
we performed the following tests in GAP :
• Generate 10 small cancellation groups using the parameters from the first
paragraph of this section.