# RS Erasure Coding and Shamir's Secret Sharing

So I was trying to understand the basic difference between erasure coding and secret sharing, and I found this paper (that you can find here or here).
For what I understand, it states that Shamir's Secret Sharing is basically a particular instance of a Reed-Solomon Code;
However I cannot really understand the difference between any RS code and a SS coding from a security standpoint.

Imagine that I have an RS code (m,n) and a data chunk to encode. After encoding the data I will have n chunks, and if I want to reconstruct the data, I will need at least m shares of the data, right?

How this is different to an instance of Shamir's Secret Sharing (m,n), where I need m shares out of n to reconstruct the secret? Are they perfectly equivalent, or SS is some way more secure?

I admit to be really ignorant about the detailed technical/math aspects of how the two work, and I am more interested in the practical point of view.

-

Shamir's (m,n) secret sharing scheme has a secret $s_0$ which is represented as an element of a finite field $\mathbb F_q$ of $q$ elements. There are also $m-1$ other "randomly chosen" elements $s_1, s_2, \ldots, s_{m-1}$ that the designer uses. The scheme creates a polynomial
$$S(x) = s_0 + s_1x + \cdots + s_{m-1}x^{m-1}$$ and evaluates $S(x)$ at $n$ distinct nonzero elements $\alpha_1, \alpha_2, \ldots, \alpha_n$. Note that $n$ must be at least as large as $m$ and cannot be larger than $q-1$. The $n$ pieces of the secret that are handed out to those sharing in the secret are just these polynomial values $S(\alpha_1), S(\alpha_2), \ldots, S(\alpha_n)$.

Given $m$ of the $n$ shares, the Lagrange interpolation formula gives the unique polynomial $T(x)$ of degree $m-1$ or less that interpolates through these $m$ points, that is, for each share $[\alpha_j, S(\alpha_j)]$ that is available to the reconstructor, $T(\alpha_j)$ equals the share value $S(\alpha_j)$. Therefore, $T(x)-S(x)$ is a polynomial of degree $m-1$ or less that has $m$ roots in the field, and by the Fundamental Theorem of Algebra, must be zero. Thus, $T(0) = s_0$ is the secret.

If $m$ shares are available, the secret can be recovered.

If more than $m$ shares are available, any $m$ of them can be used to reconstruct the secret. Shamir also showed that if fewer than $m$ shares are available, then the secret cannot be recovered; in fact, all possible $q$ values of the secret are equally likely to be obtained if one interpolates through fewer than $m$ shares.

The McEliece-Sarwate generalization of this scheme via Reed-Solomon codes has two aspects.

• First, by using the error-correcting properties of Reed-Solomon codes, it is possible to recover the secret even if some of the shares are in error. Here, error means that the shareholder submits a share value that is different from the value given to him/her. Such errors could be due to malice, or could occur because of accident (e.g. a flash drive holding the share is forgotten in a pocket and gets washed in a clothes-washer). In the standard Shamir reconstruction, damaged shares are no different from valid shares and Lagrange interpolation will almost always reconstruct a "secret" that is different from the original. Unless there is error control built into the secret (e.g. a CRC checksum), there is no way of knowing that the recovered "secret" is different from the original. On the other hand, the properties of Reed-Solomon codes say that if $m+t$ shares are available of which at most $\lfloor t/2\rfloor$ are in error, then by using a Reed-Solomon decoding algorithm, the secret can be successfully recovered. The reconstructor does not need to know which shares are in error (if this were known, the damaged shares could just be ignored!). The decoding algorithm also indicates which shares, if any, of the $m+t$ submitted shares are in error, that is, cheaters (or launderers!) can be identified, and of course the correct share values can be computed and given to the innocent share holders on new flash drives. It is also true that if more than $\lfloor t/2\rfloor$ shares are in error, the Reed-Solomon decoding algorithm will quite likely refuse to reconstruct a secret, and will reconstruct a "secret" different from the original only in rare circumstances. Note that a failure to reconstruct a secret is not fatal (unless $m+t = n$) since one can always await the submission of more valid shares so that the effect of the invalid ones can be overcome. In this form, there is no difference between the security of the Shamir scheme and the Reed-Solomon coding scheme.

