Exploiting Randomness in Secret Sharing

Shamir's (k,n)-threshold scheme is a method for sharing a secret among n participants such that any group of k or more participants can recover the secret. Additionally, any group of participants with size less than k should learn nothing about the secret. The scheme works by distributing a share to each participant, where each share is a linear combination of the secret and k-1 random symbols. This allows any group of k or more participants to solve a linear system to compute the secret. Any group of less than k participants does not have enough to determine anything about the secret. When k or more participants solve the linear system, they recover not only the secret but also all of the random symbols. These random symbols can be exploited by replacing them with uniformly distributed secrets. Doing this improves the scheme's efficiency. The trade-off is that groups of less than k participants may gain some information about a combination of secrets, though they still learn nothing about any individual secret -- a property known as individual security. In this thesis, we demonstrate how to exploit randomness in secret sharing for general access structures, i.e. schemes where specific groups are authorized to recover the secret, rather than just any group of a fixed size. For a given access structure, we characterize which random symbols can be replaced and provide an algorithm for the replacement. Our approach improves the scheme's performance for the given access structure while preserving individual security.