Minimal Codewords and Secret Sharing

Abstract

: The use of a linear code to "split" secrets into equal-size shares is considered. The determination of which sets of shares can be used to obtain the secret leads to the apparently new notion of minimal codewords in a linear code. It is shown that the minimal codewords in the dual code completely specify the access structure of the secret-sharing scheme, and conversely. 1. Introduction In an (S, T) threshold secret-sharing scheme as introduced by Shamir [1], a q-ary secret is "split" into S q-ary shares in such a manner that any T shares uniquely determine the secret but any T - 1 or fewer shares provide no information about the secret. Shamir constructed such (S, T) threshold schemes (where 1 T S < q) by taking the secret to be the constant term in a monic polynomial of degree T over the finite field GF(q) whose T - 1 other coefficients are selected uniformly at random; the S shares are the values of this polynomial at any S specified and distinct nonzero elements of GF(q). McEl...