Date of Award
12-2024
Document Type
Thesis
Degree Name
Master of Science (MS)
Department
Mathematical Sciences
Committee Chair/Advisor
Rafael D'Oliveira
Committee Member
Ryann Cartor
Committee Member
Felice Manganiello
Committee Member
Alex Sprintson
Abstract
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.
Recommended Citation
Bass, Cailyn, "Exploiting Randomness in Secret Sharing" (2024). All Theses. 4402.
https://open.clemson.edu/all_theses/4402