• The second aspect of Reed-Solomon coding schemes considered in the McEliece-Sarwate paper is that it is not necessary to fill up $S(x)$ with $m-1$ randomly chosen symbols. In fact, the secret can be all $m$ symbols $s_0,\ldots,s_{m-1}$ instead of just $s_0$ being the secret. One advantage is that we can use a smaller finite field. If the secret is $1000$ bits, say, and $m=10$, Shamir's scheme would operate over $\mathbb F_{2^{1000}}$ and each share of the secret would also be $1000$ bits long. $10$ kilobits ($10$ one-kilobit shares) would be needed to recover the secret. On the other hand, a Reed-Solomon coding scheme could divide the secret into $10$ $100$-bit symbols and operate over $\mathbb F_{2^{100}}$. Also each share would be $100$ bits long, and, as before, only ten such short shares would be needed to recover the secret. This reduction in the field size does come at some cost in security. If only $9$ shares are available to a cabal and they guess at possible values of the tenth needed share, they can come up with a "short list" of only $2^{100}$ values that the $1000$-bit secret might have. Shamir's scheme in a similar predicament would have a list of $2^{1000}$ possible values of the secret, thus providing perfect security. The trade-off between reduction in security and ease of implementation as well as storage of each share of the secret is something that needs to be evaluated for each application. The most secure scheme has shares that are as long as the secret while the Reed-Solomon scheme can be used to reduce the share size at the cost of reduced security.

Edit Another version of secret-sharing gives the $i$-th share holder the value of $\alpha_i$ as well as the share $S(\alpha_i)$ (this requires twice as much storage). Thus, $m$ share holders can reconstruct the secret if they know Lagrange interpolation and have access to a computer that does the needed finite-field arithmetic without anyone else knowing about it. In the standard scenario, the $i$-th share holder only has $S(\alpha_i)$ without any knowledge of $\alpha_i$, and only an official reconstructor knows that Joe Blow is the $i$-th share holder and looks up $\alpha_i$ when Joe submits his share for reconstruction purposes. In this case, secret re-construction can only be done by the official re-constructor; a cabal of $m$ rebellious share holders cannot reconstruct the secret in private and use it to overthrow the Evil Empire. When share holders actually have $[\alpha_i,S(\alpha_i)]$, a cheater could alter either quantity or both, and an innocent error might do likewise. The solution to this problem is more difficult. For what can be done in such cases, see, for example, here.

