Secret Sharing Schemes : A Fine Grained Analysis
In this paper we prove that embedding parity bits and other function outputs in share string enables us to construct a secret sharing scheme (over binary alphabet) robust against a resource bounded adversary. Constructing schemes robust against adversaries in higher complexity classes requires an increase in the share size and increased storage. By connecting secret sharing with the randomized decision tree of a Boolean function we construct a scheme which is robust against an infinitely powerful adversary while keeping the constructions in a very low complexity class, viz. AC. As an application, we construct a robust secret sharing scheme in AC that can accommodate new participants (dynamically) over time. Our construction requires a new redistribution of secret shares and can accommodate a bounded number of new participants.