# 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?