A Full Proof of the BGW Protocol for Perfectly Secure Multiparty Computation

In previous versions of this paper [1] and in [2], we mistakenly stated that using [10] it is possible to obtain full adaptive security with efficient simulation. However, this is actually not known, and [10] only proves that perfect security under [16] implies adaptive security with inefficient simulation, which is significantly weaker.

Throughout, when we refer to a polynomial of degree t, we mean of degree at most t.

This definition of the functionality assumes that all of the inputs lie on the polynomials \(f_a(x),f_b(x)\) and ignores the case that this does not hold. However, since we are dealing with the semi-honest case here, the inputs are always guaranteed to be correct. This can be formalized using the notion of a partial functionality [20, Sec. 7.2].

This is a specific VSS definition that is suited for the BGW protocol. We remark that it is possible to define VSS in a more general and abstract way (like a multiparty “commitment”). However, since we will need to compute on the shares \(q(\alpha _1),\ldots ,q(\alpha _n)\), these values need to be explicitly given in the output.

We remark that in the case of \(t<n/4\) (i.e., \(n\ge 4t+1\)), the parties can correct errors directly on degree-2t polynomials. Therefore, the parties can distribute subshares of the products \(a_i \cdot b_i\), and correct errors on these shares using (a variant of) the \(F_{VSS}^{subshare}\) functionality directly. Thus, overall, the case of \(t<n/4\) is significantly simpler, since there is no need for the \(F_{VSS}^{mult}\) subprotocol that was mentioned in the second step described above. A full specification of this simplification is described in “Appendix”; the description assumes familiarity with the material appearing in Sects. 6.2, 6.3, 6.4 and 6.7, and therefore should be read after these sections.

It actually suffices to send the shares \((q_1(\alpha _j),\ldots ,q_n(\alpha _j))\) only to parties \(P_j\) for \(j\notin I\) since all other parties have already received these values. Nevertheless, we present it in this way for the sake of clarity.

In the UC framework, the adversary can communicate directly with the ideal functionality and it is mandated that the adversary notifies the ideal functionality (i.e., trusted party) of the identities of all corrupted parties. Furthermore, ideal functionalities often utilize this information (i.e., they are corruption aware) since the way that the universal composability framework is defined typically requires functionalities to treat the inputs of honest and corrupted parties differently. See Section 6 of the full version of [9] for details.

This is needed because in \(F_{VSS}^{subshare}\) the parties need to output \(g_i(x)\) and so need to know it. It would be possible to have the functionality choose \(g_i(x)\) and provide it in the output, but then exactly the same issue would arise. This is explained in more detail in the next paragraph.

If all of the points sent by the honest parties lie on a single degree-t polynomial, then this guarantees that f(x) is the unique degree-t polynomial for which \(f(\alpha _j)=\beta _j\) for all \(j\notin I\). If not all the points lie on a single degree-t polynomial, then no security guarantees are obtained. However, since the honest parties all send their prescribed input, in our applications, f(x) will always be as desired. This can be formalized using the notion of a partial functionality [20, Sec. 7.2]. Alternatively, it can be formalized by as follows: In the case that the condition does not hold, the ideal functionality gives all of the honest parties’ inputs to the adversary and lets the adversary single-handedly determine all of the outputs of the honest parties. This makes any protocol vacuously secure (since anything can be simulated).

The corrupted parties also receive the vector of polynomials \((g_1(x),\ldots ,g_n(x))\cdot H^T\) as output from \(F_{mat}^H\). However, in the protocol, we only specify the honest parties’ instructions.

An alternative strategy could be to run the verification strategy of Protocol 5.6 for VSS on the shares \(C(\alpha _j)\) that the parties computed in order to verify that \(\{C(\alpha _j)\}_{j=1}^n\) define a degree-t polynomial. The problem with this strategy is that if C(x) is not a degree-t polynomial, then the protocol for \(F_{VSS}\) changes the points that the parties receive so that it is a degree-t polynomial. However, in this process, the constant term of the resulting polynomial may also change. Thus, there will no longer be any guarantee that the honest parties hold shares of a polynomial with the correct constant term.

The naming convention for the \(r_{i,j}\) values is as follows. In the first \(t-1\) coefficients, the first index in every \(r_{i,j}\) value is the index of the polynomial and the second is the place of the coefficient. That is, \(r_{i,j}\) is the jth coefficient of polynomial \(D_i(x)\). The values for the \(t^\mathrm{th}\) coefficient are used in the other polynomials as well, and are chosen to cancel out; see below.

As with \(F_{eval}\) and \(F_{VSS}^{mult}\), the simulator needs to receive the correct shares of the corrupted parties in order to simulate, and so this is also received as output. Since this information is anyway given to the corrupted parties, this makes no difference to the use of the functionality for secure computation.

We remark that the original \(\mathcal{S}\) could not work in this way since our proof that the simulations by \(\mathcal{S}\) and \(\mathcal{S}_1\) are identical uses the fact that the points \(\{A'_j(\alpha _i),B'_j(\alpha _i)_{i\in I; j\notin I},\{C'_j(\alpha _i)\}_{i\in I; j\notin I}\) alone suffice for simulation. This is true when computing \(\vec Y_A(x)\) and \(\vec Y_B(x)\) via the error vectors, but not when computing them from the actual polynomials as \(\mathcal{S}_2\) does.