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 = log 2 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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2015 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.