[tor-dev] PrivCount - Draft of secret-sharing specification

[Ian Goldberg]

Thanks for the writeup!  Some notes inline.

On Mon, Sep 25, 2017 at 09:26:13AM +0200, Carolin Zöbelein wrote:
> 1. Introduction
> 
> 	Assume, we have a given secret s which we want to share with a particular
> 	number N of participants who are only together be able to reconstruct it.
> 	To realize this, we can split our secret in n parts s_i. Our secret will be 
> 	then the sum over all s_i. This is the simplest secret sharing scheme at all.
> 	Since it needs all participants for the reconstruction, it is called a (N,N) 
> 	treshold secret sharing algorithm.
> 
> 	But we also see that it has weaknesses. With every leaked share s_i, an 
> 	adversary can reduce the number of possible soulutions for our secret very
> 	easily. This leads to the group of more efficient secret sharing algorithms.

This is not true.  Even if N-1 of the shares are exposed, *zero
information* about the secret is leaked!

> 	In [4], Adi Shamir introduced a (K,N) secret sharing scheme which is named 
> 	after him and offers more security.

Shamir secret sharing is not more secure than the above additive secret
sharing.  But it is more flexible, as you allude to below.

>       Additionally, on the contrary to our 
> 	scheme above, we only need a minimum amount of k out of n participants to 
> 	reconstruct the secret. Our specification will be	based on this scheme.
> 
> 3. Overview and preliminaries
> 
> 	In this section, we make some preparations for the protocol specification
> 	itself.
> 
> 	3.1. Scope
> 
> 		In this document we describe the protocol specification for a Shamir 
> 		Secret Sharing scheme on a finite field of size p > s and p > N, with p 
> 		be prime number.

If your secrets are large (more than one machine word), this isn't
actually the best way to do it.  But teor's followup message suggested
using 64-bit p, which would be fine.  (p = 2^63-25, for example.)

> 		The secret sharing protocol has three participating parties which we will
> 		call as follows:
> 
> 			Secret Keeper (SK) knows the secret, does the initial setup and 
> 			determines the secret shares.

The SK is typically called the "Dealer".

> 		2.	The SK generate a random prime number p, with p > s AND p > N.
> 				[see sec. 5.3.]

(See notes in 5.3 below, and similarly for the other points in this
section.)

> 5. Specification
> 
> 	Now we will give more details to the raw outline above.
> 	
> 	5.1. Given constants
> 
> 		"s", type: int, exactly one, integer
> 			The given secret.

As you say below, s is an element of Z/pZ, not precisely an integer.

> 		"N", type: int, exactly one, natural number
> 			The number of participating SHs.
> 			It MUST to be N >= N_min.
> 
> 			=> TODO: Which value should N_min has? Default: N_min = 2?
> 
> 		"K", type: int, exactly one, natural number
> 			The threshold of the minimum number of necessary shares for the
> 			reconstruction.
> 			It MUST to be K <= N.
> 
> 			=> TODO: Are more (size) information necessary? E.g. amount of bits/bytes?
> 				I think so.

Not sure what you mean by this last bit.

> 	5.3. Prime number
> 
> 		Since we are using a secret sharing scheme on a finite field, we need a
> 		random prime number.

There is no reason for p to be random.  It is totally fine to just fix
it large enough to be larger than both s and N, as you have written.

> 		"p", type: int, exactly one, prime number
> 			It MUST to be p > s AND p > N AND it MUST to be the secret s element of 
> 			Z/pZ.
> 
> 		=> TODO: I'm not sure how exactly p should be handled. When and from where,
> 			is it given to whom?
> 
> 		=> TODO: Do we need to write anything about the necessary "random" 
> 			characteristic? The "quality" of the randomly generation of the number?
> 
> 		=> TODO: Minimum size of p? Which value should p has, at least, caused by
> 			security reasons?
> 
> 		=> TODO: Are more (size) information necessary? E.g. amount of bits/bytes?
> 			I think so.
> 
> 	5.4. The secret keeping polynomial
> 
> 		"a_j", type: int, K-1 values, Z/pZ
> 		"g[X]", type: polynomial with order K-1, exactly one, (Z/pZ)[X]
> 
> 		The SK determines the final secret keeping polynomial, which is given by
> 		
> 			g[X] := s + SUM(a_j*X^j) 
> 
> 		and hence our secret for g[0] = s. Its random coefficients are a_j, 
> 		1 <= j <= K-1 which MUST be element of Z/pZ.
> 		
> 		=> TODO: Which constraints exists for this a_j values? Size? Relative,
> 			pairwise, distance a_j - a_m between for all a_j,a_m with j != m?
> 			Is this relevant? References for this?

