Product of secrets in multi-secret sharing schemes (aka packed secret sharing schemes)

The question is related to the multi-secret sharing scheme described in the following paper:

[FY92] Matthew K. Franklin, Moti Yung: Communication Complexity of Secure Computation (Extended Abstract). STOC 1992: 699-710 (Link)

Following is some background. However, if you're familiar with that paper, you can skip directly to the main question below (highlighted with bold header font).

A $(t-k+1,t+1;k,n)$-multi-secret sharing scheme, as defined in [FY92], allows a dealer to share $k $ secrets among $n$ players, such that any subset of $t+1$ players or more can recover the $k$ secrets, and any subset of players of size up to $t-k+1$ cannot learn any information about the $k$ secrets.

The multi-secret sharing scheme in [FY92] uses the following setting/system parameters:

• Let $F$ be a finite field.
• Let $s_1,\cdots,s_n \in F$ be the dealer's secrets.
• Let $\alpha_1,\cdots,\alpha_n$ and $e_1,\cdots,e_n$ be preselected elements of $F$ that are known all parties.
• Let $p(x) = q(x) \prod_{i=1}^{k}(x-e_i) + \sum_{i=1}^{k} s_i L_i(x)$, where $q(x) \in_R F[x]$ with $deg(q(x))=(t-k)$, and $$L_i(x)= \frac{\prod_{j\neq i}(x-e_j)}{\prod_{j\neq i}(e_i-e_j)}$$

The dealer distributes the share $p(\alpha_i)$ to Player $P_i$, for $1\leq i \leq n$. Any subset of players of size $\geq t+1$, can pool their shares together, and reconstruct the polynomial $p(x)$, and then compute the secrets $s_i = p(e_i)$ for $1\leq i \leq n$.

Conversely, for any subset of $t-k+1$ shares there is a single polynomial those shares and any $k$ secrets. Hence, any subset of $t-k+1$ players do learn any information about the $k$ secrets.

Computing the shares of the product of secrets from the shares of the individual secrets

Let $(y_1,\cdots,y_n)$ be the multi-share of secrets $(s'_1,\cdots,s'_n)$, and $(z_1,\cdots,z_n)$ be the multi-share of secrets $(s''_1,\cdots,s''_n)$. [FY92] describes an algorithm to compute the multi-share $(v_1,\cdots,v_n)$ of the product of secrets $(s'_1 s''_1,\cdots,s'_n s''_n)$ from the individual multi-shares $(y_1,\cdots,y_n)$ and $(z_1,\cdots,z_n)$.

The algorithm works as follows:

• Each player $P_i$ computes $w_i = y_i \times z_i$. This results in a tuple $(w_1,\cdots,w_n)$ that encodes the secrets $(s'_1 s''_1,\cdots,s'_n s''_n)$ using a $2t$-degree polynomial.
• Since a multi-secret share must use a $t$-degree polynomial, tuple $(w_1,\cdots,w_n)$ is not a valid multi-share of the secrets. Instead, it is called a pseudo multi-share.
• A degree-reduction procedure is needed to convert the $(w_1,\cdots,w_n)$ pseudo-multi-share to a valid multi-share $(v_1,\cdots,v_n)$, i.e., one that uses a degree-$t$ polynomial of the form $p(x) = q(x) \prod_{i=1}^{k}(x-e_i) + \sum_{i=1}^{k} s_i L_i(x)$ as described above.

Degree-reduction step and main focus/question of this post

[FY92] gives the following formula for computing the multi-share $(v_1,\cdots,v_n)$ from the pseudo multi-share $(w_1,\cdots,w_n)$. $$(w_1,\cdots,w_n). A = (v_1,\cdots,v_n)$$ where $$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chop_{t-k+1} B_\ell M_\ell$$ and

• $B_\ell$ is the vandermonde matrix whose $(i,j)$ entry is $(\alpha_j - e_\ell)^{i-1}$
• $Chop_{t-k+1}$ is the projection matrix on the first ${t-k+1}$ vectors of the space basis.
• $M_\ell$ is the matrix whose $(i,j)$ entry is $L_\ell(\alpha_i)$ for $i=j$, and zero everywhere else.

Main question of this post

The authors do not explain how they derived the formula. $$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chop_{t-k+1} B_\ell M_\ell$$

