Improving the Cheater Identification Capability of Threshold Secret Sharing Schemes

Abstract

Secret sharing is an important cryptographic primitive by which any confidential information or secret is shared among a group of participants. Only authorized subsets of participants can recover the secret correctly, while unauthorized subsets of participants eventually get no information about the secret. Vulnerabilities arise in a secret sharing scheme due to a single or multiple dishonest participants. A single or multiple participants can collude to cheat by modifying their shares during the reconstruction of the secret. This enables them to recover the secret correctly for themselves by misleading the honest participants. The proposed scheme aims to detect such dishonest activity of the cheating participants and identify them. The detection mechanism utilizes the property of divided difference and identifies cheaters by checking the consistency of the inherent algebraic constraints across multiple subsets of shares arising from the divided difference structure. Further, the scheme does not rely on any cryptographic assumption and achieves an improved bound on the maximum number of identifiable cheaters while maintaining the share size equal to that of the secret. In addition, a lower bound on the minimum number of participants required for successful undetectable cooperative cheating is established.