Efficient Statistical Asynchronous Verifiable Secret Sharing with Optimal Resilience

We present a new statistical

asynchronous verifiable secret sharing

(AVSS) protocol with

optimal resilience

; i.e. with

n

 = 3

t

 + 1, where

n

is the total number of participating parties and

t

is the maximum number of parties that can be under the control of a

computationally unbounded active adversary

${\mathcal A}_t$

. Our protocol privately communicates

${\mathcal O}((\ell n^3 + n^4 \kappa) \kappa)$

bits and

A-cast

s

${\mathcal O}(n^3 \log(n))$

bits to simultaneously share ℓ ≥ 1 elements from a finite field

${\mathbb F}$

, where

κ

is the error parameter.

There are only two known statistical AVSS protocols with

n

 = 3

t

 + 1, reported in [11] and [26]. The AVSS protocol of [11] requires a private communication of

${\mathcal O}(n^9 \kappa^4)$

bits and

A-cast

of

${\mathcal O}(n^9 \kappa^2 \log(n))$

bits to share a

single

element from

${\mathbb F}$

. Thus our AVSS protocol shows a significant improvement in communication complexity over the AVSS of [11]. The AVSS protocol of [26] requires a private communication of

${\mathcal O}((\ell n^3 + n^4) \kappa)$

bits and

A-cast

of

${\mathcal O}((\ell n^3 + n^4) \kappa)$

bits to share ℓ ≥ 1 elements. However, the shared element(s) may be

$NULL \not \in {\mathbb F}$

. Thus our AVSS is better than the AVSS of [26] due to two reasons: (a) The

A-cast

communication of our AVSS is

independent

of the number of secrets i.e. ℓ; (b) Our AVSS makes sure that the shared value(s) always belong to

${\mathbb F}$

.

Using our AVSS, we design a new primitive called Asynchronous Complete Secret Sharing (ACSS) which is an essential building block of

asynchronous multiparty computation

(AMPC). Using our ACSS scheme, we can design a statistical AMPC with

optimal resilience

; i.e., with

n

 = 3

t

 + 1, that privately communicates

${\mathcal O}(n^5 \kappa)$

bits

per multiplication gate

. This will significantly improve the only known statistical AMPC of [8] with

n

 = 3

t

 + 1, which privately communicates Ω(

n

11

κ

4

) bits and

A-cast

Ω(

n

11

κ

2

log(

n

)) bits per multiplication gate.