0
$\begingroup$

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

Improve this question
$\endgroup$
10
  • $\begingroup$ define BGW for completeness please. And give a link if applicable $\endgroup$ – kodlu Apr 26 '20 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 Apr 27 '20 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 Apr 27 '20 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 Apr 27 '20 at 8:40
  • 1
    $\begingroup$ @rakshitnaidu That's pythons "matrix multiplication operator". $\endgroup$ – Mark Apr 27 '20 at 19:38

Your Answer

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

Browse other questions tagged or ask your own question.