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?


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.