6
$\begingroup$

When using Shamir's Secret Sharing is it possible to use Secure Multi-Party Computation to reconstruct the original secret without revealing one's secret share?

When searching I have found results talking about using secret sharing as part of a Multi-Party Computation scheme. But that is not my question.

$\endgroup$

1 Answer 1

3
$\begingroup$

Sure you can.

Suppose there are $t$ shares $(x_1,y_1),\ldots,(x_t,y_t)$ hold by $t$ different parties. Recall that in Shamir secret sharing, the secret is the free coefficient in the polynomial. Then to reconstruct the secret, the parties need to compute jointly:

$$L(0) = {\sum_{j=1}^{t}} y_j \cdot l_j(0)$$

where

$$l_j(0) =\prod_{\begin{smallmatrix}1\le m\le t\\ m\neq j\end{smallmatrix}} \frac{x_m}{x_m-x_j}$$

Usually $x_1,\ldots,x_t$ are public, so all parties can compute all $l_j(0)$ locally. Then what they need to do is to share $y_j$ among them and compute $L(0)$ securely using generic secret sharing based MPC.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.