Access Restriction

Author Rabin, Tal
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1994
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract The problem of Verifiable Secret Sharing (VSS) is the following: A dealer, who may be honest or cheating, can share a secret $\textit{s},$ among $\textit{n}$ ≥ $2\textit{t}$ + 1 players, where $\textit{t}$ players at most are cheaters. The sharing process will cause the dealer to commit himself to a secret $\textit{s}.$ If the dealer is honest, then, during the sharing process, the set of dishonest players will have no information about $\textit{s}.$ When the secret is reconstructed, at a later time, all honest players will reconstruct $\textit{s}.$ The solution that is given is a constant round protocol, with polynomial time local computations and polynomial message size. The protocol assumes private communication lines between every two participants, and a broadcast channel. The protocol achieves the desired properties with an exponentially small probability of error.A new tool, called Information Checking, which provides authentication and is not based on any unproven assumptions, is introduced, and may have wide application elsewhere.For the case in which it is known that the dealer is honest, a simple constant round protocol is proposed, without assuming broadcast.A weak version of secret sharing is defined: Weak Secret Sharing (WSS). WSS has the same properties as VSS for the sharing process. But, during reconstruction, if the dealer is dishonest, then he might obstruct the reconstruction of $\textit{s}.$ A protocol for WSS is also introduced. This protocol has an exponentially small probability of error. WSS is an essential building block for VSS. For certain applications, the much simpler WSS protocol suffice.All protocols introduced in this paper are secure in the Information Theoretic sense.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1994-11-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 41
Issue Number 6
Page Count 21
Starting Page 1089
Ending Page 1109

Open content in new tab

   Open content in new tab
Source: ACM Digital Library