4 BREN CAVALLO AND DELARAM KAHROBAEI
determining the relators by seeing patterns in words they learn are trivial. Namely,
after a participant reveals their share (possibly while recovering the secret) an
adversary could determine which of the wji were trivial and potentially find the
group presentation of Gi which would allow them to reconstruct Pi’s share on
their own. As in [7], we assume that this is a computationally difficult problem.
Moreover, in Section 5 we provide a method to update relators over time thus
limiting the amount of information an adversary could obtain about a single group.
Another advantage to this scheme is that since it is based on the Shamir secret
sharing protocol it can benefit from the large amount of research done on Shamir’s
scheme. For instance, the verification methods or proactive secret sharing protocols
from [16] and [8] can still be used in this scheme.
4.3. Small Cancellation Groups. In this section we introduce a candidate
group for the above secret sharing scheme.
A word w is cyclically reduced if it is reduced in all of its cyclic permutations.
Note that this only occurs if the word is freely reduced, it has no subwords of the
form xi
−1xi
or xixi
−1,
and the first and last letters are not inverses of each other.
A set of words R is called symmetrized if each word is cyclically reduced and
the entire set and their inverses are closed under cyclic permutation. If R is viewed
as a set of relators, symmetrizing R does not change the resulting group as the
closure R under cyclic permutations and inverses is a subset of the normal closure.
Given a set R we say that v is a piece if it is a maximal initial subword of two
different words, namely if there exist w1,w2 R such that w1 = vr1 and w2 = vr2.
A group G = X|R satisfies the small cancellation condition C (λ) for 0 λ 1
if for all r R such that r = vw where v is a piece, then |v| λ|r|.
Small cancellation groups satisfying C (
1
6
) have a linear time algorithm for
the word problem [3] making them an ideal candidate for the HKS secret sharing
scheme. Moreover, it can be seen from their definition that if the number of gen-
erators is large compared to the number of relators and lengths of the relators, it
is likely that there will be small cancellation since the probability that any two
words have a large maximal initial segment is low. After generating a random set
of relators satisfying the above properties, it is also fast to symmetrize the set and
then find the pieces and check that they are no larger than one sixth of the word.
As such, it is fast to create such groups by repeatedly randomly generating relators,
symmetrizing, and checking to see if they satisfy the C (
1
6
) condition. There are
other groups that have an efficient word problem that could also function as can-
didate groups, but small cancellation groups have the advantage of being efficient
to generate randomly.
4.4. Secret Sharing and the Shortlex Ordering. Let X = {x1, · · · , xn}
and G = X . A shortlex ordering on G is induced by an order on
X±1
as follows.
Given reduced w = xi1 · · · xip and l = xj1 · · · xjk with w = l then w l if and only
if:
|w| |l|,
or if p = k and xia xja where a = minα{xiα = xjα }.
For example, let X = {x, y} and give

the ordering x
x−1
y
y−1.
Then
some of the first words in order would be:
e x
x−1
y
y−1 x2
xy
xy−1 x−2 x−1y x−1y−1
yx
yx−1 y2 y−1x y−1x−1 y−2 x3 x2y x2y−1
xyx
xyx−1
· · ·
Previous Page Next Page