Algebraic aspects of secret sharing and erasure decoding
To share a secret, Shamir proposed to use polynomials over a finite field. Unknown values of a polynomial can be obtained from a large enough subset of known values through interpolation. In coding theory terms the reconstruction of a secret amounts to the correction of erasures in a Reed-Solomon code. The principles of secret sharing have since found their way into multiparty computation protocols, encoding schemes for the wiretap channel and secure network coding. We use these applications as motivation to study a wider class of secret sharing schemes. We describe several phenomena that are not visible in the case of Reed-Solomon codes and that appear when polynomials over a finite field are replaced with multivariate polynomials or with algebraic functions, and how to take advantage of them. No special background is assumed beyond Reed-Solomon codes or polynomials over a finite field.