What's the functional difference between fountain codes and polynomial secret sharing?

Question

Fountain codes, as I understand it, allow for the reconstruction of a set of data (e.g. a 64-bit word), by sending (without corruption or failure) chunks of data generated using a probabilistic function, with the benefit that due to an unlimited supply of chunks being sent over an unreliable channel, as long as the threshold of successfully send chunks are received (e.g. more than 64-bits of encoded data), the client can reconstruct the data without having knowledge of packet loss.

Polynomial secret sharing splits a piece of data into multiple shares, such that if the minimum threshold of shares is provided, the data can be reconstructed. An unlimited amount of shares can be generated. This could be used, for example, to split a secret to multiple locations to provide redundancy and/or security.

The actual implementations of these algorithms are different, but how are they functionally different? Why can't one be interchanged for another?

Answer 1

Consider what happens when we construct Shamir's secret sharing scheme for a secret $s$ and a reconstruction threshold $t=4$. Our polynomial will be of degree $t - 1$ with $a_i$ being random coefficients:

$$ f(x) = s + a_1x + a_2x^2 + a_3x^3 $$

The shares for the $n$ players are given by $f(1), f(2), \dots f(n)$. Any $t \ge 4$ of the players can reconstruct the polynomial $f(x)$ and can recover the secret as $s = f(0)$, but any $t < 4$ of the players do not have enough information and thus learn nothing about the secret $s$.

We can use this exact same technique as a fountain code through nothing more than a change in perspective. Instead of a secret $s$, we have a message $m$:

$$ g(x) = m + a_1x + a_2x^2 + a_3x^3 $$

And instead of giving each player $n$ the share $f(n)$, we broadcast a series of blocks $g(1), g(2), \dots$ to the players. Once a player has received $t \ge 4$ message blocks, they have enough information to reconstruct the polynomial $g(x)$ and can recover the original message as $m = g(0)$. By choosing a large enough finite field, it is possible to generate a very large number of unique message blocks.

Practical fountain codes are usually based on low-density parity codes for reasons of efficiency, but I hope this example helps to show that in many ways error-correcting codes and secret-sharing schemes are merely two interpretations of the same underlying concept.

Answer 2

Shamir secret sharing directly uses Reed-Solomon codes.

Note that the collection of all polynomials over $\mathbb{F}_q$ of degree up to $k-1$ (whose evaluations along some ordering of $\mathbb{F}_q$ form the codewords of the Reed-Solomon code with minimum distance $q-k$) play the central part in Shamir secret sharing.

These codewords are constructible from any $k$ uncorrupted shares and leak no information when only $k-1$ or less shares (equivalently codeword coordinates) are available.