Thanks for the writeup! Some notes inline.
On Mon, Sep 25, 2017 at 09:26:13AM +0200, Carolin Zöbelein wrote:
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 ourscheme 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.
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.)
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 byg[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.