My earlier mail in this thread bounced for Reasons. Here it is again.
- Ian
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.
_______________________________________________
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
