Question about Shamir secret sharing scheme

[Matt Ball]

On Sat, Oct 3, 2009 at 12:42 AM, Kevin W. Wall <kevin.w.wall at gmail.com> wrote:
>
> The question that a colleague and I have is there any cryptographic
> purpose of computing the independent coefficients over the finite
> field, Zp ?

Here is a concrete example of information leakage when not using Zp.

Assume that the secret and each additional coefficient is a positive
integer less than 3 (intentionally picking a very small range to keep
the math simple).  Assume there are two shares and that both shares
are needed to recover the secret.  a0 = the secret and a1 is randomly
chosen in the same range.

q(x) = a0 + a1*x

We can make a table of all possible coefficients (a0, a1) and share
values (q(1), q(2)):

(a0, a1, q(1), q(2)) = {
  (0, 0, 0, 0)
  (0, 1, 1, 2)
  (0, 2, 2, 4)
  (1, 0, 1, 1)
  (1, 1, 2, 3)
  (1, 2, 3, 5)
  (2, 0, 2, 2)
  (2, 1, 3, 4)
  (2, 2, 4, 6)
 }

>From this table, it is possible to deduce a0 (the secret) knowing only
q(2), assuming that q(2) is not 4 or 2.  Even then, you know that the
secret is not odd.  Knowing only q(1) leaks a little less information,
but you can still fully determine the secret if q(1) = 0 or 4, and
partially determine the secret if q(1) is 1 or 3.

Intuitively, the information leakage occurs because the range of q(x)
is larger than the range of the secret a0.

Conversely, when using the set of integers mod 3, the table looks like this:

(a0, a1, q(1) mod 3, q(2) mod 3) = {
  (0, 0, 0, 0)
  (0, 1, 1, 2)
  (0, 2, 2, 1)
  (1, 0, 1, 1)
  (1, 1, 2, 0)
  (1, 2, 0, 2)
  (2, 0, 2, 2)
  (2, 1, 0, 1)
  (2, 2, 1, 0)
 }

It's easy to confirm by visual inspection that knowledge of q(1) or
q(2) alone does not reveal any information about the secret a0.

>
>  The only reason that we can see to doing this is to
> keep the sizes of the shares Si bounded within some reasonable range
> and it seems as though one could just do something like allowing T
> choose random coefficients from a sufficient # of bytes and just
> do all the calculations without the 'mod p' stuff.

In any real implementation, you'd want to use a binary finite field,
such as GF(2^8) or GF(2^16).  This is way faster than using a
non-binary finite field.  The 'mod p' stuff would be optimized into a
series of fast table lookups.

For example, if you want to generate shares for a 512-bit ECC Key, you
would first divide it into 64 bytes (each of which fits inside
GF(2^8)), and then compute 64 independent shares.  Each multiply would
be a couple table look-ups and your done.

Conversely, If you were using a non-binary finite field, your best bet
is probably using 2^521-1 (a.k.a., P-521 or the 13th Mersenne prime).
However, this is way slower than 64 GF(2^8) operations because the
time required to multiply two large integers grows with the square of
the size n.  (Technically you can do it in n log n operations by using
Fourier Transforms, but this is only useful with really big integers
and you have to watch for rounding errors).  The modulo computation
with P-521 would just be a couple BIGNUM subtractions.

Even worse, if you used the set of integers (Z), the evaluated points
on the polynomial would require about d*64 bytes of storage, where d
is the degree of your polynomial (i.e., the threshold number of shares
needed to recover the secret).  The time required to do all these
multiples would roughly grow quadratically with the threshold (or
rather n log n because at this point, using Fourier transforms starts
to become appealing).

This is all moot, though, because using Z is not secure.

>
> We thought perhaps
> Shamir did the calculations of Zp because things like Java's BigInteger
> or BigDecimal weren't widely available when came up with this
> scheme back in 1979.
>
Even today, I don't see why anyone would use BigInteger or BigDecimal
for Shamir's Secret Sharing.  As I mentioned above, the time required
for a BigInteger operation grows faster than linearly with the size of
the secret (either n log n or n^2), as opposed to linear growth with a
binary field.

You might argue that BigInteger and BigDecimal are 'easy to use', but
when considering the substantially slower execution time and the extra
burden of dealing with very large shares, it's really not a net
savings.  Besides, there are many useful implementations of Shamir
Secret sharing that you could import into Java with much less work
required than reimplementing the algorithm from scratch.

Cheers,
-Matt

Matt Ball, Chair, IEEE P1619 Security in Storage Working Group
Staff Engineer, Sun Microsystems, Inc.
500 Eldorado Blvd, Bldg #5 BRM05-212, Broomfield, CO 80021
Work: 303-272-7580, Cell: 303-717-2717

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com