Communication Efficient Perfectly Secure VSS and MPC in Asynchronous Networks with Optimal Resilience

Verifiable Secret Sharing (VSS) is a fundamental primitive used in many distributed cryptographic tasks, such as Multiparty Computation (MPC) and Byzantine Agreement (BA). It is a two phase (sharing, reconstruction) protocol. The VSS and MPC protocols are carried out among

n

parties, where

t

out of

n

parties can be under the influence of a

Byzantine (active)

adversary, having

unbounded computing power

. It is well known that protocols for perfectly secure VSS and perfectly secure MPC exist in an asynchronous network iff

n

 ≥ 4

t

 + 1. Hence, we call any perfectly secure VSS (MPC) protocol designed over an asynchronous network with

n

 = 4

t

 + 1 as

optimally resilient

VSS (MPC) protocol.

A secret is

d

-shared among the parties if there exists a random degree-

d

polynomial whose constant term is the secret and each honest party possesses a distinct point on the degree-

d

polynomial. Typically VSS is used as a primary tool to generate

t

-sharing of secret(s). In this paper, we present an

optimally resilient, perfectly secure

Asynchronous VSS (AVSS) protocol that can generate

d

-sharing of a secret for any

d

, where

t

 ≤ 

d

 ≤ 2

t

. This is the first

optimally resilient, perfectly secure

AVSS of its kind in the literature. Specifically, our AVSS can generate

d

-sharing of ℓ ≥ 1 secrets from

${\mathbb F}$

concurrently, with a communication cost of

${\cal O}(\ell n^2 \log{|{\mathbb F}|})$

bits, where

${\mathbb F}$

is a finite field. Communication complexity wise, the best known optimally resilient, perfectly secure AVSS is reported in [2]. The protocol of [2] can generate

t

-sharing of ℓ secrets concurrently, with the same communication complexity as our AVSS. However, the AVSS of [2] and [4] (the only known optimally resilient perfectly secure AVSS, other than [2]) does not generate

d

-sharing, for any

d

 > 

t

.

Interpreting in a different way, we may also say that our AVSS shares ℓ(

d

 + 1 − 

t

) secrets simultaneously with a communication cost of

${\cal O}(\ell n^2 \log{|{\mathbb F}|})$

bits. Putting

d

 = 2

t

(the maximum value of

d

), we notice that the amortized cost of sharing a single secret using our AVSS is only

${\cal O}(n \log{|{\mathbb F}|})$

bits. This is a clear improvement over the AVSS of [2] whose amortized cost of sharing a single secret is

${\cal O}(n^2 \log{|{\mathbb F}|})$

bits.

As an interesting application of our AVSS, we propose a new

optimally resilient, perfectly secure

Asynchronous Multiparty Computation

(AMPC) protocol that communicates

${\cal O}(n^2 \log|{\mathbb F}|)$

bits

per multiplication gate

. The best known

optimally resilient perfectly secure

AMPC is due to [2], which communicates

${\cal O}(n^3 \log|{\mathbb F}|)$

bits per multiplication gate. Thus our AMPC improves the communication complexity of the best known AMPC of [2] by a factor of Ω(

n

).