Hi (PrivCount) folks!
I just finished the first draft of the k,n-secret-sharing thing for PrivCount. :)
Sorry that it need some time, but I'm sadly a bit slowly with reading and writing.
You can find it here at github:
https://github.com/Samdney/28X-k-of-n-secret-sharing
and also below in this email.
You will see a lot of "=> TODO". This belongs of course not to the specification ;). There are still a lot of open details and questions left (or stuff which still have to be written, I think) and hence it is time for some help from you, now.
I looked a bit around how a specification has to look like, before I started to write it, but this was more confusing like helpful, hehe.
I'm a completely newbie with writing this kind of documents, hence I'm pretty nervous for your feedback :)
Bye, Carolin
========== Draft v1 ========== Filename: 28X-k-of-n-secret-sharing.txt Title: k-of-n Secret Sharing Author: Carolin Zöbelein Created: XX-Sept-2017 Status: Draft
0. Motivation
The implementation of schemes for collecting statistic data within a high sensitive network like Tor for preserving anonymity, is a hard challenge. Over the years the Tor network has grown but its usage and operation is not well-understood and already existing ways [1] leads to some open issues [maybe add also a reference here].
For doing this better like the current state of the art, we discuss to switch to PrivCount [2][3], a system for measuring the Tor network created with a high attention on user privacy.
PrivCount consists of a system of Data Collectors (DC) which forward their blinded measure counter results to a number of, so-called, Tally Reporters (TR) which are only together be able to reconstruct the original data.
In the context of the implementation of the mentioned system, we decided to use a secret sharing algorithm for forwarding the blinded counter values. This gives us the chance of reconstructing the data also with a particular minimum amount of secret share holders and hence a failure handling possibility of Tally Reporters.
=> TODO: References [maybe add also a reference here]
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. In [4], Adi Shamir introduced a (K,N) secret sharing scheme which is named after him and offers more security. 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.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119.
3.2. Notation
We will use for public, non-secret, values UPPER CASE and for private, secret, values lower case.
We write: "a", type: b, c, d "a" gives the name of the parameter. type: b be the type of the parameter a. c be the amount of this parameters. d be the mathematical definition set for a.
Mathematical assignments:
Let "a := b" be the assignment of the value of b to the variable a.
Let "a mod b" be the modulus calculation of a with respect to b.
Let "a != b" be that a is unequal to b. In our document "natural numbers" are defined as the set of all integers greater than zero.
g[X] describes a polynomial with respect to X.
SUM(a_i) gives the sum over a_i for all known i.
SUM(i=a,b,c_i) gives the sum over all c_i for all a <= i <= b.
PRODUCT(a,b,c_i) gives the product over all c_i for all a <= i <= b.
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. Share Holders (SH) receive the secret shares from the SK. Secret Reconstructor (SR) takes a particular number of secret shares from the SHs and reconstruct the secret.
4. Protocol outline
We give a raw protocol overview.
0. Preparation: The parties negotiate an appropriate handshake and communication way for forwarding the secret shares between SK to the SHs and between the SHs to SR. [This is not part of that specifiation] => TODO: Do we need a more detailed definition of "appropriate"?
1. The SK knows the secret s. Additionally, given are the amount N of participating SHs and the threshold K for the minimum number of necessary shares for the reconstruction. [see sec. 5.1.]
2. The SK generate a random prime number p, with p > s AND p > N. [see sec. 5.3.]
3. The SK determines the secret polynomial coefficients a_j, 1 <= j <= K-1. With this, the secret keeping polynomial is given by g[X] := s + SUM(a_j*X^j). [see sec. 5.4.]
4. The SK determines the secret shares parts x_i, 1 <= i <= N. [see sec. 5.5.]
5. The SK computes the secret shares parts y_i := g[x_i]. [see sec. 5.5.]
6. The SK forward the secret shares to the SHs. Each SH_i MUST receive exactly one secret share pair (x_i,y_i). [see sec. 5.6.] 7. The SR receives K secret share pairs (x_h,y_h) from the SHs and p from the SK, 1 <= h <= K. [see sec. 5.7] 8. The SR compute the Lagrange basis polynomials l_h[X]. [see sec. 5.8.]
9. The SR reconstruct the original polynomial with g[x] = SUM(h=1, K, y_h*l_h[X] mod p). [see sec. 5.8.]
10. The SR computes the secret s = g[0]. [see sec. 5.8.] 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.
"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. 5.2. Parties
Secret Keeper (SK) It MUST exists exactly one SK.
Share Holders (SH) It MUST exists exactly N SHs.
Secret Reconstructor (SR) It SHOULD exists exactly one SR.
[=> TODO: SHOULD since one is necessary but more could be used for checking the result. But I would prefere MUST.] => TODO: Which additional information do we need to know/to give about the parties? 5.3. Prime number
Since we are using a secret sharing scheme on a finite field, we need a random prime number.
"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?
=> TODO: Are more (size) information necessary? E.g. amount of bits/bytes? I think so.
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.
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?
=> 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.
5.6. Sending secret shares from SK to SHs The SK sends the secret share pairs to the SHs. Each SH_i MUST receive exactly one secret share pair (x_i,y_i).
=> TODO: How exactly has to look the data which has to be send and which size has it (bits/bytes) to be?
=> TODO: Which data has also to be send apart from (x_i,y_i)?
=> TODO: How should looks like a possible answer of the SHs for the SK to confirm the receipt? [Is this necessary, at all? I think so.]
=> TODO: I'm not sure how exactly p should be handled. When and from where, is it given to whom?
=> TODO: I need a helping hand for this specification section :)
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
=> 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? !!!
=> TODO: I need a helping hand for this specification section :)
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.
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].
=> 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.
6. Security discussion => TODO: Write important points about the security aspects of this scheme. :)
7. References [1] https://www.cypherpunks.ca/~iang/pubs/privex-ccs14.pdf [maybe add also a reference here] [2] http://www.robgjansen.com/publications/privcount-ccs2016.pdf [3] https://github.com/privcount/privcount [4] Shamir A., "How to share a secret", Communications of the ACM. 22, 1979, S. 612–613.
=> TODO: References => TODO: Correct references for regular citation => TODO: Add missing references
A. Lemma => TODO: Still to write. The Lemma (why this Shamir thing works :) proof ========== TODO: RESEARCH AND EXTENSION OF SPECIFICATION!!! => TODO: Investigate more some very interesting papers! :) => TODO: Multi-Secret Sharing Schemes!!!
TODO: MISC: => TODO: Notation stuff checking => TODO: Check my English for language mistakes :) => TODO: I used: scheme, algorithm, protocol, ... what is the best word in what context? ==========
On 25 Sep 2017, at 17:26, Carolin Zöbelein contact@carolin-zoebelein.de wrote:
Hi (PrivCount) folks!
I just finished the first draft of the k,n-secret-sharing thing for PrivCount. :)
Sorry that it need some time, but I'm sadly a bit slowly with reading and writing.
You can find it here at github:
https://github.com/Samdney/28X-k-of-n-secret-sharing
and also below in this email.
You will see a lot of "=> TODO". This belongs of course not to the specification ;). There are still a lot of open details and questions left (or stuff which still have to be written, I think) and hence it is time for some help from you, now.
I looked a bit around how a specification has to look like, before I started to write it, but this was more confusing like helpful, hehe.
I'm a completely newbie with writing this kind of documents, hence I'm pretty nervous for your feedback :)
Hi,
This looks like a great overview of the Shamir secret-sharing protocol.
We talked about instantiating it with unsigned 64-bit integers on IRC. It would be easier for me to understand it (and for someone to code it).
This would also help us define an interchange format, or modify the prop 280 interchange format to support secret sharing.
For hints about how this works, look at proposal 280, which also uses unsigned 64 bit integers.
Tim
T -- Tim Wilson-Brown (teor)
teor2345 at gmail dot com PGP C855 6CED 5D90 A0C5 29F6 4D43 450C BA7F 968F 094B ricochet:ekmygaiu4rzgsk6n ------------------------------------------------------------------------
Hi,
Hi,
This looks like a great overview of the Shamir secret-sharing protocol.
We talked about instantiating it with unsigned 64-bit integers on IRC. It would be easier for me to understand it (and for someone to code it).
This would also help us define an interchange format, or modify the prop 280 interchange format to support secret sharing.
For hints about how this works, look at proposal 280, which also uses unsigned 64 bit integers.
Tim
I will work on this and the long list of still open TODOs in the proposal, the next days. Hence please have a look at
https://github.com/Samdney/28X-k-of-n-secret-sharing
for changes, from time to time.
I will be around at irc, too ;).
Btw, should I also create a ticket for this proposal for important topic discussions?
Bye, Carolin
Hello,
This appears to be a sketch of Shamir secret sharing, which will be just one tool used in the PrivCount system. For example, it is missing how relays (aka Data Collectors) maintain counters, how aggregators (aka Share Keepers) aggregate counters, and how secret sharing is used among those entities to provide fault tolerance for the aggregation process.
The grammar and writing style need improvement. They are at a level that makes the proposal hard to understand at times.
There are many important missing details even in the secret sharing component: - How is p determined? - How is N determined? - Who plays the roles of the SK, SHs, and SR? How do these relate to the parties in PrivCount?
Some minor notes I kept before it became clearer that higher-level comments would be more useful: - Sec. 1: Description of secret sharing is incorrect. Strict subsets of shares in a simple additive secret-sharing scheme do not leak information. - Sec. 1: Variable capitalization (e.g. K vs. k, N vs. n) should be consistent. - Sec. 3.2: I could not understand what notation was being introduced through a, b, c, and d. - Sec. 3.2: SUM and PRODUCT variable notation is inconsistent ("i=" missing from PRODUCT). - Sec. 3.2: "Secret Keeper (SK)" has an unfortunate collision with the acronym for Share Keeper, which is a different role in the PrivCount paper. - Sec. 4, Step 2: The prime need not be random. It can be fixed and public. - Sec. 4, Step 3: Specify how the coefficients are determined.
Best, Aaron
On Sep 27, 2017, at 11:20 PM, Carolin Zöbelein contact@carolin-zoebelein.de wrote:
Hi,
Hi,
This looks like a great overview of the Shamir secret-sharing protocol.
We talked about instantiating it with unsigned 64-bit integers on IRC. It would be easier for me to understand it (and for someone to code it).
This would also help us define an interchange format, or modify the prop 280 interchange format to support secret sharing.
For hints about how this works, look at proposal 280, which also uses unsigned 64 bit integers.
Tim
I will work on this and the long list of still open TODOs in the proposal, the next days. Hence please have a look at
https://github.com/Samdney/28X-k-of-n-secret-sharing
for changes, from time to time.
I will be around at irc, too ;).
Btw, should I also create a ticket for this proposal for important topic discussions?
Bye, Carolin
--
Carolin Zöbelein / Nick: Samdney PGP: D4A7 35E8 D47F 801F 2CF6 2BA7 927A FD3C DE47 E13B
tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Hi,
Am Donnerstag, den 28.09.2017, 11:48 -0400 schrieb Aaron Johnson:
Hello,
This appears to be a sketch of Shamir secret sharing, which will be just one tool used in the PrivCount system. For example, it is missing how relays (aka Data Collectors) maintain counters, how aggregators (aka Share Keepers) aggregate counters, and how secret sharing is used among those entities to provide fault tolerance for the aggregation process.
=> Yeap, this stuff is still missing and belongs to this big bunch of TODOs which were in the proposal. I skipped some of this points since I would need some help with this. Additionally, I'm not complettely sure which PrivCount specific topics have to be the content of this proposal and which topics belong to a rewritten 280-privcount-in-tor.txt proposal.
The grammar and writing style need improvement. They are at a level that makes the proposal hard to understand at times.
=> Thank you for this feedback. My English is not the best. I work on this problem.
There are many important missing details even in the secret sharing component:
- How is p determined?
- How is N determined?
- Who plays the roles of the SK, SHs, and SR? How do these relate to the parties in PrivCount?
Some minor notes I kept before it became clearer that higher-level comments would be more useful:
- Sec. 1: Description of secret sharing is incorrect. Strict subsets of shares in a simple additive secret-sharing scheme do not leak information.
=> I corrected this terrible content mistake! I'm sorry! It's not super pretty ... but better like before.
- Sec. 1: Variable capitalization (e.g. K vs. k, N vs. n) should be consistent.
=> Corrected.
- Sec. 3.2: I could not understand what notation was being introduced through a, b, c, and d.
=> Oh, is this really so confusing(?). For the moment I didn't change it since I'm not sure how I can write it in a better way. => Still TODO.
- Sec. 3.2: SUM and PRODUCT variable notation is inconsistent ("i=" missing from PRODUCT).
=> Corrected.
- Sec. 3.2: "Secret Keeper (SK)" has an unfortunate collision with the acronym for Share Keeper, which is a different role in the PrivCount paper.
=> I will rename the parties since I it can be confusing.
- Sec. 4, Step 2: The prime need not be random. It can be fixed and public.
- Sec. 4, Step 3: Specify how the coefficients are determined.
Best, Aaron
Bye and thank you for your feedback, Carolin
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.
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:
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.
Hi,
thank you for your feedback!
I have to say this....
Am Donnerstag, den 28.09.2017, 14:35 -0400 schrieb Ian Goldberg:
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:
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!
... is of course, very big trash which I wrote in the proposal.
Why did I write this? I don't know. I think I had Gaussian elimination in my mind which is absolute nonsense if you only have one equation, of course! *argh*
Sometimes, by brain does strange things ;)
I have some comments to the other things you pointed out. I will follow up with some emails, tomorrow.
Bye and thank you for your help! Carolin
-
Aaron Johnson -
Carolin Zöbelein -
Ian Goldberg -
teor