How to Stop a Cheater: Secret Sharing with Dishonest Participation
Erik W. Selberg · 2001
At times it is necessary to obtain a group decision from a number of different nodes over a large network. Secret sharing protocols allow a quorum q of a group of n people to arrive at decisions by having the quorum recompute a predetermined secret, such as an access code, while preventing less than q people from gaining any information about the secret. However, current protocols [6, 5] are vulnerable when participants cheat, for example by giving false information to other participants. In this work, I present a powerful new protocol which detects cheaters immediately and halts the exchange before any more information is revealed. In addition, it prevents cheaters from gaining any information without revealing an equal amount of their own. This protocol will present new paradigms in a variety of applications, such as electronic balloting and secure file system fault tolerance. This report was submitted in partial fulfillment of the requirements for the Senior Honors Research Program ...