Round and Communication Efficient Unconditionally-Secure MPC with $t<n/3$ in Partially Synchronous Network

Abstract

In this work, we study unconditionally-secure multi-party computation (MPC) tolerating $t < n/3$ corruptions, where n is the total number of parties involved. In this setting, it is well known that if the underlying network is completely asynchronous, then one can achieve only statistical security; moreover it is impossible to ensure input provision and consider inputs of all the honest parties. The best known statistically-secure asynchronous MPC (AMPC) with $t<n/3$ requires a communication of $\varOmega (n^5)$ field elements per multiplication. We consider a partially synchronous setting, where the parties are assumed to be globally synchronized initially for few rounds and then the network becomes completely asynchronous. In such a setting, we present a MPC protocol, which requires $\mathcal {O}(n^2)$ communication per multiplication while ensuring input provision. Our MPC protocol relies on a new four round, communication efficient statistical verifiable secret-sharing (VSS) protocol with broadcast communication complexity independent of the number of secret-shared values.

A. Choudhury—Financial support from Infosys Foundation acknowledged.

A. Patra—Work partially supported by INSPIRE Faculty Fellowship (DST/INSPIRE/04/2014/015727) from Department of Science & Technology, India.

1 Introduction

Threshold unconditionally-secure multiparty computation (MPC) is a fundamental problem in secure distributed computing [2, 8, 12, 26, 36, 38]. Informally, an MPC protocol enables a set of n mutually distrusting parties to jointly and securely compute a publicly known function f of their private inputs over some finite field $\mathbb {F}$, even in the presence of a computationally unbounded active adversary $\mathsf {Adv}$, who can corrupt any t out of the n parties. Let the parties be connected by pair-wise secure (private and authentic) channels. Then in the synchronous communication setting, where the parties are assumed to be synchronized through a global clock, it is known that perfectly-secure MPC is possible if and only if $t<n/3$ [8]. If a common broadcast channel is also available to the parties in addition to the pair-wise secure channels, then one can tolerate upto $t<n/2$ corruptions, albeit with statistical security ¹ [36]. The resilience bounds become different if one considers a completely asynchronous setting, where parties are not synchronized and messages can be arbitrarily delayed. Specifically, perfectly-secure asynchronous MPC (AMPC) is possible if and only if $t<n/4$ [7], while statistically-secure AMPC is possible if and only if $t<n/3$ [9].

Feasibility Results for Unconditionally-secure MPC: In any general MPC protocol [2,3,4,5, 8, 10, 12, 15, 20, 27, 36], the function f is usually expressed as an arithmetic circuit (consisting of addition and multiplication gates) over $\mathbb {F}$ and then the protocol “securely” evaluates each gate in the circuit in a shared/distributed fashion. More specifically, each party secret-shares its inputs among the parties using a linear secret-sharing scheme (LSS) [17], say Shamir [37], with threshold² t. The parties then interact to maintain the following invariant for each gate: given the gate inputs in a secret-shared fashion, the gate output is computed in a secret-shared fashion. Finally the (shared) circuit output is publicly reconstructed. Intuitively, the privacy follows since each intermediate value in the above process remains secret-shared with threshold t. Due to the linearity of the LSS, the addition (linear) gates are evaluated locally by the parties. However, maintaining the above invariant for the multiplication (non-linear) gates requires interaction among the parties. The focus therefore is rightfully placed on measuring the communication complexity (namely the total number of field elements communicated) required to evaluate the multiplication gates in the circuit. In the recent past, a lot of work has been done to design communication-efficient MPC protocols; we summarize the relevant works here.

With $t<n/3$, [5] presents a perfectly-secure MPC protocol with $\mathcal {O}(n)$ amortized communication complexity³ per multiplication, while [10] presents a statistically-secure MPC protocol with $t<n/2$ with almost $\mathcal {O}(n)$ communication complexity per multiplication. Both these results are in the synchronous setting and require non-constant number of rounds of interaction among the parties. While the protocol of [5] requires $\varTheta (n + \mathcal {D})$ rounds, the protocol of [10] requires $\varTheta (n^2 + \mathcal {D})$ rounds, where $\mathcal {D}$ denotes the multiplicative depth of the circuit.

A major drawback of the synchronous setting is that it does not model real life networks like the Internet accurately where it is very hard to ensure that the users are synchronized through a global clock and that there exists a strict a priori known upper bound on the message delivery. Real life networks can be modelled more appropriately by the asynchronous setting, where there are no known upper bounds and messages are delivered arbitrarily (the only guarantee given in this model is that the messages sent by the honest parties will reach to their destination eventually). Hence designing AMPC protocols is practically motivated. However, an inherent challenge in designing protocols in a completely asynchronous setting is that it is impossible to distinguish between a slow, but honest party (whose messages are delayed arbitrarily) and a corrupt party (who do not send any message at all). Hence in a completely asynchronous protocol, no party can afford to receive messages from all the n parties, as the wait may turn out to be an endless wait. So as soon a party receives messages from $n - t$ parties, it has to proceed to the next “step” of the protocol. However, in this process, messages from t potentially honest, but slow parties may get ignored. Due to this inherent phenomena, designing efficient AMPC protocols is a challenging task, as evident from the known feasibility results for AMPC protocols summarized below.

In a completely asynchronous setting, [34] presents a perfectly-secure AMPC protocol with $t<n/4$ and $\mathcal {O}(n^2)$ communication per multiplication, while [32] presents a statistically-secure AMPC with $t<n/3$ and $\mathcal {O}(n^5)$ communication per multiplication. As it is clear, there is a significant gap in the communication complexity of MPC and AMPC protocols. In addition, any AMPC protocol cannot ensure input provision, namely the inputs of all the honest parties may not be considered for the circuit evaluation, as this may turn out to be an endless wait and so inputs of upto t potentially honest parties may get ignored. With an aim to bridge the gap in the communication complexity of synchronous and asynchronous MPC and to enforce input provision, the works of [4, 14] motivate and consider hybrid asynchronous setting, where the network is assumed to be synchronized for few initial rounds and then it becomes completely asynchronous. This is a practically motivated communication setting, which has been well considered in the recent past for bridging the efficiency gap between synchronous and asynchronous protocols for various distributed computing tasks [4, 6, 14, 23, 30].

With $t<n/4$, a perfectly-secure hybrid MPC protocol with one synchronous round is presented in [14], with $\mathcal {O}(n)$ amortized communication complexity per multiplication. In [15], four MPC protocols in the hybrid setting are proposed with $t<n/3$; while two of these protocols are perfectly-secure, the remaining two are statistically-secure. These protocols are obtained by instantiating the efficient framework for unconditionally-secure MPC proposed in [15] with existing VSS schemes with $t<n/3$ (more on this later). Among the perfectly-secure protocols, the first one requires less number of synchronous rounds, namely⁴ (12, 3), but requires a higher communication of $\mathcal {O}(n^5)$ per multiplication. The second perfectly-secure protocol requires more number of synchronous rounds, namely (21, 7), but provides a better communication complexity of $\mathcal {O}(n^4)$ per multiplication. So a tradeoff is attained between the amount of synchrony required and communication achieved per multiplication. The statistically-secure hybrid protocols of [15] with $t<n/3$ retain the same communication complexity as their perfect counterparts, but reduces the number of synchronous rounds. Namely the first statistically-secure protocol requires (7, 2) rounds and $\mathcal {O}(n^5)$ communication per multiplication, the second statistically-secure protocol requires (16, 6) rounds and $\mathcal {O}(n^4)$ communication per multiplication. As it is clear from these results, with $t<n/3$, significant improvement in the communication complexity is not achieved, even if partial synchrony is provided in the network. Our goal is to design more efficient hybrid MPC protocol with $t<n/3$ using minimal level of synchrony.

Our Results. We present a hybrid MPC protocol with $t<n/3$. Our protocol is statistically-secure, requires (4, 3) synchronous rounds and $\mathcal {O}(n^2)$ communication per multiplication. Moreover, our protocol also ensures input provision. Our protocol outperforms the existing hybrid MPC protocols with $t<n/3$, both in terms of communication complexity as well as in terms of the number of synchronous rounds required in the protocol.

To design our protocol, we follow the standard offline-online paradigm, based on Beaver’s circuit-randomization technique [2] and which is now the de facto style of designing efficient MPC protocols [3,4,5, 10, 14, 15]. In this paradigm, an MPC protocol is divided into two phases, a circuit-independent offline phase and a circuit-dependent online phase. While the offline phase generates “raw data”, independent of the circuit and actual inputs for the computation, the online phase utilizes this raw data for the circuit evaluation. In a more detail, the offline phase generates random multiplication triples of the form (a, b, c), Shamir-shared with threshold t; here a, b are random and private and $c = ab$ holds. Later, using such triples, multiplication gates are evaluated in a shared fashion. For each multiplication gate, one multiplication triple from the offline phase is utilized and the multiplication gate is evaluated at the cost of publicly reconstructing two Shamir-shared values. Reconstructing a Shamir-shared valued (with threshold t) can be done efficiently with $t<n/3$ using the standard Reed-Solomon (RS) error correction [31], even in a completely asynchronous setting [7, 11]. Hence we shift the focus to design an efficient offline phase in the hybrid setting for generating multiplication triples. For this we follow the recent framework of [15], which shows how to efficiently generate Shamir-shared multiplication triples in offline phase, using any (polynomial based) verifiable secret-sharing (VSS) protocol [13] as a black-box. Informally, a VSS protocol allows a designated party called dealer ($\mathsf {D}$) to verifiably Shamir-share a secret with threshold t. Thus at the end of the VSS protocol it is ensured that there exists some polynomial of degree at most t with the secret as the constant term and every share-holder has a distinct evaluation of this polynomial. Moreover this is ensured irrespective of whether the dealer is under the influence of the adversary or not. In addition, if the dealer is honest then it is ensured that the secret remains information-theoretically secure from t corrupted share-holders.

