Optimum Secret Sharing Scheme Secure against Cheating

Abstract

Tompa and Woll introduced a problem of cheating in $(k,n)$ threshold secret sharing schemes. In this problem $k-1$ malicious participants aim to cheat an honest one by opening forged shares and causing the honest participant to reconstruct the wrong secret. We first derive a tight lower bound on the size of shares $|\cV_i|$ for secret sharing schemes that protect against this type of attack: $ |\cV_i| \geq (|\cS|-1)/\delta + 1 $, where $\cV_i$ denotes the set of shares of participant $P_i$, $\cS$ denotes the set of secrets, and $\delta$ denotes the cheating probability. We next present an optimum scheme, which meets the equality of our bound, by using "difference sets." A partial converse and some extensions are also shown.