Threshold Secret Sharing Scheme for Compartmented Access Structures

Related Literature Review

Many researchers introduced new secret sharing scheme based either on Shamir’s scheme (1979) or with new concepts. Shamir introduced multipartite access structures in his seminal work for weighted threshold access structures. Blakely (1979) introduced geometric threshold secret sharing scheme. Mignotte (1983) and Asmuth-Bloom (1983) developed threshold secret sharing scheme based on the Chinese remainder theorem.

Mignotte’s threshold secret sharing scheme (1983) uses special sequences of integers, referred to as Mignotte sequences. A (k, n)-Mignotte sequence is a sequence of positive integers m₁ < · · · < m_n such that (m_i, m_j) = 1, for all 1 ≤ i < j ≤ n, and m_n−k+2 · · · m_n < m₁ · · · m_k. The scheme proposed by Asmuth and Bloom (1983) also used special sequences of integers. More exactly, a sequence of pairwise coprime positive integers r, m₁ < · · · < m_n is chosen such that r · m_n−k+2 · · · m_n < m₁ · · · m_k. This scheme was generalized for allowing modules that are not necessarily pairwise coprime in an obvious manner.

Brickell (1990) proposed an elegant solution by choosing the secret S as a combination of m compartment secrets and using a threshold secret sharing scheme for each compartment. In the reconstruction phase, if the number of participants from the j^th compartment is greater than or equal to the k_j, for all 1 ≤ j ≤ m, then all compartment secrets can be recovered and thus the secret S can be obtained. Brickell proved that all multilevel and compartmented access structures are ideal. He proved that every structure in one of those families admits a vector space secret sharing scheme over every large enough field. Even though the proof is constructive, this scheme did not explain how to construct efficiently.

Simmons (1990) introduced two families of multipartite access structures, the so-called multilevel and compartmented access structures by generalizing the geometrical threshold scheme by Blakely (1979) and he speculated that this was possible for all of them. He has presented the example of an official action that requires at least two Americans and at least two Russians for its initiation.