Reed Solomon secret sharing and as a one-time symmetric key?

Question

Shamir's Secret Sharing is just a special case of Reed-Solomon where only one coefficient is used to store the secret instead of the entire polynomial.

Sarwate however, suggests that the latter can be done by sacrificing information theoretic security:

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

Has anyone else agreed with Sarwate on this? Is it proven to be true?

Suppose you have a $10,000$-bit secret which you split into $100$ $100$-bit shares. Being in possession of $99$ shares can you really not learn anything about the $10,000$-bit secret even if parts of it are known or can be guessed? With complexity less than $2^{100}$.

And wouldn't it imply that this can be used to encrypt? The last share can be withheld from source of data and be effectively its encryption key.

Answer 1

Suppose the 10 000-bit message is uniformly distributed and we split it with a $t$-of-$n$ scheme.

• With Shamir's secret-sharing where each share is 10 000 bits apiece, if you have only $t - 1$ shares, the $t^{\mathit{th}}$ share has $2^{10~000}$ possible values with uniform distribution, and so the conditional distribution on the secret given $t - 1$ shares can (and does) have 10 000 bits of entropy.

• With a conventional erasure coding scheme like Reed–Solomon where each share is 100 bits apiece, if you have only $t - 1$ shares, the $t^{\mathit{th}}$ share has only $2^{100}$ possibilities to determine what the secret could be, so the conditional distribution on the secret given $t - 1$ shares can't have more than 100 bits of entropy—in other words, you can narrow the secret down to a minuscule fraction of the possible subspace. (If it had fewer than 100 bits of entropy, then it wouldn't be a very efficient erasure code.)

The question you might ask is: Which subspace of the message space does the erasure code use? Here's a simple 2-of-3 scheme, sometimes called RAID-5: divide the secret into 5000-bit halves $s_1$ and $s_2$, and use $s_1$, $s_2$, and $s_1 \oplus s_2$ as the shares. A single share reveals a lot about the original message! So, not very useful for encryption.

What about Reed–Solomon? We interpret a $t\ell$-bit message $m = (m_0, m_1, \dots, m_{t-1})$ as a degree-$(t - 1)$ polynomial $m(x) = m_0 + m_1 x + m_2 x^2 + \cdots + m_{t-1} x^{t-1}$ over $\operatorname{GF}(2^\ell)$, and evaluate it at $n$ distinct points, say $\{0, 1, \alpha, \alpha^2, \dots, \alpha^{n-2}\}$ where $\alpha$ is a generator of $\operatorname{GF}(2^\ell)$. Note that the first two shares in this perfectly reasonable choice of Reed–Solomon code are $m_0$ and $m_0 + m_1 + m_2 + \cdots + m_{t-1}$. Still not very useful for encryption.

‘But you just chose the evaluation points pathologically!’ Well, OK, but let's say you used $\{\alpha, \alpha^2, \dots, \alpha^n\}$ for fixed $\alpha$. There's a trivial known-plaintext distinguisher for a ciphertext $(c_1, c_2, \dots, c_{t-1})$ and key $c_t$ where $c_i = m(\alpha^i)$: simply evaluate the polynomial at the evaluation points and compare to the putative ciphertext.

What if $\alpha$ were part of the key too? Well, then $\alpha$ is one of the at most $t - 1$ roots of the degree-$(t - 1)$ polynomial $m(\alpha^i) - c_i$ for each $i$, which we can compute in a known-plaintext attack by standard root-finding.

What if we randomize the first message block too? Well, there distinguisher still basically works except we have to see whether $m(\alpha^i) - c_i$ (here $m$ is taken to have zero constant term) is the same randomized first block for all $i$. We could randomize all but one of the message blocks, but then we're just back to Shamir's secret-sharing.

There's another way: We could apply an all-or-nothing transform (AONT), and then use one of the shares as a secret key. With an efficient erasure code, this is obviously as secure as the AONT itself. (AONTs were not developed until well after the McEliece–Sarwate note.)

There's still a practical problem with using this as a cipher: How does the recipient get the key if it is determined by the plaintext? Maybe you actually want a public-key cryptosystem, but it's not clear to me how to get one out of this—although you can get one out of other error-correcting codes, also due to McEliece, where you encapsulate a secret key in the syndrome of a random error under a hidden Goppa code, and derive a key by hashing the error.

So, this idea is mainly useful for storing a message that is already randomized like a large secret key, where knowledge of part of it doesn't help. Of course, if we want to make sure that the subspace of messages covered by an incomplete set of shares is at least (say) 256 bits for modern security, we might as well just make the secret be 256 bits itself and use a key derivation function to derive a larger key from it. For storing longer structured secrets, the McEliece–Sarwate is slightly more efficient than just encrypting them, splitting the ciphertext with Reed–Solomon, and splitting the key with Shamir.

Maybe there's a broader use for the McEliece–Sarwate observation but it's not obvious to me!

The standard caveat about secret-sharing applies too: Whenever you reconstruct the secret, someone has to have the whole secret in one place to use it, and could sequester it away. So if you ever use it, there's a single party with unilateral access to whatever power the secret grants. Many applications for which secret-sharing might be tempting are better served by higher-level multiparty computation like threshold signatures where no party ever has unilateral power of some central secret.

Answer 2

Sarwate's comment seems very uncontroversial to me. It is related to the idea of "packed secret sharing" (see Why only one secret value with Shamir's secret sharing?), also called "ramp secret sharing".

Recall polynomial interpolation through points $(x_1, y_1), \ldots, (x_n,y_n)$. The polynomial has coefficients $p_0, \ldots, p_{n-1}$ given by the following linear system of equations:

$$ \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix} = \begin{bmatrix} x_1^0 & x_1^1 & x_1^2 & \cdots & x_1^{n-1} \\ x_2^0 & x_2^1 & x_2^2 & \cdots & x_2^{n-1} \\ \vdots & & & \ddots & \vdots \\ x_n^0 & x_n^1 & x_2^2 & \cdots & x_n^{n-1} \end{bmatrix} \begin{bmatrix} p_0 \\ p_1 \\ p_2 \\ \vdots \\ p_{n-1} \end{bmatrix} $$

The important observation is that the matrix is a Vandermonde matrix, so it has full rank. In fact, any subset of its rows also has full rank.

Knowing $t$ shares/points on the polynomial tells you $t$ (independent) linear constraints about the coefficients of $p$. This is like constraining the vector $(p_0, \ldots, p_{n-1})$ to a subspace of dimension $n-t$.

In normal Shamir sharing, $p_0$ is the secret payload and $p_1, \ldots, p_{n-1}$ are random. Until you have $t=n$ points on the polynomial, you get no information about $p_0$.

In packed secret sharing, you can let $p_0, \ldots, p_{s-1}$ be the secret payloads and $p_s, \ldots, p_{n-1}$ random. If you know $n-s$ points on the polynomial, you have no information about the payloads. If you know $n-s+1$ points on the polynomial, you now know a subspace of dimension $s-1$ that contains the payloads. If you know $n-s+2$ points on the polynomial, you know a subspace of dimension $s-2$ that contains the payloads, etc.

Suppose we have a secret value, which we write as $p_0 \| \cdots \| p_{s-1}$. If this value is known to be highly structured, then it is quite possible that you completely learn the secret by knowing that it lives in some $(s-2)$-dimensional subspace. So this kind of secret sharing is only good if you have sufficient lack of structure on the payload, or don't care at all about what happens after $n-s$ shares are revealed.