No, the a_j values must each be uniformly random elements of Z/pZ.
There must be no enforced relationships among them.

> 		=> TODO: Are more (size) information necessary? E.g. amount of bits/bytes?
> 			I think so.

Not more than "uniformly random elements of Z/pZ".

> 	5.5. The secret shares
> 
> 		"x_i", type: int, N values, Z/pZ
> 		"y_i", type: int, N values, Z/pZ
> 		"(x_i,y_i)", type: (int,int), N value pairs, Z/pZ -> Z/pZ
> 
> 		The SK determines the random secret shares parts x_i, i <= N which MUST be 
> 		element of Z/pZ and MUST be pairwise different from zero.

Not sure what "pairwise different from zero" means.  They should be
pairwise different (no two the same) and all non-zero; is that what you
meant?

> 		With this x_i, SK computes the secret shares parts y_i := g[x_i] and hence
> 		the finally secret share pairs (x_i,y_i).
> 
> 		=> TODO: How should this x_i be generated? Distribution?
> 			E.g. the smallest, non negative, representatives? 

x_i = i is totally fine (for i = 1, ..., N).

> 		=> TODO: Which constraints exists for this x_i values? Size? Relative,
> 			pairwise, distance x_i - x_m between for all x_i,x_m with i != m?
> 			Is this relevant? References for this?
> 
> 		=> TODO: Are more (size) information necessary? E.g. amount of bits/bytes?
> 			I think so.

As above.

> 	5.7. SR receives secret shares from the SHs
> 
> 		The SR MUST receive K secret share pairs from the SHs and p from the SK. 
> 		The SR MUST receive exactly one secret share pair (x_,y_h), 1 <= h <= k, 
> 		from each SH_h

x_h above instead of x_, presumably?

> 		=> TODO: How exactly has to look the data which has to be send as response
> 			to the SHs? What, which additionally data, has to be send? And which 
> 			size has it (bits/bytes) to be?
> 		
> 		=> TODO: I'm not sure how exactly p should be handled. When and from where,
> 			is it given to whom?
> 
> 		=> TODO: From where comes the information about N and K? (and p?)
> 
> 		=> TODO: Where has to be decided, from which K out of N SHs has this
> 			(x_h,y_h) to come from? And how (randomly)? And in which way has this 
> 			to be comunicated to the given parties? !!!

It's actually fine to receive *more* than K shares, and it in fact can
help you pick out SHs that give you incorrect values, through error or
malice.

> 	5.8. Reconstruction
> 	
> 		"l_h[x]", type: polynomial with order K-1, K, (Z/pZ)[X]
> 
> 		The SR compute the Lagrange basis polynomials l_h[x] with the secret share 
> 		pairs (x_h,y_h), 1 <= h <= K, which it received from the SHs. The SR MUST 
> 		receive exactly K pairs from exactly K SHs. I MUST be exactly one secret 
> 		share pair from each, of this K, SH.

What is "I" here?

> 		The Lagrange basis polynomials are given by 
> 			
> 			l_h[X]:= PRODUCT(1 <= m <= K AND m != h, (X - x_m)/(x_h - x_m))
> 		
> 		with 1 <= j <= K. This leads to our original secret keeping polynomial
> 
> 			g[X] := SUM(h=1, K, y_h*l_h[x] mod p)
> 
> 		and the given secret by s = g[0].

You don't actually have to reconstruct the whole polynomial.  It's
easier to just compute g[0] directly by plugging X=0 into the definition
of l_h[X] above, to yield:

        l_h[0] := PRODUCT(1 <= m <= K AND m != h, x_m / (x_m - x_h))
        g[0] := SUM(h=1, K, y_h * l_h[0])

This step will also of course change if you want to handle more than K
shares or incorrect shares.

> 		=> TODO: From which K out of N SHs come this secret shares?
> 	
> 		=> TODO: Are more (size) information necessary? E.g. amount of bits/bytes?
> 			I think so.