Question about Shamir secret sharing scheme

[Kevin W. Wall]

Hi list...I have a question about Shamir's secret sharing.

According to the _Handbook of Applied Cryptography_
Shamir’s secret sharing (t,n) threshold scheme works as follows:

SUMMARY: a trusted party distributes shares of a secret S to n users.
RESULT: any group of t users which pool their shares can recover S.

The trusted party T begins with a secret integer S ≥ 0 it wishes
to distribute among n users.
(a) T chooses a prime p > max(S, n), and defines a0 = S.
(b) T selects t−1 random, independent coefficients defining the random
polynomial over Zp.
(c) T computes Si = f(i) mod p, 1 ≤ i ≤ n (or for any n distinct
points i, 1 ≤ i ≤ p − 1), and securely transfers the share Si
to user Pi , along with public index i.

The secret S can then be computed by finding f(0) more or less by
using Lagrangian interpolation on the t shares, the points (i, Si).

The question that a colleague and I have is there any cryptographic
purpose of computing the independent coefficients over the finite
field, Zp ?  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. 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.

So other than perhaps compatibility with other implementations (which
we are not really too concerned about) is there any reason to continue
to do the calculations over Zp ???

Thanks,
-kevin
-- 
Kevin W. Wall
"The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents."-- Nathaniel Borenstein, co-creator of MIME


-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com

Re: Question about Shamir secret sharing scheme

[Victor Duchovni]

On Sat, Oct 03, 2009 at 02:42:14AM -0400, Kevin W. Wall wrote:

> The secret S can then be computed by finding f(0) more or less by
> using Lagrangian interpolation on the t shares, the points (i, Si).
> 
> The question that a colleague and I have is there any cryptographic
> purpose of computing the independent coefficients over the finite
> field, Zp ?  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.

Lagrange interpolation works for polynomials over a field. The most
convenient *finite* fields in this context are the Z_p for prime p.

In this context it is also easy to make a uniform choice of a random
coefficient and to quantify the work-factor for a brute-force attack.

With rationals, everything is much messier. There is no good reason to
work over Q.

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

An algorithm is not the same an implementation. There was no Java back
then either, and people still somehow wrote working code in '79.

-- 

 /"\ ASCII RIBBON  NOTICE: If received in error,
 \ / CAMPAIGN Victor Duchovni  please destroy and notify
  X AGAINST   IT Security, sender. Sender does not waive
 / \ HTML MAILMorgan Stanley   confidentiality or privilege,
   and use is prohibited.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com

Re: Question about Shamir secret sharing scheme

[David-Sarah Hopwood]

Kevin W. Wall wrote:
> Hi list...I have a question about Shamir's secret sharing.
> 
> According to the _Handbook of Applied Cryptography_
> Shamir’s secret sharing (t,n) threshold scheme works as follows:
> 
> SUMMARY: a trusted party distributes shares of a secret S to n users.
> RESULT: any group of t users which pool their shares can recover S.
> 
> The trusted party T begins with a secret integer S ≥ 0 it wishes
> to distribute among n users.
> (a) T chooses a prime p > max(S, n), and defines a0 = S.
> (b) T selects t−1 random, independent coefficients defining the random
> polynomial over Zp.
> (c) T computes Si = f(i) mod p, 1 ≤ i ≤ n (or for any n distinct
> points i, 1 ≤ i ≤ p − 1), and securely transfers the share Si
> to user Pi , along with public index i.
> 
> The secret S can then be computed by finding f(0) more or less by
> using Lagrangian interpolation on the t shares, the points (i, Si).
> 
> The question that a colleague and I have is there any cryptographic
> purpose of computing the independent coefficients over the finite
> field, Zp ?

Yes, the information-theoretic security of the scheme depends on
performing the arithmetic in a finite field, and on the coefficients
being chosen randomly and independently in that field. In Shamir's
original paper:



the statement that "By construction, these p possible polynomials
are equally likely" depends on these conditions. I believe any finite
field will work, but Zp is the simplest option.

[Incidentally, if you're implementing this from Handbook of Applied
Cryptography, there's an erratum for that section (12.71):
"of degree at most t" in the paragraph after the Mechanism should be
"of degree less than t".]

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com

Re: Question about Shamir secret sharing scheme

[Jerry Leichter]

On Oct 3, 2009, at 2:42 AM, Kevin W. Wall wrote:


Hi list...I have a question about Shamir's secret sharing.

According to the _Handbook of Applied Cryptography_
Shamir’s secret sharing (t,n) threshold scheme works as follows:

   SUMMARY: a trusted party distributes shares of a secret S to n  
users.

   RESULT: any group of t users which pool their shares can recover S.

   The trusted party T begins with a secret integer S ≥ 0 it wishes
   to distribute among n users.
   (a) T chooses a prime p > max(S, n), and defines a0 = S.
   (b) T selects t−1 random, independent coefficients defining  
the random

   polynomial over Zp.
   (c) T computes Si = f(i) mod p, 1 ≤ i ≤ n (or for any n  
distinct
   points i, 1 ≤ i ≤ p − 1), and securely transfers the  
share Si

   to user Pi , along with public index i.