In this work, our proposed VSS protocol in the setting of $t<n/3$ is plugged into the framework of [15] and the result is a more efficient hybrid MPC protocol. Communication-wise, our VSS protocol stands out with an amortized overhead of $\mathcal {O}(n^2)$ per secret-shared value, whereas the best known bound is only $\mathcal {O}(n^3)$ [25, 28]. The improvement comes from the fact that our VSS protocol requires a broadcast complexity that is independent of the number of secrets shared, a property that is not achieved by the known constructions [25, 28]. To induce a better complexity over point-to-point channels, we use the best known broadcast amplification protocols (aka multi-valued broadcast protocols) [22] to simulate the broadcast invocations in the VSS protocols of [25, 28]. Informally, in a multi-valued protocol, broadcasting a “sufficiently large” message of size $\ell$ has communication complexity of $\mathcal {O}(n \ell )$ over point-to-point channels and a broadcast complexity of $\text{ poly }(n)$. With $t<n/3$, the most efficient multi-valued broadcast protocol is due to [35]. The protocol requires a communication complexity of $\mathcal {O}(n \ell )$ over point-to-point channels and broadcast of $n^2$ bits for broadcasting an $\ell$-bit message. Detailed analysis and comparison of our VSS with existing ones is deferred to the full version of the paper. In Fig. 1, we compare our MPC and VSS protocols with their previous best counter parts.

Fig. 1.

Comparison of our results with previous best results.

Other Related Work. In the synchronous setting, MPC protocols with $\mathcal {O}(n)$ communication per multiplication has been reported in [5] with perfect security and $t<n/3$ and in [10] with statistical security and $t<n/2$. These protocols deploy non-robust secret-sharing protocols in the player-elimination and dispute-control framework. The non-robustness of the underlying primitives inflates the round complexity of their offline phase to $\mathcal {O}(n)$ and $\mathcal {O}(n^2)$ respectively. The naive approach of adopting these protocols in hybrid setting will lead to protocols with $\mathcal {O}(n)$ or $\mathcal {O}(n^2)$ synchronous (broadcast) rounds to execute the offline phase. The online phase of these protocols can be executed asynchronously. Our hybrid MPC protocol on the other hand requires only a constant number of synchronous broadcast rounds.

The reported works [18, 19] in the synchronous setting with polylogarithmic (in n) communication per gate (denoted as $\widetilde{\mathcal {O}}(n)$)⁵ are only non-optimally resilient. While [19] works with $t < (\frac{1}{2} - \epsilon ) n$ and provides statistical security, [18] works with $t < (\frac{1}{3} - \epsilon ) n$ and provides perfect security, where $\epsilon > 0$. These protocols also evaluate the underlying circuit in a secret-shared fashion. However, instead of Shamir secret-sharing, they use packed secret-sharing [24] taking advantage of the presence of larger subset of honest parties (due to the non-optimal resilience). Due to the use of packed secret-sharing, “multiple” gates can be evaluated simultaneously by doing a fixed set of operations on the shares. However, this requires “special” structure from the underlying circuit being available at each layer, maintaining which, demands additional circuitry to be incorporated between different layers of the circuit. Evaluating the overall circuit using packed secret-sharing makes these protocols highly non-trivial and complex. It is not known how to adapt these protocols in a completely asynchronous or a partially synchronous setting. Specifically, it is not clear whether these protocols can be executed in a hybrid setting, with a constant number of synchronous rounds. Therefore, while treating VSS as an MPC functionality and evaluating the resultant “VSS circuit” using the MPC protocols of [18, 19] may lead to sublinear (namely $\widetilde{\mathcal {O}}(n)$) overhead per secret-shared value, it is not clear if the resultant protocols runs with a constant number of synchronous rounds in hybrid setting.

New Techniques. Our VSS protocol is built upon a new primitive called information checking with succinct proof of possession (ICPoP) that takes motivation from information checking protocol (ICP) introduced in [16, 33, 36]. An ICP allows a $\mathsf {D}$ to privately authenticate some data for an intermediary $\mathsf {INT}$, who can later publicly reveal this data and prove that it originated from $\mathsf {D}$. On the other hand, in an ICPoP protocol $\mathsf {INT}$ gives a proof of possession publicly of the data originated from $\mathsf {D}$, instead of publicly revealing the data. The proof preserves data privacy and is “succinct” i.e. its size is independent of the size of the data. The succinctness of the proof makes the broadcast complexity of our VSS protocol independent of the number of shared secrets. Our ICPoP also offers transferability that allows any designated party to take possession of $\mathsf {INT}$’s authenticated (by $\mathsf {D}$) data and to be able to give a proof of possession on the “behalf” of $\mathsf {INT}$. The existing ICPs do not support transferability.

We next give a high level overview of our VSS. To share a secret s, we embed s in the constant term of a random bivariate polynomial F(x, y) of degree t in x and y. Every party $P_i$ then obtains a row polynomial $f_i(x) = F(x, \alpha _i)$. The parties then publicly verify whether the row polynomials of at least $n - t$ parties called $\mathsf {VCORE}$ define a unique bivariate polynomial. The standard way to do this is to perform the “pair-wise checking”, where every pair of parties $(P_i, P_j)$ is asked to verify the consistency of the common values on their respective polynomials and publicly complain if there is any inconsistency, in which case $\mathsf {D}$ publicly resolves the complaint by making the common value public [21, 25, 28]. This approach will lead to a broadcast complexity of $\mathcal {O}(n^2)$ per secret-shared value; instead we use a statistical protocol called $\mathsf {Poly}\text{- }\mathsf {Check}$ (Sect. 4.1), adapted from [34], which performs the same task in parallel for $\ell$ secrets (and hence $\ell$ bivariate polynomials), but keeping the broadcast complexity independent of $\ell$. Once $\mathsf {VCORE}$ is found, it is ensured that $\mathsf {D}$ has committed a unique F(x, y) and the secret F(0, 0) to the parties in $\mathsf {VCORE}$. To enable the parties to obtain their shares, the goal will be to enable each party $P_j$ to compute its column polynomial $g_j(y) = F(\alpha _j, y)$. For this each party $P_i \in \mathsf {VCORE}$ transfers its common value on $g_j(y)$ (namely $f_i(\alpha _j)$) to $P_j$. To ensure that correct values are transferred, $P_j$ publicly gives a proof of possession of all the transferred values originated from $\mathsf {D}$ via the intermediary parties in $\mathsf {VCORE}$. This is done in parallel for $\ell$ secrets (and hence $\ell$ bivariate polynomials); the succinctness of the proof ensures that this step has broadcast complexity, independent of $\ell$.

2 Network Model, Definitions and Existing Tools

We consider a set $\mathcal {P}= \{P_1, \ldots , P_n\}$ of n parties, connected by pair-wise private and authentic channels. For simplicity we assume $n = 3t + 1$, so $t = \varTheta (n)$. There exists a computationally unbounded adversary $\mathsf {Adv}$ who can maliciously corrupt any t parties and may force them to behave in any arbitrary fashion during the execution of a protocol. We assume the adversary to be static, who decides the set of corrupted parties at the beginning of the protocol execution. We assume a partially synchronous network, where the first four rounds are synchronous, after which the entire communication is done asynchronously. Moreover, we assume that the parties have access to a broadcast channel during the second, third and fourth synchronous round. Our protocols operate over a finite field $\mathbb {F}$, where $|\mathbb {F}| > 2n$. We assume that there exists 2n distinct non-zero elements $\alpha _1, \ldots , \alpha _n, \beta _1, \ldots , \beta _n$ in $\mathbb {F}$. Each element of $\mathbb {F}$ can be represented by $\mathcal {O}(\log {|\mathbb {F}|})$ bits. The communication complexity of any protocol is defined to be the total number of field elements communicated by the honest parties in that protocol. We denote the point-to-point communication complexity by $\mathcal {PC}()$ and the broadcast communication complexity as $\mathcal {BC}()$.

Without loss of generality, we assume that the parties want to securely compute the function $f: \mathbb {F}^n \rightarrow \mathbb {F}$ via an MPC protocol, where $f(x_1, \ldots , x_n) = y$, such that $x_i \in \mathbb {F}$ is the input of $P_i$ and every party is supposed to receive the output $y \in \mathbb {F}$. The function f is assumed to be represented by a publicly known arithmetic circuit C over $\mathbb {F}$. The circuit C consists of n input gates, two-input addition (linear) and multiplication (non-linear) gates, zero-input random gates (for generating random values during the computation) and one output gate. We denote by $c_M$ and $c_R$ the number of multiplication and random gates in C respectively. By [X] and [X, Y] for $Y\ge X$, we denote the sets $\{1, \ldots , X \}$ and $\{X, X+1, \ldots , Y\}$, respectively. We use $i \in [k ]$ to denote that i can take a value from the set $\{1, 2 \dots k\}$. We will also require that $|\mathbb {F}| > 4n^4(c_M + c_R)(3t+1)2^{\kappa }$ to ensure that the error-probability of our MPC protocol is at most $2^{-\kappa }$, for a given error parameter $\kappa$.

2.1 Definitions

Definition 1

