# How the degree reduction in BGW protocol works?

In the BGW protocol given in the original paper http://groups.csail.mit.edu/cis/pubs/shafi/1988-stoc.pdf

It says the after the randomization step every party $P_i$ finds its share $s_i = \tilde{h}(\alpha_i)$ on the polynomial $\tilde{h}(x) = h(x)+\sum^{n-1}_{j=0}q_j(x)$, and then it applies degree reduction on $\tilde{h}(x)$.

It defines vector $S = [s_0 s_1 \cdots s_{n-1}]$ and a constant matrix $A_{n\times n}$, such that $R = S.A$. where $R$ is the vector of shares of each party $P_i$ on polynomial $k(x)$ which is $t$-degree and $k(0) = \tilde{h}(0)=a.b$.

So, what is want to know that how this matrix multiplication is evaluated among the parties t-privately ? Because each party holds $s_i$ not known to any other party. How the whole $\mbox{truncate}(\tilde{h})$ is done ?

• Nov 15, 2016 at 16:16

## 1 Answer

I refer you to a full proof of the paper with all of the details on how the protocol works. See: http://eprint.iacr.org/2011/136.pdf.