Coefficients in Shamir's Secret Sharing

[N. Durner]

Hi,

I want to implement Shamir's Secret Sharing scheme as described in
Applied Cryptography, 23.2.

What's the recommended size of the coefficients (in bits) for a message
M that has a length of 128 or 256 bits?

Thanks a lot,

Nils Durner

[Michael Amling]

N. Durner wrote:
>
> I want to implement Shamir's Secret Sharing scheme as described in
> Applied Cryptography, 23.2.
>
> What's the recommended size of the coefficients (in bits) for a message
> M that has a length of 128 or 256 bits?

The modulus P has to be large enough to distinguish all possible
secrets. To cover a 256-bit secret, you'd use a 257-bit prime. The
coefficients may be slightly shorter than that if they have leading zeros.

--Mike Amling

[Gregory G Rose]

In article <d0v4n9$ad6$01$1...@news.t-online.com>,

N. Durner <ndu...@web.de> wrote:
>I want to implement Shamir's Secret Sharing scheme as described in
>Applied Cryptography, 23.2.
>
>What's the recommended size of the coefficients (in bits) for a message
>M that has a length of 128 or 256 bits?

Since you're using information theory in finite
fields, it's quite safe to use coefficients of
the same length as the items to be encoded.
Alternatively, you could treat a longer secret as
if it was broken into smaller chunks, and
independently split each chunk. There was a
public domain program called "secsplit" (IIRC)
that did this with 16 bit chunks. You don't need
to go for longer moduli or anything.

Note that secret splitting is
information-theoretically secure; it all comes
down to your random number generator.

Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au

[Bryan Olson]

Gregory G Rose wrote:
> N. Durner <ndu...@web.de> wrote:
>
>>I want to implement Shamir's Secret Sharing scheme as described in
>>Applied Cryptography, 23.2.
>>
>>What's the recommended size of the coefficients (in bits) for a message
>>M that has a length of 128 or 256 bits?
>
>
> Since you're using information theory in finite
> fields, it's quite safe to use coefficients of
> the same length as the items to be encoded.
> Alternatively, you could treat a longer secret as
> if it was broken into smaller chunks, and

> independently split each chunk. [...]

That "alternately" idea has a lot going for it. The algorithms
are super-linear time, so handling a big secret as a list of
shorter secrets is more efficient. The coefficient size does
limit the number of shares, but there's no demand for large
numbers of shares, nor even modest numbers like 173-of-204. (The
one exception I can imagine is if one wants to be able to create
new shares at random, with negligible chance of colliding with
an existing share.)

Secret vectors, like most data today, tend to split neatly on
bit boundaries, so working modulo a primitive polynomial in
GF(2**n) is usually more convenient than using mod-p
polynomials. With GF(2**8), one can efficiently split on byte
boundaries and support up to 255 shares.

--
--Bryan