-
Do you know of a good reference implementation I can take a look at for using reed-solomon to decode shamir shares? –  mikeazo Sep 23 '13 at 15:04
@mikeazo Sorry, I don't know of any Reed-Solomon implementations suited for secret-sharing applications. Most Reed-Solomon decoder implementations that I am aware of are for error-control purposes in digital communications schemes or digital video recording schemes, and VLSI implementation as an ASIC rather than software routines is the norm. Adapting these for secret-sharing would be difficult to say the least. –  Dilip Sarwate Sep 23 '13 at 16:55
@mikeazo I found the programs here to be useful. If I remember correctly, the Reed-Solomon stuff is in C or C++. –  Dilip Sarwate Sep 23 '13 at 19:09
I appreciate the help. One more follow-up question. Say I have 4 parties and I want to share a secret $s$ such that I can tolerate 1 corrupt party. What parameters do I use for Shamir to be able to use RS decoding? Do I use 2 out of 4 secret sharing or 3 out of 4? –  mikeazo Oct 1 '13 at 17:29
@mikeazo How many uncorrupted shares do you need for reconstruction? If $2$ good shares are required to reconstruct, then you use a $[4,2]$ Reed-Solomon code. It can reconstruct the secret if any two good shares are available. It can reconstruct if two good shares are available and a third "My flash drive got laundered" share is present (just ignore the clean guy's share!). And it can reconstruct the secret if all $4$ parties are present and (possibly) one of the shares is bad, but it is not known which one is bad. (If you know which share is bad, just ignore it and use 2 good shares). –  Dilip Sarwate Oct 1 '13 at 17:43

In general, an $(n,k,k')$ erasure code must have the property that any $k'$ out of $n$ symbols must be sufficient to recover the original $k$-symbol message.

An $(n,k')$ threshold secret sharing scheme, however, requires an additional property: knowing less than $k'$ shares out of $n$ must not be sufficient to recover any information about the message.

That is to say, the possibility that one might sometimes be able to recover the message, or at least part of it, from less than $k'$ out of $n$ symbols might be seen as harmless or even positive for an erasure code, but would be totally disastrous for a threshold secret sharing scheme.

-
I am not sure if any erasure code can be used to construct a secret sharing scheme. I would definitely like to see a reduction in that scenario. Reed Solomon has a direct relation with Secret Sharing if we see the space of all messages as the secret space and therefore, we have the bound. It is possibly for BCH also to show secret sharing property for the multivariate generalizations of Shamir-Secret sharing, but how to argue for codes, say like Reed Muller code or even Hamming code! –  Jalaj Jan 27 '12 at 22:06
This answer goes more in the direction I was looking for. My original question was due to the technique they use in this article [dl.acm.org/citation.cfm?id=1993051]: basically they use RS for integrity and SS for security: I was guessing whether it was a redundant solution or not. –  andrea.reale Jan 28 '12 at 16:02
It is fine in that case because you can see that they are using two RS codes with two different parameters. The one with the erasure property has a weaker parameter than the one in the secret sharing scheme. We often use this form of composition while developing a protocol. You may find Kurosawa's work on "Error decodable secret sharing" (eprint.iacr.org/2009/263) and Martin et. al follow up work on "Error decodable secret sharing and one-round perfectly secure message transmission for general adversary structures" more interesting for a much stronger result. –  Jalaj Jan 28 '12 at 18:02
Thanks, this comment really makes things clear for me –  andrea.reale Jan 30 '12 at 8:40

First of all, the choice of word "Erasure code" is not appropriate. RS code can be used as an erasure code, but when you are talking about erasure code, you implicitly work in the area where some bits of the data has been deleted (note the difference from ECC where you know that the data has been corrupted). An erasure code is more efficient in terms of block length and the distance of the code than if you want to achieve the same parameters for correcting errors. The moral is that just detecting is far more easier than correcting. So what you mean in the question is when RS is used as an ECC and not as an erasure code.

The similarity between Reed-Solomon code and Shamir Secret Sharing scheme was first observed by McEliece et al. in On sharing secrets and Reed-Solomon codes. In such a RS-code, you will need $n-k \geq 2t$ to get a $(t,n)$-Shamir Secret Sharing scheme. So you need a particular form of RS-code to get a particular kind of secret sharing scheme. Other than that, you are fine.

Techniques for performing such error correction for secret-sharing schemes have received a certain amount of attention in the literature as well (see for example, An application of covering designs: determining the maximum consistent set of shares in a threshold scheme and A new algorithm for searching a consistent set of shares in a threshold scheme with cheaters).

-
The paper you reference is the same as the one I cited in the original question. My question was focused on security: If I want a secret not to be uncovered unless m out of n participants are compromised can I use an RS code? Is it less secure than Shamir's algorithm? If yes, why? –  andrea.reale Jan 28 '12 at 15:52
I am sorry, I didn't check the link. You can use the RS code with the required parameter. They are equivalent in that case, especially because the unconditional security of Shamir Secret Sharing comes from the impossibility of solving a system of linear equations in $k$ variables with less than $k$ equations, or in other words, the Shannon theory of Perfect secrecy. The same holds for RS-code as well. You cannot decode a code if the hamming distance of the codewords received from any rightful code is more than the distance of the code. I hope this helps. –  Jalaj Jan 28 '12 at 17:53