0
$\begingroup$

I am looking for a secret sharing scheme that is robust against noise, the shares are going to be noisy. We do not want to reconstruct the secret perfectly and a noisy reconstruction with a bound on noise is good enough.

Assume we are using $(n,k)$ Shamir's scheme to distribute a secret among $n$ parties so that we need at least $k$ of them to recover. If we add noise to the shares, using $k$ points, the reconstructed polynomial would be very noisy. However, having access to an infinite amount of points would result in a perfect reconstruction. Are there any works that quantify this reconstruction noise?

If you know of any other idea or another sharing scheme, that would also be great!

Improve this question
$\endgroup$
5
1
$\begingroup$

Do you have a noise model in mind?

If the noise affects only a small portion of shares, regular shamir secret sharing is robust. You only need k complete shares.

For other scenarios, like having a few bit flips across all shares. You add any error correction code after creating the shares before distributing them. E.g Reed Solomon. so That each party still gets a single share but with extra error correction information.

Improve this answer
$\endgroup$
2
  • $\begingroup$ We can assume that noise is normal. We add noise to all of the shares. $\endgroup$ – Erfan Hosseini Oct 15 '20 at 23:08
  • $\begingroup$ normal noise makes sense with analog systems. Not so much with digital systems. Where we discuss bit flips zeroing bits or setting bits noise can be independent or can affect runs of continious data. etc. anyway applying a suitable error correcting code to each share independently and sharing those will work. The error correcting code ensures each share reaches it's recepient. and we don't tell anyone anything about other shares. $\endgroup$ – Meir Maor Oct 16 '20 at 4:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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