|M.Sc Student||Omari Majd|
|Subject||The Complexity of Identifying Cheaters|
|Department||Department of Computer Science||Supervisor||Professor Yuval Ishai|
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 algorithm. 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 Locally Identifiable Secret Sharing (LISS), in which the reconstruction algorithm reveals to every party i a list of parties Li, such that if party i is honest then Li 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 nearly tight lower bound on the communication complexity of Unanimously Identifiable Commitment (UIC), a useful building block in previous constructions of identifiable secret sharing schemes.