# Shamir's Simple Sharing Scheme - preventing partial recovery of data

In SSSS, if you recreate the original secret with one of the decoder inputs being slightly damaged (e.g. one or two chars incorrect), you receive a slightly damaged version of the original secret. So if the original secret was "Abraham Lincoln", decoding using a slightly damaged input might still get you "Ab%aham Lincoln", for example.

What's the best way to encode and decode the secret, on top of SSSS, such that any variance at all in the inputs causes the decoded secret to be completely useless?

One obvious way would be to encrypt the secret before using SSSS. Are there any alternatives? In particular, any alternative that would not require each user to have a final decryption key (for decoding the secret that comes out of SSSS) as well as their SSSS decoding keys?

-
1) How would that partial damage happen? Why do you care about this scenario 2) It's often a good idea to apply secret sharing to a symmetric key, not to the data itself. –  CodesInChaos Nov 25 '13 at 10:25
@user8911 Without an answer to my first question, this can't be answered well. Blindly applying my second point is not the way to go and can be broken by guessing the remaining bits. –  CodesInChaos Nov 25 '13 at 10:55
@CodesInChaos I don't really have a scenario in mind. It just makes me nervous that information is retrievable even when the inputs are less than 100% accurate. –  occulus Nov 25 '13 at 11:30
I do not see how a modified/damaged share in polynomial secret sharing (viewing some encoding of "Abraham Lincoln" as the constant term of a polynomial over a finite field) could lead to a result as given by your example (with non negligible probability). If you still have enough valid shares (equal to or greater than the threshold) you can apply for instance list decoding. Or are you assuming you run secret sharing on every character independently? –  DrLecter Nov 25 '13 at 12:50
Obviously, they share the secret character by character: On their page they write: "PassGuardian is built on secrets.js, an open-source implementation of Shamir's sharing scheme. While secrets.js permits Galois Fields up to 20 bits in size, PassGuardian uses an 8-bit binary finite field for computations. The share format is described at the secrets.js page." –  DrLecter Nov 25 '13 at 15:23

With SSS you are sharing field elements, so if the secret to be shared is larger than one field element, you are going to have to break up the secret somehow and share the parts. I am not aware of any standard method that allows you to make the sharings dependent on one another. Probably the best way is to encrypt the secret with a key and then share the key (using Shamir) and the encrypted secret (e.g using an appropriate erasure code) and store the share/fragment parts at different locations.

Note that this is not a problem of SSS. In SSS if a share is slightly corrupted it cannot be used in reconstruction.

You could also pick a field large enough for your secret.

-
It might be better to say: encrypt the secret with a key and then share the key (using Shamir) and the encrypted secret (e.g. using an appropriate erasure code) and store the (share,fragment) parts at different locations. That's basically secret sharing made short, which, then does only provide computational secrecy instead of information theoretic. –  DrLecter Nov 25 '13 at 16:54
thanks for update :) –  DrLecter Nov 25 '13 at 21:47
For example, let's say that the secret is a password shared using a threshold secret sharing scheme (like Shamir's) using threshold $t$, and that we know $t-1$ full shares plus all but the third byte of the $t$-th share. Now, there are 256 possible values the missing byte could have, so we can just reconstruct the secret using each of those values, giving us 255 different passwords.
The same attack can be applied to other kinds of missing or corrupted information, as long as we have some idea of what the missing information might be. For example, if each share was $n$ bytes long, and we only knew (or suspected) that some byte of some share was wrong, we could just try changing each byte of each share to each of its 255 possible alternative values, giving us $t$ × $n$ × 255 reconstructions to choose from. For typical values of $t$ and $n$, this should still be easily manageable.