A New, Publicly Veri able, Secret Sharing Scheme


1 Department of Mathematical Sciences,Sharif University of Technology

2 Department of Electrical Engineering,Sharif University of Technology


A Publicly Veri able Secret Sharing (PVSS) scheme, as introduced by Stadler, has a feature
where anyone, besides the participants, can verify the validity of the shares distributed by
the dealer. Schoenmakers added a new feature, by providing a proof of correctness of the
shares released by the players in the reconstruction process. This protocol is claimed to
be an improvement on Stadler's and Fujisaki-Okamoto's, both in eciency and in the type
of intractability assumptions. However, Young-Yung improved Schoenmakers' PVSS, using a
Discrete-Log instead of a Decision Die-Hellman. In this paper, a new PVSS is presented,
having an intrinsic di erence with its predecessors, that is, the participants can prove the validity
of their given shares, implicitly, proving their membership by a zero-knowledge protocol. This
feature prevents cheaters from participating in the reconstruction process to gain valid shares.
Hence, the new proposed PVSS is more secure than previous ones. Besides, the dealer only
sends the amount of commitments limited to the threshold value, regardless of the number of
shareholders; this leads to a more dynamic protocol.