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 diﬃcult 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 eﬃcient word problem that could also function as can-

didate groups, but small cancellation groups have the advantage of being eﬃcient

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

X±

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

· · ·