Abstract:
We consider verifiable secret sharing (VSS) and multiparty
computation (MPC) in the secure channels model, where a broadcast channel is
given and a non-zero error probability is allowed. In this model Rabin and
Ben-Or proposed VSS and MPC protocols, secure against an adversary that can
corrupt any minority of the players. In this paper, we first observe that a
subprotocol of theirs, known as weak secret sharing (WSS), is not secure
against an adaptive adversary, contrary to what was believed earlier. We then
propose new and adaptively secure protocols for WSS, VSS and MPC that are
substantially more efficient than the original ones. Our protocols generalize
easily to provide security against general 
adversaries
Available as PostScript, PDF, DVI.