2
$\begingroup$

Suppose we have a (t,n) Shamir-secret sharing scheme. A value of some computation is shared with n parties where at most $t-1$ parties are malicious. What is the best strategy to reconstruct the shares? I believe we can use Reed-Solomon error corrections to retrieve value for upto t<n/3. For t<n/2, we can randomly reconstruct $k$ times using $t$ shares and check for the value that appears the most number of times. Is there anything better than this?

$\endgroup$

1 Answer 1

1
$\begingroup$

A stronger approach is to use the Guruswami-Sudan list-decoding algorithm. If you have $m$ shares then their polynomial reconstruction algorithm will return all polynomials of degree at most $t$ such that at least $k$ of the shares satisfy the polynomial, provided that $k>\sqrt{km}$. As $m-t+1$ grows relative to $t$, the number of sporadic false positives will reduce (notice that if the number of honest parties is close to the number of dishonest parties, there is a significant chance that we cannot uniquely recover the polynomial but can contain it to a relatively short list of possibilities).

$\endgroup$

Your Answer

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

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