( d -sharing [3, 5, 20]). A value $s \in \mathbb {F}$ is said to be d-shared if there exists a polynomial over $\mathbb {F}$, say $f(\cdot )$, of degree at most d, such that $f(0) = s$ and every (honest) party $P_i \in \mathcal {P}$ holds a share $s_i$ of s, where $s_i = f(\alpha _i)$. We denote by $[s]_d$, the vector of shares of s corresponding to the (honest) parties in $\mathcal {P}$.

A vector $\varvec{S} = (s^{(1)}, \ldots , s^{(\ell )}) \in \mathbb {F}^{\ell }$ is said to be d-shared if each $s^{(i)}$ is d-shared. Note that d-sharings are linear: given $[a]_d$ and $[b]_d$, then $[a+b]_d = [a]_d + [b]_d$ and $[c \cdot a]_d = c \cdot [a]_d$ holds, for a public constant c. In general, given $\ell$ sharings $[x^{(1)}]_d, \ldots , [x^{(\ell )}]_d$ and a public linear function $g: \mathbb {F}^{\ell } \rightarrow \mathbb {F}^m$, where $g(x^{(1)}, \ldots , x^{(\ell )}) = (y^{(1)}, \ldots , y^{(m)})$, then $g([x^{(1)}]_d, \ldots , [x^{(\ell )}]_d) = ([y^{(1)}]_d, \ldots , [y^{(m)}]_d)$. We say that the parties locally compute $([y^{(1)}]_d, \ldots , [y^{(m)}]_d) = g([x^{(1)}]_d, \ldots , [x^{(\ell )}]_d)$ to mean that every $P_i$ (locally) computes $(y^{(1)}_i, \ldots , y^{(m)}_i) = g(x^{(1)}_i, \ldots , x^{(\ell )}_i)$, where $y^{(l)}_i$ and $x^{(l)}_i$ denotes the $i^{th}$ share of $y^{(l)}$ and $x^{(l)}$ respectively.

Definition 2

(Polynomial-based) Verifiable Secret Sharing (VSS) [3,4,5]). Let $\varvec{S} = (s^{(1)}, \ldots , s^{(L)}) \in \mathbb {F}^{L}$ be a set of L values that a dealer $\mathsf {D}\in \mathcal {P}$ wants to t-share among $\mathcal {P}$. Let $\mathsf {Sh}$ be a protocol for the n parties, where $\mathsf {D}$ has the input $\varvec{S}$. Then $\mathsf {Sh}$ is a VSS scheme if the following holds for every possible $\mathsf {Adv}$, on all possible inputs: (1) Correctness: If $\mathsf {D}$ is honest then $\varvec{S}$ is t-shared among $\mathcal {P}$ at the end of $\mathsf {Sh}$. Moreover even if $\mathsf {D}$ is corrupted there exists a set of L values, say $(\overline{s}^{(1)}, \ldots , \overline{s}^{(L)})$, which is t-shared among $\mathcal {P}$ at the end of $\mathsf {Sh}$. (2) Privacy: If $\mathsf {D}$ is honest then $\mathsf {Sh}$ reveals no information about $\varvec{S}$ to $\mathsf {Adv}$ in the information-theoretic sense; i.e. $\mathsf {Adv}$’s view is identically distributed for all possible $\varvec{S}$.

If $\mathsf {Sh}$ satisfies all its properties without any error then it is called perfectly-secure. If the correctness is satisfied with probability at least $1 - \epsilon$, for a given error parameter $\epsilon$, then it is called statistically-secure.

Unconditionally-secure MPC: Recent papers on efficient unconditionally-secure MPC follow a simpler “property based” security definition of secure MPC [3, 5, 10, 20], instead of the more rigorous “real-world/ideal-world” paradigm based definition [1, 29]. As our main goal is to provide an efficient VSS and MPC, to avoid blurring the main focus of the paper and to avoid additional technicalities, we also use the property based security definition. However, we confirm that using standard techniques, like the above efficient protocols, our MPC protocol can be also proved secure according to the simulation based definition. We defer the details to the full version of the paper.

Let $f: \mathbb {F}^n \rightarrow \mathbb {F}$ be a publicly known function and party $P_i$ has input $x_i \in \mathbb {F}$. In any (unconditionally-secure) multiparty computation, each party $P_i$ t-shares its input. Let $\mathsf {x}_i$ be the value shared by $P_i$. If $P_i$ is honest then $\mathsf {x}_i = x_i$. The parties then compute f as $y = f(\mathsf {x}_1, \ldots , \mathsf {x}_n)$ and everyone receives y.

Definition 3

(Unconditionally-secure MPC). A protocol $\varPi$ among the n parties securely computes f, if it satisfies the following for every possible $\mathsf {Adv}$, on all possible inputs: (1) Correctness: All honest parties obtain y at the end of $\varPi$. (2) Privacy: $\mathsf {Adv}$ obtains no additional information about the inputs of the honest parties, other than what is inferred from the inputs of the corrupted parties and y. Protocol $\varPi$ is called perfectly-secure if it satisfies all its properties without any error. If the correctness is satisfied with probability at least $1 - 2^{-\kappa }$, for a given error parameter $\kappa$, then $\varPi$ is called statistically-secure.

Information Checking with Succinct Proof of Possession (ICPoP): An ICPoP protocol involves three entities: a designated dealer $\mathsf {D}$ $\in$ $\mathcal {P}$ who holds a set of L private values $\mathcal {S}= \{s^{(1)}, \ldots , s^{(L)}\}$, an intermediary $\mathsf {INT}$ $\in$ $\mathcal {P}$ and the set of parties $\mathcal {P}$ acting as verifiers (note that $\mathsf {D}$ and $\mathsf {INT}$ will also play the role of verifiers, apart from their designated role of dealer and intermediary respectively). The protocol proceeds in three phases, each of which is implemented by a dedicated sub-protocol: (1) Distribution Phase: Here $\mathsf {D}$, sends $\mathcal {S}$ to $\mathsf {INT}$ along with some auxiliary information. For the purpose of verification, some verification information is additionally sent to each individual verifier. (2) Authentication Phase: This phase is initiated by $\mathsf {INT}$ who interacts with $\mathsf {D}$ and the verifiers to ensure that the information it received from $\mathsf {D}$ is consistent with the verification information distributed to the individual verifiers. If $\mathsf {D}$ wants it can publicly abort this phase, which is interpreted as if $\mathsf {D}$ is accusing $\mathsf {INT}$ of malicious behaviour. (3) Revelation Phase: This phase is carried out by $\mathsf {INT}$ and the verifiers in $\mathcal {P}$ only if $\mathsf {D}$ has not aborted the previous phase. Here $\mathsf {INT}$ reveals a proof of possession of the values received from $\mathsf {D}$. The verifiers in $\mathcal {P}$ check this proof with respect to their verification information. Then based on certain criteria, each verifier either outputs $\mathtt {Accept Proof}$ (indicating that it accepts the proof) or $\mathtt {Reject Proof}$ (indicating that it rejects the proof).

Definition 4

(ICPoP). A triplet of protocols $(\mathsf {Distr}, \mathsf {AuthVal}, \mathsf {RevealPoP})$ (implementing the distribution, authentication and revelation phase respectively) is a (1 - $\epsilon$)-secure $\mathsf {ICPoP}$, for an error parameter $\epsilon$, if the following holds: (1) $\mathsf {ICPoP}$-Correctness1: If $\mathsf {D}$ and $\mathsf {INT}$ are honest, then each honest verifier $P_i \in \mathcal {P}$ outputs $\mathtt {Accept Proof}$ at the end of $\mathsf {RevealPoP}$. (2) $\mathsf {ICPoP}$-Correctness2: If $\mathsf {D}$ is corrupted and $\mathsf {INT}$ is honest and if $\mathsf {ICPoP}$ proceeds to $\mathsf {RevealPoP}$, then except with probability at most $\epsilon$, all honest verifiers output $\mathtt {Accept Proof}$ at the end of $\mathsf {RevealPoP}$. (3) $\mathsf {ICPoP}$-Correctness3: If $\mathsf {D}$ is honest, $\mathsf {INT}$ is corrupted, $\mathsf {ICPoP}$ proceeds to $\mathsf {RevealPoP}$ and if the honest verifiers output $\mathtt {Accept Proof}$, then except with probability at most $\epsilon$, the proof produced by $\mathsf {INT}$ corresponds⁶ to the values in $\mathcal {S}$. (4) $\mathsf {ICPoP}$-Privacy: If $\mathsf {D}$ and $\mathsf {INT}$ are honest, then information obtained by $\mathsf {Adv}$ during $\mathsf {ICPoP}$ is independent of $\mathcal {S}$. (5) $\mathsf {ICPoP}$-Succinctness of the Proof: The size of the proof produced by $\mathsf {INT}$ during $\mathsf {RevealPoP}$ is independent of L.

Properties of Polynomials: A bivariate polynomial F(x, y) of degree at most t is of the form $F(x, y) = \sum _{i, j = 0}^{i, j = t}r_{ij}x^i y^j$, where $r_{ij} \in \mathbb {F}$. Let $f_i(x) {\mathop {=}\limits ^{\text{ def }}}F(x, \alpha _i), g_i(y) {\mathop {=}\limits ^{\text{ def }}}F(\alpha _i, y)$ for $i \in [n]$. We call $f_i(x)$ and $g_i(y)$ as ith row polynomial and column polynomial respectively of F(x, y). We say that a row polynomial $\overline{f}_i(x)$ lies on a bivariate polynomial F(x, y) of degree at most t if $F(x, \alpha _i) = \overline{f}_i(x)$ holds. Similarly we will say that a column polynomial $\overline{g}_i(y)$ lies on F(x, y) if $F(\alpha _i, y) = \overline{g}_i(y)$ holds. We will use the following well known standard properties of bivariate and univariate polynomials.

