Choosing finite field size in Shamir's Secret Sharing Scheme

Question

The Wikipedia article on Shamir's Secret Sharing says to that to have information theoretical security the splitting algorithm should be evaluated using finite field arithmetic on the field $\rm{GF}(p)$ such that $p>n,p>S$ where $n$ is the number of shares and $S$ is the information to be shared. It suggests that on the one hand $p$ should be large because an attacker knows that $S\in\mathbb{Z}/p\mathbb{Z}$. It also suggests that $p$ should not be too large because an attacker knows that as $p\uparrow$ $\rm{p}\{f(x)\bmod p = f(x)\}\uparrow$. How should one choose the best value of $p$ and be confident about choice?

Charles Karney's implementation splits $S$ into $i$ pieces such that $\forall \,i,\,S_i\in\rm{GF}(257)$. I do not understand a specific reason to use $p=257$ over any other prime number. For instance the elements $S_i$ could be stored in in an 8 bit value if $p=251$ was chosen.

Answer 1

Actually, you can do Shamir Secret Sharing over any finite field $GF(p^k)$, for any prime $p$ and any integer $k$. If $k=1$, you have the $GF(p)$ field you mentioned; however it works on extension fields as well. We often pick $p=2$ and $k$ a multiple of 8; this makes everything nice even number of bytes (at the cost of doing our calculations in $GF(2^k)$). Of course, this is a choice of convenience, you can make your own choice.

As for the size of $p^k$, well, $p^k > n$ is a hard requirement; you can't give out more shares than nonzero indicies available. As for $p^k > S$, well, that's not actually a hard requirement; you can split up $S$ into several pieces (each piece no larger than $p^k$), and share each piece separately. For example, if the secret is a 128-bit AES key, and you're using $p = 257$, you'd split up the key into 16 pieces, each from 0-255, and generate 16 independent polynomials, and give each share holder a point on each of those 16 polynomials. Just remember: when generating the polynomials, the polynomial you pick must be selected independently of all the other pieces; otherwise you lose the security of the system).

As for not picking $p$ (or $p^k$) too large, well, Wikipedia is wrong there; Secret Sharing is informationally secure (assuming a randomly chosen polynomial); if someone has fewer than the threshold number of shares, then they learn nothing about the secret, and that holds no matter how large we make $p^k$. I suspect someone took the discussion about Shamir Secret Sharing over the integers (which doesn't work, in part because the integers don't form a field, as there are elements without multiplicative inverses, and in part because it's impossible to select a random polynomial with a uniform distribution over the integers), and extrapolated the problems there to finite fields (which doesn't have those issues).