3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually, if $p=251$, then you can't fit an 8 bit value there; there are only 251 possible secret values, and hence there are 5 possible values of $S_i$ that cannot be shared. $\endgroup$ – poncho Apr 14 '15 at 16:10
  • $\begingroup$ @poncho That's a good point. I suppose $S$ could be broken (in an overly complicated way) into pieces such that each piece is represented by only 251 values. What I meant was that if such a thing were done then each $S_i$ could fit into an 8 bit value. $\endgroup$ – chew socks Apr 15 '15 at 1:19
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks! I didn't know that any value of $p^k$ would work. Considering the libraries available using $GF(2^n)$ seems very convenient. $\endgroup$ – chew socks Apr 15 '15 at 1:22
  • $\begingroup$ In case of sharing over integers, system of diophantine equations could be solved for valid shares. This makes a distinguisher algorithm, so computational only (not information-theoretic) security. One could pick random coefficients large enough to produce "almost uniform" distribution of shares, just like at interactive proofs with groups of a hidden order. Would this make sharing over integers acceptable? Any reason still left to avoid it? Thanx. $\endgroup$ – Vadym Fedyukovych Apr 16 '15 at 10:18
  • $\begingroup$ @VadymFedyukovych: it's not at all clear how good you could make it. Apart from the issues for leaking lsbits (e.g. if you have shares for 3 and 26, I believe that might leak the secret modulo 26-3=23, as 23 is uninvertible in the integers, you also have the problem of probability distributions. You must pick coefficents according to some nonuniform distribution; with $t-1$ shares, the attacker can compute, for any possible secret value, the coefficients that would have been. If any of the coefficents have probabilities that are too small, the attacker can eliminate that possibility. $\endgroup$ – poncho Apr 16 '15 at 12:57
  • $\begingroup$ crypto.stackexchange.com/questions/9295/… $\endgroup$ – Vadym Fedyukovych Apr 16 '15 at 13:03
  • $\begingroup$ The wikipedia article has since been corrected. $\endgroup$ – PyRulez Feb 13 '16 at 4:05

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.