Lemma 1

([1, 11, 34]). Let $f_1(x), \ldots , f_{\ell }(x), g_1(y), \ldots , g_{\ell }(y)$ be degree t univariate polynomials with $t+1 \le \ell \le n$, such that $f_i(\alpha _j) = g_j(\alpha _i)$ holds for every $\alpha _i, \alpha _j \in \{\alpha _1, \ldots , \alpha _{\ell } \}$. Then there exists a unique bivariate polynomial $\overline{F}(x, y)$ of degree t, such that $f_i(x)$ and $g_i(y)$ lie on $\overline{F}(x, y)$, for $i \in [\ell ]$.

Lemma 2

([1, 11, 34]). Let $f_1(x), \ldots , f_{\ell }(x)$ be univariate polynomials of degree at most t where $t+1 \le \ell \le n$. Let F(x, y) and G(x, y) be two bivariate polynomials of degree at most t, such that $f_i(x)$ lies on both F(x, y) and G(x, y) for each $i \in [\ell ]$. Then $F(x, y) = G(x, y)$.

Lemma 3

([34]). Let $G^{(1)}(x), \dots G^{(L)}(x)$ be degree $\mathsf {d}$ polynomials and let $A(x) {\mathop {=}\limits ^{\text{ def }}}eG^{(1)}(x) + \dots + e^L G^{(L)}(x)$, where e is a random value from $\mathbb {F}\setminus \{0\}$. Let a tuple $(\gamma , v_{1}, v_{2}, \dots v_{L})$ be such that $v_{i} \ne G^{(i)}(\gamma )$ for some $i \in [L]$. Then except with probability at most $\frac{L-2}{|\mathbb {F}| - 1}$, the condition $A(\gamma ) \ne ev_{1} + \ldots e^L v_{L}$ holds.

Lemma 4

([34]). Let $h^{(0)}(y), \dots h^{(L)}(y)$ be $L+1$ polynomials and r be a random value from $\mathbb {F}\setminus \{0\}$. Let $h_{com}(y) {\mathop {=}\limits ^{\text{ def }}}h^{(0)}(y) + r h^{(1)}(y) + \dots r^{L} h^{(L)}(y)$. If at least one of $h^{(0)}(y), \dots h^{(L)}(y)$ has degree more than t, then except with probability at most $\frac{L}{|\mathbb {F}|}$, the polynomial $h_{com}(y)$ will have degree more than t.

3 Efficient ICPoP

We present a $(1 - \epsilon )$-secure $\mathsf {ICPoP}$ protocol, where $|\mathcal {S}| = L = \ell \times \mathsf {pack}$, with $\ell \ge 1$ and $1 \le \mathsf {pack}\le n - t$; moreover $\epsilon = \max \{\frac{n \ell }{|\mathbb {F}| - 1}, \frac{n(n-1)}{|F| - \mathsf {pack}}\}$. The protocol has communication complexity $\mathcal {PC}(\mathcal {O}(n \ell ))$ and $\mathcal {BC}(\mathcal {O}(n))$. Hence the broadcast complexity is independent of $\ell$. Our ICPoP is similar to the asynchronous ICP of [33], adapted to the synchronous setting with the following differences: in ICP the whole $\mathcal {S}$ is revealed during the revelation phase, as only its authenticity is required during the revelation phase. We require $\mathsf {INT}$ to be able to publicly prove the possession of $\mathcal {S}$ while maintaining its privacy. Hence the auxiliary information distributed in our ICPoP differs and also used differently; the details follow.

Let $\mathcal {S}= \{(s^{(1, 1)}, \ldots , s^{(1, \mathsf {pack})}), \ldots , (s^{(\ell , 1)}, \ldots , s^{(\ell , \mathsf {pack})})\}$. During the distribution phase, $\mathsf {D}$ embeds the values $(s^{(k, 1)}, \ldots , s^{(k, \mathsf {pack})})$ for $k \in [\ell ]$ in a random degree $\mathsf {d}$ secret-encoding polynomial $G^{(k)}(x)$ at $x = \beta _1, \ldots , \beta _{\mathsf {pack}}$, where $\mathsf {d}= \mathsf {pack}+ t - 1$. In addition, $\mathsf {D}$ picks a masking set $\mathcal {M}$, consisting of $2 \cdot \mathsf {pack}$ random values $\{ (m^{(1, 1)}, \ldots , m^{(1, \mathsf {pack})}), (m^{(2, 1)}, \ldots , m^{(2, \mathsf {pack})})\}$, which are embedded in two random degree $\mathsf {d}$ polynomials $H^{(1)}(x)$ and $H^{(2)}(x)$ respectively at $x = \beta _1, \ldots , \beta _{\mathsf {pack}}$; we call these polynomials as masking polynomials. The polynomials are sent to $\mathsf {INT}$, while each verifier $P_i$ receives the values $v_{1, i}, \ldots , v_{\ell , i}, m_{1, i}, m_{2, i}$ of these polynomials at a secret evaluation point $\gamma _i$. This distribution achieves $\mathsf {ICPoP}$-Privacy, as each secret-encoding polynomial has degree $\mathsf {d}$ and adversary may get at most t values on these polynomials; so it will lack $\mathsf {pack}$ values on each polynomial to uniquely interpolate them.

During revelation phase, to give a proof of possession of $\mathcal {S}$, $\mathsf {INT}$ produces a random linear combination of the values in $\mathcal {S}\cup \mathcal {M}$ by making public a random linear combiner, say e and a linear combination $C(x) {\mathop {=}\limits ^{\text{ def }}}e H^{(1)}(x) + e^2 H^{(2)}(x) + e^3 G^{(1)}(x) + \ldots + e^{\ell + 2} G^{(\ell )}(x)$. The values $C(\beta _1), \ldots , C(\beta _{\mathsf {pack}})$ define $\mathsf {pack}$ linear combinations of $\mathcal {S}\cup \mathcal {M}$ with respect to e. The pair (e, C(x)) is considered as a proof of possession of $\mathcal {S}$ (union $\mathcal {M}$) and verified as follows: each verifier locally verifies if the corresponding linear combination $e m_{1, i} + e^2 m_{2, i} + e^3 v_{1, i} + \ldots + e^{\ell + 2}v_{\ell , i}$ satisfies C(x) at $x = \gamma _i$ and accordingly broadcast an $\mathtt {Accept}$ or a $\mathtt {Reject}$ message. If more than t verifiers broadcast $\mathtt {Accept}$ then the proof (e, C(x)) is said to be accepted, otherwise it is rejected. The proof will always be accepted for an honest $\mathsf {D}$ and $\mathsf {INT}$, implying $\mathsf {ICPoP}$-Correctness1. The size of the proof is $\mathcal {O}(n)$ (as $\mathsf {d}= \mathcal {O}(n)$), which is independent of $\ell$, implying $\mathsf {ICPoP}$-Succinctness of the Proof. No additional information about the secret-encoding polynomials is revealed from C(x), thanks to the masking polynomials. If $\mathsf {D}$ is honest and $\mathsf {INT}$ is corrupted then the evaluation points of the honest verifiers will be private. So if $\mathsf {INT}$ gives a proof of possession of $\mathcal {S}^{\star } \cup \mathcal {M}^{\star } \ne \mathcal {S}\cup \mathcal {M}$ by revealing a linear combination of $\mathcal {S}^{\star } \cup \mathcal {M}^{\star }$ through $(e, C^{\star }(x))$ where $C^{\star }(x) \ne C(x)$, then with high probability, every honest verifier will reject the proof. This is because the corresponding linear combination of the values possessed by the honest verifiers will fail to satisfy $C^{\star }(x)$; this implies $\mathsf {ICPoP}$-Correctness 3.

The above mechanism, however, fails to achieve $\mathsf {ICPoP}$-Correctness 2, as a corrupted $\mathsf {D}$ can distribute “inconsistent” polynomials and values to an honest $\mathsf {INT}$ and honest verifiers respectively; later on the proof produced by $\mathsf {INT}$ will be rejected by every honest verifier. To verify the consistency of the distributed information, during the authentication phase, $\mathsf {INT}$ “challenges” $\mathsf {D}$ by making public a random linear combination A(x) of the received polynomials. In response, $\mathsf {D}$ either instructs to abort the protocol or continue, after verifying whether the A(x) polynomial satisfies the corresponding random linear combination of the values held by each verifier. The idea here is that if $\mathsf {D}$ distributed inconsistent data, then with very high probability, any random linear combination of the distributed polynomials would fail to satisfy the corresponding linear combination of the values given to the honest verifiers. And this will be locally learned by the honest verifiers after A(x) is made public. So if $\mathsf {D}$ still instructs to continue the protocol, then clearly $\mathsf {D}$ is corrupted; so later even if the proof produced in the revelation phase turns out to be inconsistent with the information held by the honest verifiers, the proof is accepted by adding an additional acceptance condition to deal with this particular case. We stress that the additional acceptance condition never gets satisfied for an honest $\mathsf {D}$ and a corrupted $\mathsf {INT}$. The privacy of the secret-encoding polynomials is still preserved during the authentication phase (for an honest $\mathsf {INT}$ and $\mathsf {D}$), thanks to the masking polynomials⁷. The formal steps of ICPoP are given in Fig. 3. In the protocol, if the output is $\mathtt {Accept Proof}$ then we additionally let the parties output $\mathsf {pack}$ linear combinations of the values in $\mathcal {S}\cup \mathcal {M}$ possessed by $\mathsf {INT}$; looking ahead this will be useful in our VSS. In Fig. 2 we give a pictorial representation of the values distributed and revealed in ICPoP.

