What is the maximum number of shares in Shamir's Secret Sharing?

Question

I am using codahale’s Shamir's Secret Sharing implementation of Shamir's secret sharing from Github.

I am using this to generate a 32 byte random key encryption key (KEK) to encrypt a 32 byte data encryption key (DEK) which is used to encrypt the data on the Kafka producers. The DEK would be part of the payload, but the secret KEK is divided into max shares so that it can be distributed among consumers to recompute it.

What is the maximum number of shares that can be created with a threshold of 2 parts?

If I have to achieve this strategy for 1000 clients/parties, how can I do this?

Answer 1

The maximum number of shares in Shamir's secret sharing is limited by the size of the underlying finite field. In particular, the maximum is one less than the number of elements in the field, since each share must be associated with a distinct element of the field, and one of the elements (usually the zero element) must be reserved for the secret being shared.

A quick Google search indicates that the com.codahale.shamir implementation always uses GF(256). Thus, it can support at most 255 shares.

If you switched to an implementation that used, say, GF(2¹⁶), then the maximum number of shares would increase to 2¹⁶ − 1 = 65,535. That should be enough for your purposes. If not, using GF(2³²) would let you have up to 2³² − 1 = 4,294,967,295 possible shares.

The main disadvantage of using fields larger than GF(256) = GF(2⁸) for Shamir's secret sharing is that you may need to pad your data up to a multiple of the field size. (With GF(256), the field elements are single bytes, so that's rarely an issue.) In your case, however, your secrets are always 32 bytes = 256 bits long, so you can safely use GF(2¹⁶), GF(2³²), GF(2⁶⁴), GF(2¹²⁸) or even GF(2²⁵⁶) without having to worry about that.