I have some trouble understanding the linearization of the degree 2t polynomial generated by multiplication in BGW. It would be great if someone could decode this linearization in simple terms from a 2t degree polynomial to a t degree polynomial.

I've understood that in multiplication, we calculate r(x) = p(x)q(x) but this means that r(x) is a polynomial of degree 2t. How is this polynomial distributed linearly in the circuit?

Addition in BGW is easy to understand but multiplication has been difficult to comprehend.

Reference: https://www.csa.iisc.ac.in/~arpita/SecureComputation15/Lecture18.pdf

  • $\begingroup$ define BGW for completeness please. And give a link if applicable $\endgroup$
    – kodlu
    Commented Apr 26, 2020 at 8:58
  • 2
    $\begingroup$ Can you elaborate on what part of my answer to your similar question you had issues understanding? Asking a follow up question is completely fine, but I don't know what part of the answer to write differently. $\endgroup$
    – Mark Schultz-Wu
    Commented Apr 27, 2020 at 6:33
  • 1
    $\begingroup$ I've implemented the construction of the matrix that BGW uses in this code. Note that it uses real (or more properly floating point arithmetic) instead of Finite Field arithmetic, so there are some rounding errors. Playing around with those functions may help you understand more concretely that these things work (for example, there is explicit code implementing the creation of the Vandermonde matrix, and the code responsible for the 2t degree polynomial becoming t degree is the proj matrix in the trunc_matrix function). $\endgroup$
    – Mark Schultz-Wu
    Commented Apr 27, 2020 at 8:38
  • 1
    $\begingroup$ Understanding why the above all works on a conceptual level is slightly more difficult. I managed to feel pressed for space (while writing a quite long answer) on your previous question. I would suggest breaking down the problem of understanding BGW arithmetic into "How to take shares of a polynomial and "truncate" them via a linear operation" and "How to securely compute a linear operation of shares". All of my comments have been towards this first point. $\endgroup$
    – Mark Schultz-Wu
    Commented Apr 27, 2020 at 8:40
  • 1
    $\begingroup$ @rakshitnaidu That's pythons "matrix multiplication operator". $\endgroup$
    – Mark Schultz-Wu
    Commented Apr 27, 2020 at 19:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.