Fig. 2.

Pictorial representation of the information generated and communicated during $\mathsf {ICPoP}$ protocol.

In ICPoP, the correspondence between a proof and a set of values is defined as follows: Let $\mathcal {S}= \{(s^{(1, 1)}, \ldots , s^{(1, \mathsf {pack})}), \ldots , (s^{(\ell , 1)}, \ldots , s^{(\ell , \mathsf {pack})})\}$ and $\mathcal {M}= \{ (m^{(1, 1)}, \ldots , m^{(1, \mathsf {pack})}), (m^{(2, 1)}, \ldots , m^{(2, \mathsf {pack})})\}$. We say that a proof (e, C(x)) corresponds to $\mathcal {S}\cup \mathcal {M}$ if C(x) embeds linear combination of $\mathcal {S}\cup \mathcal {M}$ with respect to e at $x = \beta _1, \ldots , \beta _{\mathsf {pack}}$; i.e. if $C(\beta _i) = em^{(1, i)} + e^2 m^{(2, i)} + e^3 s^{(1, i)} + \ldots + e^{(\ell + 2)}s^{(\ell , i)}$ holds for $i \in [\mathsf {pack}]$.

Fig. 3.

Efficient ICPoP protocol where $\ell \ge 1$ and $1 \le \mathsf {pack}\le n - t$.

We state the properties of our $\mathsf {ICPoP}$ and the final theorem. We give proofs for the important properties; the other proofs are simple and will appear in the full version.

Lemma 5

( $\mathsf {ICPoP}$ -Correctness1). If $\mathsf {D}$ and $\mathsf {INT}$ are honest then each honest verifier $P_i \in \mathcal {P}$ outputs $\mathtt {Accept Proof}$ along with $(C(\beta _1), \ldots , C(\beta _{\mathsf {pack}}))$ at the end of $\mathsf {RevealPoP}$.

Lemma 6

( $\mathsf {ICPoP}$ -Correctness2). If $\mathsf {D}$ is corrupt and $\mathsf {INT}$ is honest, and if $\mathsf {ICPoP}$ proceeds to $\mathsf {RevealPoP}$, then all honest verifiers output $\mathtt {Accept Proof}$, except with probability at most $\frac{n \ell }{|\mathbb {F}| - 1}$.

Proof

We claim that if $\mathsf {INT}$ is honest and $\mathsf {ICPoP}$ proceeds to $\mathsf {RevealPoP}$, then an honest verifier $P_i$ broadcasts $\mathtt {Accept}$, except with probability at most $\frac{\ell }{|\mathbb {F}| - 1}$. Assuming that the claim is true, from the union bound it follows that the probability any honest verifier fails to broadcast an $\mathtt {Accept}$ message is at most $\frac{n \ell }{|\mathbb {F}| - 1}$, as the number of honest parties is upper bounded by n. This ensures that there will be more than t $\mathtt {Accept}$ messages broadcasted by honest verifiers implying that each honest verifier outputs $\mathtt {Accept Proof}$ at the end of $\mathsf {RevealPoP}$.

We next proceed to prove our claim. For this we focus on a designated honest verifier $P_i$ and consider the relationship that holds between the polynomials $\overline{G}^{(1)}(x), \ldots , \overline{G}^{(\ell )}(x), \overline{H}^{(1)}(x), \overline{H}^{(2)}(x)$ distributed by a corrupted $\mathsf {D}$ to $\mathsf {INT}$ and the tuple $(\overline{\gamma }_i, \overline{v}_{1, i}, \overline{v}_{2, i}, \dots \overline{v}_{\ell , i}, \overline{m}_{1, i}, \overline{m}_{2, i})$ distributed by $\mathsf {D}$ to $P_i$. We have two cases:

• $\overline{v}_{k, i} = \overline{G}^{(k)}(\overline{\gamma }_i)$ for each $k \in [\ell ]$ and $\overline{m}_{1, i} = \overline{H}^{(1)}(\overline{\gamma }_i), \overline{m}_{2, i} = \overline{H}^{(2)}(\overline{\gamma }_i)$: In this case, the claim is true without any error as $P_i$ will find that condition C1 is true for the C(x) polynomial during $\mathsf {RevealPoP}$.

• At least one of the following holds — either $\overline{v}_{k, i} \ne \overline{G}^{(k)}(\overline{\gamma }_i)$ for some $k \in [\ell ]$ or $\overline{m}_{1, i} \ne \overline{H}^{(1)}(\overline{\gamma }_i)$ or $\overline{m}_{2, i} \ne \overline{H}^{(2)}(\overline{\gamma }_i)$: In this case, $A(\overline{\gamma }_i) \ne d\overline{m}_{1, i} + d^2 \overline{m}_{2, i} + d^3\overline{v}_{1, i} + d^4\overline{v}_{2, i} + \dots d^{\ell +2} \overline{v}_{\ell , i}$ holds, except with probability at most $\frac{\ell }{|\mathbb {F}| - 1}$ (follows from Lemma 3 by substituting $L = \ell + 2$). So clearly the verifier $P_i$ will find that condition C2 is true during $\mathsf {RevealPoP}$

Lemma 7

( $\mathsf {ICPoP}$ -Correctness3). If $\mathsf {D}$ is honest, $\mathsf {INT}$ is corrupted, $\mathsf {ICPoP}$ proceeds to $\mathsf {RevealPoP}$ and if the honest verifiers output $\mathtt {Accept Proof}$, then except with probability at most $\frac{n \mathsf {d}}{|\mathbb {F}| - \mathsf {pack}}$, the proof produced by $\mathsf {INT}$ corresponds to the values in $\mathcal {S}\cup \mathcal {M}$.

Lemma 8

( $\mathsf {ICPoP}$ -Privacy). If $\mathsf {D}$ and $\mathsf {INT}$ are honest, then the information obtained by $\mathsf {Adv}$ during $\mathsf {ICPoP}$ is independent of the values in $\mathcal {S}$.

Theorem 1

Protocols $(\mathsf {Distr}, \mathsf {AuthVal}, \mathsf {RevealPoP})$ constitute a $(1 - \epsilon )$-secure $\mathsf {ICPoP}$ for $L = \ell \times \mathsf {pack}$ values with $\ell \ge 1$ and $1 \le \mathsf {pack}\le n - t$, where $\epsilon = \max \{\frac{n \ell }{|\mathbb {F}| - 1}, \frac{n \mathsf {d}}{|F| - \mathsf {pack}}\}$ and $\mathsf {d}= \mathsf {pack}+ t - 1$. The protocol has communication complexity $\mathcal {PC}(\mathcal {O}(n \ell ))$ and $\mathcal {BC}(\mathcal {O}(n))$.

Proof

The properties of $\mathsf {ICPoP}$ follow from Lemmas 5–8. We next prove the communication complexity. During $\mathsf {Distr}$, $\mathsf {D}$ sends $\ell + 2$ polynomials of degree $\mathsf {d}$ to $\mathsf {INT}$ and a tuple of $\ell + 3$ values to each individual verifier. During $\mathsf {AuthVal}$ a polynomial of degree $\mathsf {d}$ is broadcasted by $\mathsf {INT}$ and $\mathsf {D}$ broadcasts either an $\mathtt {OK}$ or $\mathtt {Abort}$ message. During $\mathsf {RevealPoP}$, $\mathsf {INT}$ broadcasts a polynomial of degree $\mathsf {d}$ and each individual verifier broadcasts either an $\mathtt {Accept}$ or a $\mathtt {Reject}$ message. So overall the protocol has communication complexity $\mathcal {PC}(\mathcal {O}(n \ell ))$ and $\mathcal {BC}(\mathcal {O}(n))$, as $\mathsf {d}= \mathcal {O}(n)$. This also proves the $\mathsf {ICPoP}$-Succinctness of the Proof property, as the size of the proof is independent of $\ell$.

Transferability of ICPoP: In our VSS protocol we will use ICPoP as follows: after receiving $\mathcal {S}\cup \mathcal {M}$ from $\mathsf {D}$ via the secret-encoding and masking polynomials, $\mathsf {INT}$ will send these polynomials (and hence $\mathcal {S}\cup \mathcal {M}$) to another designated party, say $P_R \in \mathcal {P}$ (if $\mathsf {INT}$ is corrupted then it can send incorrect polynomials to $P_R$). Later on, party $P_R$ will act as an $\mathsf {INT}$ and produce a proof of possession of $\mathcal {S}\cup \mathcal {M}$, which got “transferred” to $P_R$ from $\mathsf {INT}$; the proof gets verified with respect to the verification information held by the verifiers. This transfer of $\mathcal {S}\cup \mathcal {M}$ will satisfy all the properties of ICPoP, imagining $P_R$ as the new $\mathsf {INT}$. Specifically if $\mathsf {D}$ is honest and both $\mathsf {INT}$ and $P_R$ are honest, then the privacy will hold. Moreover if $P_R$ produces a proof of possession of incorrect sets (this can be the case if either $\mathsf {INT}$ or $P_R$ is corrupted), then the proof gets rejected. If $\mathsf {D}$ is corrupted and both $\mathsf {INT}$ and $P_R$ are honest then the proof given by $P_R$ will be accepted.

4 Statistical VSS with a Quadratic Overhead

