2
$\begingroup$

I am reading Pragmatic MPC (link) about the BGW protocol. I also cross-reference here (click on lecture link for slides) *The BGW Construction for the Information Theoretic Setting – Benny Pinkas I do not understand why the multiplication gate calculation can work.

First, let's say of $N$ parties, party $P_i$ has shares of wires $\alpha$, $\beta$ as $[v_{\alpha}]$, $[v_{\beta}]$. He can multiply them together to get a point on the polynomial $q(x) = p_{\alpha}(x) p_{\beta}(x)$. But everyone's values together could then only be reconstructed with $q(x)$, where $q(x)$ is degree $2t$.

Useful fact: we say there exists $\lambda_i$ for $i =1 $ to $N$ (or can index to $2t+1$, but I didn't know why) such that $q(0) = \sum_{i=1}^N \lambda_i q(i)$ (I guess party $P_i$ has the value $q(i)$ in his possession). The $\lambda_i$ are the "appropriate Lagrange coefficients".

Every party $P_i$ can share their value $q(i)$. They pick $g_i$ such that $g_i(0) = q(i)$. (This polynomial was unnamed in the book, but maybe makes things more explicit). Then $P_i$ shares to all the parties so they have shares $[q(i)]$.

If we then think of what $P_i$ is receiving, he gets shares of $g_j(0)$ for each $j$, for him that means he gets the value $g_j(i)$.

Then, each $P_i$ on inputs $g_j(i)$ uses these points to create the share for himself $[q(0)] = \sum_{i=1}^N \lambda_i [q(i)]$. For party $P_i$, this means he can figure out $q(i) = \sum_{i=1}^n \lambda_i g_j(i)$.

The value $q(i)$ turns out to be their share $[v_{\alpha}v_{\beta}]$.

  1. I understand that these $\lambda_i$ should be the same as the one for the useful fact. Why?

  2. Where did the useful fact come from?

  3. I also took a look at a paper (didn't read through) of A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation link where they say that the $q(x)$ (they call it $h(x)$) has a "specific structure". What does it mean?

$\endgroup$
  • $\begingroup$ I am one of the authors of that book. I'm looking at Section 3.3 of the book and cannot find the part that you are talking about. You are using completely different variable names / terminology, and the book does not mention any "specific structure" of the degree-$2t$ polynomial (it only mentions that the degree is too high). I'm happy to help address any confusions, if you can clarify. $\endgroup$ – Mikero Sep 18 at 3:30
  • $\begingroup$ I changed the notation to fit the book better, and added some other references. I pulled up the original paper (Vandermonde matrix, but haven't read closely yet), and this might have the answer I'm seeking. $\endgroup$ – eternalmothra Sep 18 at 12:28
4
$\begingroup$

Where do $\lambda_i$'s come from?

Consider a polynomial of degree 4, $p(x) = p_4 x^4 + p_3 x^3 + \cdots + p_0$. We can write polynomial evaluation as a linear operation on the coefficients:

$$ \begin{bmatrix} p(1) \\ p(2) \\ p(3) \\ p(4) \\ p(5) \end{bmatrix} = \begin{bmatrix} 1^0 & 1^1 & 1^2 & 1^3 & 1^4 \\ 2^0 & 2^1 & 2^2 & 2^3 & 2^4 \\ 3^0 & 3^1 & 3^2 & 3^3 & 3^4 \\ 4^0 & 4^1 & 4^2 & 4^3 & 4^4 \\ 5^0 & 5^1 & 5^2 & 5^3 & 5^4 \end{bmatrix} \begin{bmatrix} p_0 \\ p_1 \\ p_2 \\ p_3 \\ p_4 \end{bmatrix} $$

The matrix in the middle is a Vandermonde matrix and hence it has full rank.

Now this also means that the rows of the Vandermonde matrix form a basis. So another vector like $[1~0~0~0~0]$ can be written as a linear combination of those rows, say:

$$ \begin{bmatrix}1 & 0 & 0 & 0 & 0\end{bmatrix} = \begin{bmatrix}\lambda_1 & \lambda_2 & \lambda_3 & \lambda_4 & \lambda_5\end{bmatrix} \begin{bmatrix} 1^0 & 1^1 & 1^2 & 1^3 & 1^4 \\ 2^0 & 2^1 & 2^2 & 2^3 & 2^4 \\ 3^0 & 3^1 & 3^2 & 3^3 & 3^4 \\ 4^0 & 4^1 & 4^2 & 4^3 & 4^4 \\ 5^0 & 5^1 & 5^2 & 5^3 & 5^4 \end{bmatrix} $$

Multiply on the right by the vector of coefficients and you can see that

$$ p(0) = p_0 = \sum_i \lambda_i p(i) $$

More generally, if you have $d+2$ distinct points $x_0, x_1, \ldots, x_{d+1}$, then there exist coefficients $\lambda_1, \ldots, \lambda_{d+1}$ with the following property: For any degree-$d$ polynomial $p$, you can write $p(x_0) = \sum_{i=1}^{d+1} \lambda_i p(x_i)$. The $\lambda_i$ coefficients are the coefficients of the "Vandermonde vector" of $x_0$ when written in the basis of the Vandermonde matrix on $x_1, \ldots, x_{d+1}$, which is indeed a nonsingular matrix.

What is "specific structure" ?

It says right there in the next sentence (p14 of this):

In addition, $h(x)$ generated in this way is not a “random polynomial” but has a specific structure. For example, $h(x)$ is typically not irreducible (since it can be expressed as the product of $f_a(x)$ and $f_b(x)$), and this may leak information.

If I were to rephrase what they say: Given degree-$t$ Shamir sharings of $a$ and $b$, everyone can locally (i.e., without communication) multiply their shares. The result is a degree-$2t$ sharing. But there are two problems:

  • If this wire is used in subsequent multiplication gates, we need the value to be shared on a degree-$t$ polynomial.

  • The wire might not used in subsequent multiplication gates. Consider the case where it is an output wire, then the only thing we do in that case is open all the shares (to reveal the output). Now it is true that the degree of the polynomial doesn't really matter. But the distribution of the polynomial matters because the entire polynomial is revealed when the shares are announced.

    Here the polynomial is known to be a product of two deg-$t$ polynomials. So if the polynomial is revealed, its factors are also revealed, and it could become obvious that $a$ is the constant term of one factor and $b$ is the constant term of the other factor. In other words, the protocol would leak $a$ and $b$ whereas we only wanted the product $ab$ to be revealed as output.

I'll note that the second "problem" can also be resolved by adding a random $2t$-sharing of 0 (instead of doing an interactive degree-reduction step). But in either case, the "raw" result of locally multiplying shares is not suitable for direct use. The protocol must include some mechanism to "sanitize" it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.