5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 'Small' set difference was reconstructed at 'reconciliation' papers of Ari Trachtenberg, after sufficiently large number of data (set characteristic polynomial evaluated at random points) was received. Characteristic polynomials are quite different from Shamir secret sharing. It was the idea behind interactive proofs of graph properties with large challenges, to give an example. $\endgroup$ – Vadym Fedyukovych Sep 16 '18 at 7:18
  • 2
    $\begingroup$ This question seems somewhat related: crypto.stackexchange.com/questions/1760/… $\endgroup$ – Ilmari Karonen Sep 16 '18 at 10:10
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.