We present a 4-round VSS protocol $\mathsf {Sh}$ to t-share $\ell \times (n - t) = \varTheta (n \ell )$ values with communication complexity $\mathcal {PC}(\mathcal {O}(n^3 \ell ))$ and $\mathcal {BC}(\mathcal {O}(n^3))$. So for sufficiently large $\ell$, the broadcast complexity will be independent of $\ell$. For simplicity, we will present a 5-round statistical VSS protocol $\mathsf {Sh}\text{- }\mathsf {Single}$ for sharing a single secret. We will then explain how to reduce the number of rounds of $\mathsf {Sh}\text{- }\mathsf {Single}$ from five to four. Finally we extend this four round $\mathsf {Sh}\text{- }\mathsf {Single}$ to get $\mathsf {Sh}$. We first discuss a protocol $\mathsf {Poly}\text{- }\mathsf {Check}$ adapted from [34], used in our VSS.

4.1 Verifiably Distributing Values on Bivariate Polynomials of Degree at Most t

In our VSS protocol we will come across the following situation: $\mathsf {D}$ will select L bivariate polynomials $F^{(1)}(x, y), \ldots , F^{(L)}(x, y)$, each of degree at most t and send the ith row polynomials $f^{(1)}_i(x), \ldots , f^{(L)}_i(x)$ of $F^{(1)}(x, y), \ldots , F^{(L)}(x, y)$ respectively to each $P_i$; we stress that the corresponding column polynomials are retained by $\mathsf {D}$. The parties now want to publicly verify if there is a set of at least $t+1$ honest parties, who received row polynomials, lying on L unique bivariate polynomials of degree at most t without revealing any additional information about the polynomials. For this we use a two round protocol $\mathsf {Poly}\text{- }\mathsf {Check}$ (see Fig. 4), which is adapted from an asynchronous protocol for the same purpose, presented in [34].

In the protocol $\mathsf {Poly}\text{- }\mathsf {Check}$, there is a designated verifier $\mathsf {V}$, who challenges $\mathsf {D}$ to broadcast a random linear combination of the n column polynomials of all the bivariate polynomials selected by $\mathsf {D}$. Specifically $\mathsf {V}$ provides a challenge combiner, say r and in response $\mathsf {D}$ makes public a linear combination of its column polynomials with respect to r; to maintain the privacy of the column polynomials, this linear combination is blinded by a random degree t blinding polynomial B(y), selected by $\mathsf {D}$, with each party $P_i$ having a value on this polynomial. Corresponding to the linear combination of the column polynomials produced by $\mathsf {D}$, each party $P_i$ makes public a linear combination of n values of all its row polynomials, with respect to the combiner r, which is blinded by the value of B(y) possessed by it. The idea here is the following: if indeed there exists a set of $t+1$ honest parties that we are looking for, then the values of the row polynomials possessed by these parties will define degree t column polynomials. And these column and row polynomials will be “pair-wise consistent”. Based on this idea we check if the blinded linear combination of the column polynomials produced by $\mathsf {D}$ is of degree t. Moreover it is also checked if there exists a witness set $\mathcal {W}^{(\mathsf {V})}$ of at least $2t+1$ parties, such that their blinded linear combination of row polynomial values satisfies the linear combination produced by $\mathsf {D}$. If any one of the above conditions is not satisfied the parties output $\bot$, otherwise they output $\mathcal {W}^{(\mathsf {V})}$. It is ensured that if $\mathsf {V}$ is honest, then except with probability $\frac{nL}{|\mathbb {F}|}$, the honest parties in $\mathcal {W}^{(\mathsf {V})}$ constitute the desired set of row polynomial holders.

Fig. 4.

Checking the consistency of row polynomials distributed by $\mathsf {D}$ under the supervision of a designated verifier $\mathsf {V}$. The inputs for (an honest) $\mathsf {D}$ are L secret bivariate polynomials $F^{(1)}(x, y), \ldots , F^{(L)}(x, y)$ of degree at most t and a secret blinding polynomial B(y) of degree at most t. The inputs for (an honest) party $P_i$ are L row polynomials $\overline{f}^{(1)}_i(x), \ldots , \overline{f}^{(L)}_i(x)$ of degree at most t and a share $\overline{b}_i$ of blinding polynomial. If $\mathsf {D}$ and $P_i$ are honest then these values are private and $\overline{f}^{(k)}_i(x) = F^{(k)}(x, \alpha _i)$ and $\overline{b}_i = B(\alpha _i)$ will hold for each $k \in [L]$.

The properties of $\mathsf {Poly}\text{- }\mathsf {Check}$ are stated in Lemma 9; we refer to [34] for the complete proof.

Lemma 9

(Properties of Protocol $\mathsf {Poly}\text{- }\mathsf {Check}$ [34]). In protocol $\mathsf {Poly}\text{- }\mathsf {Check}$, the following holds:

• If $\mathsf {D}$ is honest then every honest party outputs a $\mathcal {W}^{(\mathsf {V})}$ set which includes all the honest parties. Moreover the row polynomials of the honest parties in $\mathcal {W}^{(\mathsf {V})}$ will lie on $F^{(1)}(x, y), \ldots , F^{(L)}(x, y)$. Furthermore $\mathsf {Adv}$ gets no additional information about $F^{(1)}(x, y), \ldots , F^{(L)}(x, y)$ in the protocol.

• If $\mathsf {D}$ is corrupted and $\mathsf {V}$ is honest and if the parties output a $\mathcal {W}^{(\mathsf {V})}$, then except with probability at most $\frac{nL}{|\mathbb {F}|}$, there exists L bivariate polynomials, say $\overline{F}^{(1)}(x, y), \ldots , \overline{F}^{(L)}(x, y)$, of degree at most t, such that the row polynomials of the honest parties in $\mathcal {W}^{(\mathsf {V})}$ lie on $\overline{F}^{(1)}(x, y), \ldots , \overline{F}^{(L)}(x, y)$.

• The protocol requires two rounds and has communication complexity $\mathcal {BC}(\mathcal {O}(n))$.

4.2 Five Round Statistical VSS for a Single Secret

To t-share s, $\mathsf {D}$ selects a random secret-carrying bivariate polynomial F(x, y) of degree at most t such that $s = F(0, 0)$. The ith row polynomial $f_i(x)$ of F(x, y) is given to each $P_i$. We stress that only the row polynomials are distributed. The parties then verify the consistency of the distributed polynomials by publicly verifying the existence of a set $\mathsf {VCORE}$ of at least $2t+1$ parties, such that the row polynomials of the honest parties in $\mathsf {VCORE}$ lie on a unique bivariate polynomial, say $\overline{F}(x, y)$, of degree at most t. For this, n instances of $\mathsf {Poly}\text{- }\mathsf {Check}$ are executed (one on the behalf of each party playing the role of the designated verifier $\mathsf {V}$) and it is verified if there is common subset of at least $2t+1$ parties, present across all the generated witness sets. As there will be at least one instance of $\mathsf {Poly}\text{- }\mathsf {Check}$ executed on the behalf of an honest verifier, clearly the common subset of $2t+1$ parties satisfies the properties of $\mathsf {VCORE}$. To maintain the privacy of the row polynomials during the $\mathsf {Poly}\text{- }\mathsf {Check}$ instances, n independent blinding polynomials are used by $\mathsf {D}$, one for each instance. If a $\mathsf {VCORE}$ is found, then we say that $\mathsf {D}$ has “committed” the secret $\overline{s}= \overline{F}(0, 0)$ to the parties in $\mathsf {VCORE}$ via their row polynomials and the next goal will be to ensure that each party $P_j$ obtains its column polynomial $\overline{g}_j(y)$ of $\overline{F}(x, y)$; party $P_j$ can then output its share $\overline{s}_j = \overline{g}_j(0)$ of $\overline{s}$ and hence $\overline{s}$ will be t-shared via $\overline{F}(x, 0)$. If $\mathsf {D}$ is honest then $\overline{F}(x, y) = F(x, y)$ will hold (and hence $\overline{s}= s$), as $\mathsf {VCORE}$ will include all the honest parties.

To enable $P_j$ obtain $\overline{g}_j(y)$, each $P_i \in \mathsf {VCORE}$ can send the common point $\overline{f}_i(\alpha _j)$ on $\overline{g}_j(y)$ to $P_j$, where $\overline{f}_i(\alpha _j)$ denotes the jth value on the ith row polynomial received by $P_i$ (if $\mathsf {D}$ is honest then $\overline{f}_i(\alpha _j) = f_i(\alpha _j)$ holds). The honest parties in $\mathsf {VCORE}$ will always send the correct values; however the corrupted parties may send incorrect values. Due to insufficient redundancy in the received $\overline{f}_i(\alpha _j)$ values, party $P_j$ cannot error-correct them (for this we require $|\mathsf {VCORE}|$ to be of size at least $3t+1$). The way out is that $P_j$ gives a proof of possession of the $\overline{f}_i(\alpha _j)$ values received from the parties $P_i$ in $\mathsf {VCORE}$. Namely the values on the row polynomials are initially distributed by $\mathsf {D}$ by executing instances of $\mathsf {Distr}$. There will be $n^2$ such instances and instance $\mathsf {Distr}_{ij}$ is executed to distribute $f_i(\alpha _j)$ to $P_i$, considering $P_i$ as an $\mathsf {INT}$; the corresponding instances $\mathsf {AuthVal}_{ij}$ are also executed and it is ensured that the $\mathsf {AuthVal}$ instances, involving any party from $\mathsf {VCORE}$ as an $\mathsf {INT}$, is not aborted by $\mathsf {D}$. Now when a party $P_i$ in $\mathsf {VCORE}$ sends $\overline{f}_i(\alpha _j)$ to $P_j$, party $P_j$ acts as an $\mathsf {INT}$ and publicly gives a proof of possession of $\overline{f}_i(\alpha _j)$ by executing an instance $\mathsf {RevealPoP}_{ji}$ of $\mathsf {RevealPoP}$. The idea is to use the transferability property of ICPoP to identify the incorrectly transferred values. Namely if $\mathsf {D}$ is honest and an incorrect $\overline{f}_i(\alpha _j)$ is transferred to $P_j$, then the corresponding proof gets rejected during $\mathsf {RevealPoP}_{ji}$ and $P_j$ discard such values.