The secret S can then be computed by finding f(0) more or less by
using Lagrangian interpolation on the t shares, the points (i, Si).

The question that a colleague and I have is there any cryptographic
purpose of computing the independent coefficients over the finite
field, Zp ?  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. 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.

So other than perhaps compatibility with other implementations (which
we are not really too concerned about) is there any reason to continue
to do the calculations over Zp ???
It's nice to be able to give a size limit for the shares.  They're  
going to need to be transmitted and stored.  Since there are many  
primes around, working over Zp ensures that shares about about the  
same size as the secret.


However, there's also a more fundamental problem:  In step (b), how do  
you choose your coefficients randomly over all of Z?  There is no  
uniform probability distribution over Z to work with.  Any realistic  
implementation will choose from some finite subset.  But then the  
scheme may not be completely secure:  If you have the value of f() at  
t-1 points, the fact that the coefficients are limited to some finite  
set also constrains the possible values at the remaining point - and  
you don't know exactly how.  Working over Zp's group structure ensures  
that if you have t-1 values, all p-1 possible remaining values are  
equally likely, so you've learned nothing.


-- Jerry

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com

Re: Question about Shamir secret sharing scheme

["Hal Finney"]

Kevin W. Wall asks about Shamir sharing:
> The question that a colleague and I have is there any cryptographic
> purpose of computing the independent coefficients over the finite
> field, Zp ?

Yes, you do have to be careful to do that. You want to make sure the
shares don't leak any information about the secret S.

Consider the simplest case where two people are involved. Call the single
random coefficient c, with secret S, then the two shares are:

S + c
S + 2c

Now if this is mod p, and c is chosen at random mod p, then both c and
2c will be random mod p, and each perfectly hides the value of S when
it is added mod p, similarly to a one-time-pad. Neither share leaks any
information about the value of S.

But suppose for convenience you did the math mod some power of 2 (or
even just over the integers). Then 2c is going to be even, regardless
of c. And seeing S + 2c will then reveal whether S is even or odd,
defeating the privacy of the scheme.

Hal Finney

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com

Re: Question about Shamir secret sharing scheme

[Matt Ball]

On Sat, Oct 3, 2009 at 12:42 AM, Kevin W. Wall  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 majord...@metzdowd.com

Re: Question about Shamir secret sharing scheme

[Jonathan Katz]

On Sat, 3 Oct 2009, Kevin W. Wall wrote:


Hi list...I have a question about Shamir's secret sharing.

According to the _Handbook of Applied Cryptography_
Shamir’s secret sharing (t,n) threshold scheme works as follows:

   SUMMARY: a trusted party distributes shares of a secret S to n users.
   RESULT: any group of t users which pool their shares can recover S.

   The trusted party T begins with a secret integer S ≥ 0 it wishes
   to distribute among n users.
   (a) T chooses a prime p > max(S, n), and defines a0 = S.
   (b) T selects t−1 random, independent coefficients defining the random
   polynomial over Zp.
   (c) T computes Si = f(i) mod p, 1 ≤ i ≤ n (or for any n distinct
   points i, 1 ≤ i ≤ p − 1), and securely transfers the share Si
   to user Pi , along with public index i.

The secret S can then be computed by finding f(0) more or less by
using Lagrangian interpolation on the t shares, the points (i, Si).

The question that a colleague and I have is there any cryptographic
purpose of computing the independent coefficients over the finite
field, Zp ?


Just to add two comments to what others have already said:
- You can use any finite field. In particular, if your secret is a bit 
string of length k you can use the field GF(2^k) to get share size equal 
to secret size. (Whereas if you work mod p you lose a bit.)


- As you describe the scheme above, note that you actually leak an 
upper-bound on the size of the secret (namely, it is at most p). The setup 
for Shamir secret sharing (and any other scheme, for that matter) assumes 
the range of the secret is public knowledge already.

Re: Question about Shamir secret sharing scheme

[Victor Duchovni]

On Sun, Oct 04, 2009 at 05:44:37PM -0600, Matt Ball 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.
> 

When using a finite subset of a totally ordered coefficient field
(such as Q) whose "+" operator is order preserving (a < b => a + c < b + c
for all c), we always see some outputs leaking more information
than others. This covers any subsets of Z as Z is a subset of Q.

A finite subset of such a field always has a minimal element.

For example, if all the coefficients happen to be equal to the least
possible coefficient, the person with share "1" easily concludes that
he has the least possible sum, and recovers the secret coefficients.

Using infinite subsets means unbounded storage requirements for the
coefficients, and necessarily a non-uniform distribution of coefficients,
with some polynomials more probable than others, so again data leakage.

Leaking no information is only possible in a finite field, of which the
Z_p are the "simplest", but (as pointed out upthread) Galois extensions
of Z_2 are typically more convenient computationally.

-- 

 /"\ ASCII RIBBON  NOTICE: If received in error,
 \ / CAMPAIGN Victor Duchovni  please destroy and notify
  X AGAINST   IT Security, sender. Sender does not waive
 / \ HTML MAILMorgan Stanley   confidentiality or privilege,
   and use is prohibited.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com