Re: Question about Shamir secret sharing scheme

2009-10-05 Thread 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

2009-10-04 Thread 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

2009-10-04 Thread 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:

http://www.caip.rutgers.edu/~virajb/readinglist/shamirturing.pdf

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

2009-10-04 Thread 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

2009-10-04 Thread 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