# Reconstruction of shamir secret shares in the presence of malicious parties

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?

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).