Broadcast Complexity and Adaptive Adversaries in Verifiable Secret Sharing

Abstract EN

Verifiable secret sharing (VSS) is one of the basic problems in the theory of distributed cryptography and has an important role in secure multiparty computation.

In this case, it is tried to share a confidential data as secret, between multiple nodes in a distributed system, in the presence of an active adversary that can destroy some nodes, such that the secret can be reconstructed with the participation of certain size of honest nodes.

A dynamic adversary can change its corrupted nodes among the protocol.

So far, there is not a formal definition and there are no protocols of dynamic adversaries in VSS context.

Also, another important question is, would there exist a protocol to share a secret with a static adversary with at most 1 broadcast round? In this paper, we provide a formal definition of the dynamic adversary.

The simulation results prove the efficiency of the proposed protocol in terms of the runtime, the memory usage, and the number of message exchanges.

We show that the change period of the dynamic adversary could not happen in less than 4 rounds in order to have a perfectly secure VSS, and then we establish a protocol to deal with this type of adversary.

Also, we prove that the lower bound of broadcast complexity for the static adversary is (2,0)-broadcast rounds.