The Taub Faculty of Computer Science Events and Talks

A secret sharing scheme allows a dealer to distribute a secret amongst a group of participants, where each participant is given a share of the secret. Authorized sets of participants can reconstruct the secret while unauthorized sets do not gain any information about the secret. We study the problem of sharing secrets in the presence of cheaters, namely parties who contribute incorrect shares to the reconstruction procedure. It is known that when there is a majority of cheaters, it is impossible to guarantee correct reconstruction or even identify the cheaters with certainty. The best one could hope for in this setting is captured by the notion of List-Identifiable Secret Sharing (LISS), in which the reconstruction procedure reveals to every party i a list of parties L_i, such that if party i is honest then L_i is the list of cheaters. We study the complexity of LISS and related primitives. Our main result is that in any LISS scheme, the size of each share should grow linearly with the number of participants. This establishes the tightness of a previous upper bound from the literature. We also prove a tight lower bound on the complexity of unanimously identifiable commitment, a crucial building block in previous constructions of identifiable secret sharing schemes.