Unfortunately, if $\mathsf {D}$ is corrupted then the above mechanism alone is not sufficient for $P_j$ to robustly reconstruct $\overline{g}_j(y)$. Because a corrupted $P_i$ in $\mathsf {VCORE}$ can then transfer an incorrect $\overline{f}_i(\alpha _j)$ to $P_j$ and still the proof will get accepted; this is because if both $\mathsf {D}$ and $\mathsf {INT}$ are corrupted, then $\mathsf {INT}$ will know the full auxiliary and verification information involved in ICPoP. As a result, $P_j$ will end up not reconstructing a degree t column polynomial from the received $\overline{f}_i(\alpha _j)$ values. To deal with this particular case, we ensure that the $\mathcal {M}$ sets used by $\mathsf {D}$ in the ICPoP instances have a similar “structure” as the corresponding $\mathcal {S}$ sets. Specifically, $\mathsf {D}$ selects two random masking bivariate polynomials $M^{(1)}(x, y)$ and $M^{(2)}(x, y)$ each of degree at most t. Let $m^{(1)}_i(x), m^{(2)}_i(x)$ denote the corresponding row polynomials. The instances $\mathsf {Distr}_{ij}$ are executed by setting $\mathcal {S}_{ij} = \{f_i(\alpha _j) \}$ and $\mathcal {M}_{ij} = \{ m^{(1)}_i(\alpha _j), m^{(2)}_i(\alpha _j)\}$ (thus $\ell = 1$ and $\mathsf {pack}= 1$ in these instances). The corresponding $\mathsf {AuthVal}_{ij}$ instances are executed with $\overline{\mathcal {S}}_{ij} = \{ \overline{f}_i(\alpha _j)\}$ and $\overline{\mathcal {M}}_{ij} = \{ \overline{m}^{(1)}_i(\alpha _j), \overline{m}^{(2)}_i(\alpha _j)\}$, which denotes the $\mathcal {S}$ and $\mathcal {M}$ sets respectively received by $P_i$ during $\mathsf {Distr}_{ij}$ (if $\mathsf {D}$ is honest then these will be the same as $\mathcal {S}_{ij}$ and $\mathcal {M}_{ij}$). The existence of $\mathsf {VCORE}$ will now imply that $\mathsf {D}$ has committed a secret-carrying polynomial, say $\overline{F}(x, y)$ and two masking bivariate polynomials, say $\overline{M}^{(1)}(x, y), \overline{M}^{(2)}(x, y)$ to the parties in $\mathsf {VCORE}$, where all these polynomials have degree at most t. It follows that any linear combination of the column polynomials $\overline{F}(\alpha _j, y), \overline{M}^{(1)}(\alpha _j, y)$ and $\overline{M}^{(2)}(\alpha _j, y)$ will be a degree t univariate polynomial. And this property is used by $P_j$ to identify the correctly transferred $\overline{\mathcal {S}}_{ij} \cup \overline{\mathcal {M}}_{ij}$ sets. Namely the values in the transferred $\overline{\mathcal {S}}_{ij} \cup \overline{\mathcal {M}}_{ij}$ sets should lie on degree t univariate polynomials and hence any random linear combination of these sets should also lie on a degree t polynomial. Based on this observation, party $P_j$ selects a common random combiner, say $e_j$, for all the transferred $\overline{\mathcal {S}}_{ij} \cup \overline{\mathcal {M}}_{ij}$ sets and publicly reveals a linear combination of these $\overline{\mathcal {S}}_{ij} \cup \overline{\mathcal {M}}_{ij}$ sets via the $\mathsf {RevealPoP}_{ji}$ instances. It is then publicly verified if these linearly combined values lie on a degree t polynomial. If not then it implies that $\mathsf {D}$ is corrupted and it is discarded; see Figs. 5 and 6 for the formal details. For the ease of understanding, a pictorial representation of the information distributed in $\mathsf {Sh}\text{- }\mathsf {Single}$ is given in Fig. 7.

Fig. 5.

VSS for sharing a single secret: Part I.

Fig. 6.

VSS for sharing a single secret: Part II.

Fig. 7.

Pictorial representation of the values distributed in $\mathsf {Sh}\text{- }\mathsf {Single}$ protocol.

We state the properties of $\mathsf {Sh}\text{- }\mathsf {Single}$ and formally prove the correctness of $\mathsf {Sh}\text{- }\mathsf {Single}$ in case of a corrupt dealer by means of a claim below. The remaining proofs will appear in the full version.

Lemma 10

If $\mathsf {D}$ is honest then except with probability at most $\frac{n^3t}{|\mathbb {F}| - 1}$, it is not discarded during $\mathsf {Sh}\text{- }\mathsf {Single}$.

Lemma 11

(Correctness for an honest $\mathsf {D}$ ). If $\mathsf {D}$ is honest then except with probability at most $\frac{n^3t}{|\mathbb {F}| - 1}$, the value s is t-shared at the end of $\mathsf {Sh}\text{- }\mathsf {Single}$.

Lemma 12

Let $\overline{f}_i(x), \overline{m}^{(1)}_i(x)$ and $\overline{m}^{(2)}_i(x)$ be the row polynomials defined by the values in $\overline{\mathcal {S}}_{ij} \cup \overline{\mathcal {M}}_{ij}$ received by party $P_i \in \mathcal {P}$ from $\mathsf {D}$ for $j \in [n]$. If $\mathsf {D}$ is corrupted and a $\mathsf {VCORE}$ is formed during $\mathsf {Sh}\text{- }\mathsf {Single}$ then except with probability at most $\frac{3n^2}{|\mathbb {F}|}$, there exist bivariate polynomials, say $\overline{F}(x, y), \overline{M}^{(1)}(x, y)$ and $\overline{M}^{(2)}(x, y)$, each of degree at most t, such that for each honest $P_i \in \mathsf {VCORE}$, the polynomials $\overline{f}_i(x), \overline{m}^{(1)}_i(x)$ and $\overline{m}^{(2)}_i(x)$ lie on $\overline{F}(x, y), \overline{M}^{(1)}(x, y)$ and $\overline{M}^{(2)}(x, y)$ respectively.

Proof

From the definition, $\mathsf {VCORE}= \mathcal {W}^{(P_1)} \cap \mathcal {W}^{(P_2)} \cap \ldots \cap \mathcal {W}^{(P_n)}$ and $|\mathsf {VCORE}| \ge 2t+1$. This ensures that there are at least $t+1$ common honest parties in $\mathsf {VCORE}$, say $\mathsf {HVCORE}$. Consider an honest party $P_j \in \mathcal {P}$, playing the role of the verifier $\mathsf {V}$ in the instance $\mathsf {Poly}\text{- }\mathsf {Check}^{(P_j)}$. It follows from Lemma 9 (by substituting $L = 3$) that for the instance $\mathsf {Poly}\text{- }\mathsf {Check}^{(P_j)}$, except with probability at most $\frac{3n}{|\mathbb {F}|}$, the row polynomials $\overline{f}_i(x), \overline{m}^{(1)}_i(x)$ and $\overline{m}^{(2)}_i(x)$ of the parties $P_i \in \mathsf {HVCORE}$ together lie on three unique bivariate polynomials, say $\overline{F}(x, y), \overline{M}^{(1)}(x, y)$ and $\overline{M}^{(2)}(x, y)$ respectively of degree at most t. The same will be true with respect to every other instance $\mathsf {Poly}\text{- }\mathsf {Check}^{(P_k)}$, corresponding to every other honest verifier $P_k \ne P_j$. Moreover, the set of three bivariate polynomials defined via each of these instances of $\mathsf {Poly}\text{- }\mathsf {Check}$ will be the same, namely $\overline{F}(x, y), \overline{M}^{(1)}(x, y)$ and $\overline{M}^{(2)}(x, y)$ respectively. This follows from Lemma 2 (by substituting $\ell = |\mathsf {HVCORE}|$) and the fact that $|\mathsf {HVCORE}| \ge t+1$. The lemma now follows from the union bound and the fact that there are $\varTheta (n)$ honest parties, playing the role of $\mathsf {V}$.

Lemma 13

(Correctness for a corrupted $\mathsf {D}$ ). If $\mathsf {D}$ is corrupted and not discarded during $\mathsf {Sh}\text{- }\mathsf {Single}$, then there exists some value, say $\overline{s}$, such that except with probability at most $\frac{n^3}{|\mathbb {F}| - 1}$, $\overline{s}$ is t-shared at the end of $\mathsf {Sh}\text{- }\mathsf {Single}$.

Proof