Can someone help me derive that formula or prove its correctness? [I have no doubt it's correct. I just want to figure out how the authors derived it]

Here's some of the approaches I have tried so far.

First, note that we can rewrite the polynomial used for sharing as a summ of $k$ terms as follows.

$$ \begin{alignat*}{2} p(x) &= q(x) \prod_{\ell=1}^{k}(x-e_\ell) + \sum_{\ell=1}^{k} s_\ell L_\ell(x) \\ &= q(x) \ \frac{1}{k} \sum_{\ell=1}^{k} \left(\prod_{\ell=1}^{k}(x-e_\ell)\right) + \sum_{\ell=1}^{k} s_\ell L_\ell(x) \\ &= q(x) \ \sum_{\ell=1}^{k} \left(\frac{(x-e_\ell)}{k} L_\ell(x) \right) + \sum_{\ell=1}^{k} s_\ell L_\ell(x) \\ &= \sum_{\ell=1}^{k} \left(\frac{q(x)(x-e_\ell)}{k} +s_\ell \right) L_\ell(x) \\ &= \sum_{\ell=1}^{k} q'_\ell(x) L_\ell(x) \end{alignat*} $$ where $q'_\ell(x)=\frac{1}{k}q(x)(x-e_\ell) +s_\ell$ is a $(t-k+1)$-degree polynomial.

Now assume we have two sets of secrets $(s'_1,\cdots,s'_n)$ and $(s''_1,\cdots,s''_n)$ shared through polynomials $p_1(x)$ and $p_2(x)$. The product $P(x)=p_1(x)p_2(x)$ is a $2t$-degree polynomial which can also be written as a sum of $k$ terms as shown below:

$$ \begin{alignat*}{2} P(x) &= p_1(x) p_2(x) \\ &= \sum_{\ell=1}^{k} q'_\ell(x) p_2(x) L_\ell(x)\\ &= \sum_{\ell=1}^{k} Q_\ell(x) L_\ell(x)\\ &= \sum_{\ell=1}^{k} Q'_\ell(x-e_\ell) L_\ell(x)\\ \end{alignat*} $$ where

• $Q_\ell(x)= q'_\ell(x) \ p_2(x)$ is a $(2t-k+1)$-degree polynomial, such that $Q_\ell(e_\ell)=s_\ell$ ($s_\ell = s'_\ell s''_\ell$ is the product of secrets we want to compute.)
• The polynomial $Q'_\ell(x)$ is obtained from $Q_\ell(x)$ through a change of variable, such that $Q'_\ell(x-e_\ell) = Q_\ell(x)$. In particular, $Q'_\ell(0) = Q_\ell(e_\ell) = s_\ell$.

Let $H_\ell=(h_{0,\ell},\cdots,h_{2t-k,\ell},0,\cdots,0)$ denote the vector of size $n$ containing the coefficients of $Q'_\ell$. In particular, we have $h_{0,\ell} = s_\ell$.

Let $(w_1,\cdots,w_n)$ be a pseudo-multi-share of secrets $(s_1,\cdots,s_n)$. Then we have $$ \begin{alignat*}{2} (w_1,\cdots,w_n) &= (P(\alpha_1),\cdots,P(\alpha_n))\\ &= \sum_{\ell=1}^{k} H_\ell \ . B_\ell \ . M_\ell \end{alignat*} $$ where $B_\ell$ is the vandermonde matrix of size $n$ whose $(i,j)$ entry is $(\alpha_j-e_\ell)^{i-1}$, and $M_\ell$ is a square matrix of size $n$ whose $(i,j)$ entry is $L_\ell(\alpha_i)$ for $i=j$, and $0$ everywhere else.

On the other hand, let $(v_1,\cdots,v_n)$ be a multi-share of secrets $(s_1,\cdots,s_n)$ and let $R(x)$ be the corresponding degree-$t$ polynomial. Then we have $$ \begin{alignat*}{2} (v_1,\cdots,v_n) &= (R(\alpha_1),\cdots,R(\alpha_n))\\ &= \sum_{\ell=1}^{k} H_\ell \ . Chop_{t-k+1} \ . B_\ell \ . M_\ell \end{alignat*} $$

The above is valid because the polynomial $R(x)$ defined below is indeed a degree-$t$ polynomial such that $R(e_\ell) = s_\ell$ for all $1 \leq \ell \leq k$. $$ \begin{alignat*}{2} R(x) &= \sum_{\ell=1}^{k} Q''_\ell(x-e_\ell) L_\ell(x)\\ \end{alignat*} $$ with $Q''_\ell(x-e_\ell)$ a $(t-k+1)$-degree polynomial such that $Q''_\ell(0)=s_\ell$ for all $1 \leq \ell \leq k$.

Since $Q''_\ell(0)=Q'_\ell(0)=h_{0,\ell}=s_\ell$ for all $1 \leq \ell \leq k$, the following tuple is a valid set of coefficients for $Q''_\ell(x)$:

$$ \begin{alignat*}{2} H_\ell \ . Chop_{t-k+1} &= (h_{0,\ell},\cdots,h_{2t-k,\ell},0,\cdots,0) \ . Chop_{t-k+1}\\ &= (h_{0,\ell},\cdots,h_{t-k,\ell},0,\cdots,0) \end{alignat*} $$

Now from the two expressions of $(w_1,\cdots,w_n)$ and $(v_1,\cdots,v_n)$ above, we need to get to the formula $$(w_1,\cdots,w_n). A = (v_1,\cdots,v_n)$$ with
$$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chop_{t-k+1} B_\ell M_\ell$$

Any thoughts or suggestions?