ON VERIFICATION IN SECRET SHARING

Verifiable Secret Sharing (VSS) hu proven to be a powerful tool in the construction of fault-tolerant distributed algorithms. Previous results show that Unverified Secret Sharing, in which there are no requirements when the dealer is faulty during distribution of the secret, requires the same number of processors as VSS. This is counterintuitive: verification that the secret is well shared out should come Lt a price. In this paper, by focussing on information leaked to nonfaulty processors during verification, we separate a certain strong version of Unverified Secret Sharing (USS) from its VSS analogue in terms of the required number of processors. The proof of the separation theorem yields information about communication needed for the original VSS problem. In order to obtain the separation result we introduce a new definition of secrecy, different from the Shannon definition, capturing the intuition that ''information' received from faulty processors may not be informative at all.