Technical Report MSC-2018-20

Title: The Complexity of Identifying Cheaters
Authors: Majd Omari
Supervisors: Yuval Ishai
PDFCurrently accessibly only within the Technion network
Abstract: 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 $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 nearly tight lower bound on the complexity of Unanimously Identifiable Commitment (UIC), a useful building block in previous constructions of identifiable secret sharing schemes.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2018
To the main CS technical reports page

Computer science department, Technion