If a corrupted $\mathsf {D}$ is not discarded then it implies that a set $\mathsf {VCORE}$ with $|\mathsf {VCORE}| \ge 2t+1$ is constructed during $\mathsf {Sh}\text{- }\mathsf {Single}$. Let $\mathsf {HVCORE}$ be the set of honest parties in $\mathsf {VCORE}$; clearly $|\mathsf {HVCORE}| \ge t+1$. From Lemma 12 it follows that except with probability at most $\frac{3n^2}{|\mathbb {F}|}$, the row polynomials $\overline{f}_i(x), \overline{m}^{(1)}_i(x)$ and $\overline{m}^{(2)}_i(x)$ of the parties in $\mathsf {HVCORE}$ lie on unique bivariate polynomials, say $\overline{F}(x, y), \overline{M}^{(1)}(x, y)$ and $\overline{M}^{(2)}(x, y)$ of degree at most t. We define $\overline{s}{\mathop {=}\limits ^{\text{ def }}}\overline{F}(0, 0)$ and claim that $\overline{s}$ is t-shared via the polynomial $\overline{f}_0(x) {\mathop {=}\limits ^{\text{ def }}}\overline{F}(x, 0)$, with each honest $P_j$ holding the share $\overline{s}_j {\mathop {=}\limits ^{\text{ def }}}\overline{F}(\alpha _j, 0)$. To prove our claim, we show that each honest party $P_j$ outputs its degree t univariate polynomial $\overline{g}_j(y) {\mathop {=}\limits ^{\text{ def }}}\overline{F}(\alpha _j, y)$ except with probability at most $\frac{n^2}{|\mathbb {F}| - 1}$; this ensures that $P_j$ obtains the correct share, as $\overline{s}_j = \overline{g}_j(0)$. For this, we further need to show that the $\overline{\mathcal {S}}_{ij}$ set transferred by each party $P_i \in \sup _j$ to $P_j$ contains the value $\overline{g}_j(\alpha _i)$.

Consider an honest $P_j$. Notice that $\sup _j \subseteq \mathsf {VCORE}$. We first argue that every $P_i \in \mathsf {HVCORE}$ is present in $\sup _j$, except with probability at most $\frac{n^2}{|\mathbb {F}| - 1}$. This is because there are $\varTheta (n)$ such parties $P_i$ and in each corresponding $\mathsf {RevealPoP}_{ji}$ instance, the output is $\mathtt {Accept Proof}$, which follows from Lemma 6 (by substituting $\ell = 1$). Now consider the set of values $\overline{\mathcal {S}}_{ij} = \{\overline{f}_{ij}\}$ and $\overline{\mathcal {M}}_{ij} = \{\overline{m}^{(1)}_{ij}, \overline{m}^{(2)}_{ij} \}$ transferred by the parties $P_i \in \mathsf {HVCORE}$ to $P_j$. Since $\overline{f}_{ij} = \overline{f}_i(\alpha _j) = \overline{g}_j(\alpha _i)$ holds, it follows that the values $\{\overline{f}_{ij} \}_{P_i \in \mathsf {HVCORE}}$ define the degree t univariate polynomial $\overline{g}_j(y)$. Similarly the values $\{\overline{m}^{(1)}_{ij} \}_{P_i \in \mathsf {HVCORE}}$ and $\{\overline{m}^{(2)}_{ij} \}_{P_i \in \mathsf {HVCORE}}$ define degree t univariate polynomials $\overline{M}^{(1)}(y, \alpha _j)$ and $\overline{M}^{(2)}(y, \alpha _j)$ respectively. To complete the proof, we argue that except with probability at most $\frac{2}{|\mathbb {F}|}$, the values in the $\overline{\mathcal {S}}_{ij}$ and $\overline{\mathcal {M}}_{ij}$ set transferred by a corrupted party $P_i \in \sup _j$ lie on $\overline{g}_j(y), \overline{M}^{(1)}(y, \alpha _j)$ and $\overline{M}^{(2)}(y, \alpha _j)$ respectively. This is because the combiner $e_j$ selected by the honest $P_j$ in the $\mathsf {RevealPoP}_{ji}$ instances corresponding to the parties in $\sup _j$ is truly random and unknown to the adversary in advance, when the $\overline{\mathcal {S}}_{ij}$ and $\overline{\mathcal {M}}_{ij}$ sets are transferred to $P_j$. The rest follows from Lemma 4 (by substituting $L = 2$) and the fact that the values $\{ \mathsf {comb}_{ji}\}_{P_i \in \sup _j}$ lie on a polynomial of degree at most t (otherwise $\mathsf {D}$ would have been discarded), say $\mathsf {comb}_j(y)$, where $\mathsf {comb}_j(y) {\mathop {=}\limits ^{\text{ def }}}e_j \overline{M}^{(1)}(y, \alpha _j) + e_j^2 \overline{M}^{(2)}(y, \alpha _j) + e_j^3 \overline{g}_j(y)$. As there can be $n^2$ pair of parties involving a corrupted party, it follows by the union bound that except with probability at most $\frac{2n^2}{|\mathbb {F}|}$, the corrupted parties in $\mathsf {VCORE}$ transfer the correct values to the honest parties.

As each honest $P_j$ correctly obtains its column polynomial except with probability at most $\frac{n^2}{|\mathbb {F}| - 1}$ and as there are $\varTheta (n)$ such honest parties, it follows that except with probability at most $\frac{n^3}{|\mathbb {F}| - 1}$, the value $\overline{s}$ is t-shared.

Lemma 14

(Privacy). In protocol $\mathsf {Sh}\text{- }\mathsf {Single}$, the value s remains information theoretically secure.

Theorem 2

$\mathsf {Sh}\text{- }\mathsf {Single}$ is a five round VSS protocol for a single secret, satisfying the requirements of VSS except with probability $\frac{n^3t}{|\mathbb {F}| - 1}$. The protocol has communication complexity $\mathcal {PC}(\mathcal {O}(n^3))$ and $\mathcal {BC}(\mathcal {O}(n^3))$.

Proof

The properties of VSS follow from Lemmas 11–14. In the protocol $n^2$ instances of $\mathsf {ICPoP}$ (with $\ell = 1, \mathsf {pack}= 1$) and n instances of $\mathsf {Poly}\text{- }\mathsf {Check}$ (each with $L = 3$) are executed. The rest follows from the communication complexity of $\mathsf {ICPoP}$ (Theorem 1) and $\mathsf {Poly}\text{- }\mathsf {Check}$ (Lemma 9).

From Five Rounds to Four Rounds: In $\mathsf {Sh}\text{- }\mathsf {Single}$, the instances of $\mathsf {RevealPoP}$ which start getting executed during Round 4 can be instead instantiated during Round 3 itself. Namely irrespective of the formation of $\mathsf {VCORE}$, each party $P_j$ starts executing the instance $\mathsf {RevealPoP}_{ji}$ corresponding to each party $P_i \in \mathcal {P}$, based on the set of values in $\overline{\mathcal {S}}_{ij} \cup \overline{\mathcal {M}}_{ij}$ which were transferred to $P_j$ by $P_i$ during Round 2. Next $\mathsf {VCORE}$ is computed and if $P_i$ is found not to be present in $\mathsf {VCORE}$, then the instance $\mathsf {RevealPoP}_{ji}$ can be halted; otherwise the remaining steps of the $\mathsf {RevealPoP}_{ji}$ instance are executed during Round 4. Based on this modification, $\mathsf {Sh}\text{- }\mathsf {Single}$ now requires four rounds, the rest of the properties remain same.

Sharing $\ell \times (n - t)$ Secrets: To share $\ell \times (n - t)$ secrets, the underlying instances of $\mathsf {Distr}, \mathsf {AuthVal}$ and $\mathsf {RevealPoP}$ are executed to deal with $\ell \times \mathsf {pack}$ values simultaneously, where $\mathsf {pack}= n - t$. The steps for consistency checking of the values transferred by the parties in $\mathsf {VCORE}$ are also generalized to deal with $\ell \times (n - t)$ values. With these modifications, we get a four round $\mathsf {Sh}$ for sharing $\ell (n - t)$ values. The properties of $\mathsf {Sh}$ follow in a straight forward fashion from the corresponding properties of $\mathsf {Sh}\text{- }\mathsf {Single}$, taking into account that the underlying instances of $\mathsf {ICPoP}$ that are executed deal with $\ell \times (n - t)$ values. We state the theorem below. The proof will appear in the full version.

Theorem 3

$\mathsf {Sh}$ is a four round VSS for $\ell \times (n - t)$ values, with an error probability of $\max \{\frac{n^3(n - 1)}{|\mathbb {F}| - (n - t)}, \frac{n^3 \ell }{|\mathbb {F}| - 1}\}$. The protocol has communication complexity $\mathcal {PC}(\mathcal {O}(n^3 \ell ))$ and $\mathcal {BC}(\mathcal {O}(n^3))$.

5 Efficient Statistical MPC Protocol

Using $\mathsf {Sh}$, we design a statistical MPC protocol in the partially synchronous setting. The protocol is designed in the offline-online paradigm, where in the offline phase, the parties generate t-sharing of random and private multiplication triples of the form (a, b, c), where $c = ab$. Later in the online phase, these triples are used for the shared evaluation of the circuit using the standard Beaver multiplication triple based technique [2, 3, 5, 14]. For designing the offline phase protocol, we use the protocol $\mathsf {Sh}$ and deploy the efficient framework of [15]. The shared evaluation of the circuit is done in a completely asynchronous fashion in the online phase. We get the following theorem. The complete description of the protocol and the proof will appear in the full version.

Theorem 4

Let $f: \mathbb {F}^n \rightarrow \mathbb {F}$ be a function expressed as an arithmetic circuit over a finite field $\mathbb {F}$, consisting of $c_M$ and $c_R$ multiplication and random gates respectively. Assuming that the first four communication rounds are synchronous broadcast rounds after which the entire communication is asynchronous, there exists a statistical MPC protocol to securely compute f, provided $|\mathbb {F}| \ge 4n^4(c_M + c_R)(3t+1)2^{\kappa }$ for a given error parameter $\kappa$. The protocol has communication complexity $\mathcal {PC}(\mathcal {O}(n^2(c_M + c_R) + n^4))$ and $\mathcal {BC}(\mathcal {O}(n^4))$.