The Wikipedia article on Shamir\'s Secret Sharing says to that to have informati

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 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?Z/pZ. It also suggests that p should not be too large because an attacker knows that as p? p{f(x)modp=f(x)}?. 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 ?i,Si?GF(257). I do not understand a specific reason to use p=257 over any other prime number. For instance the elements Si could be stored in in an 8 bit value if p=251 was chosen.

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.