A secret-sharing scheme is a method by which a dealer distributes shares to parties such that only authorized subsets of parties can reconstruct the secret. Secret-sharing schemes are an important tool in cryptography and they are used as a building box in many secure protocols, e.g., general protocol for multiparty computation, Byzantine agreement, threshold cryptography, access control, attribute-based encryption, and generalized oblivious transfer.
In this talk, I will describe the most important constructions of secret- sharing schemes; in particular, I will explain the connections between secret-sharing schemes and monotone formulae and monotone span programs. I will then discuss the main problem with known secret-sharing schemes -- the large share size, which is exponential in
the number of parties. I conjecture that this is unavoidable. I will present the known lower bounds on the share size. These lower bounds are fairly weak and there is a big gap between the lower and upper bounds. For linear secret-sharing schemes, which is a class of schemes based on linear algebra that contains most known schemes, super-polynomial lower bounds on the share size are known. If time will permit, I will also present two results connecting
secret-sharing schemes for a Hamiltonian access structure to the NP vs. coNP problem and to a major open problem in cryptography -- constructing oblivious-transfer protocols from one-way functions.