Suppose we have a set of $N$ parties. I am looking for a scheme to generate shares of a random secret $s$ where any subset of the participants with size $k$ can recover the secret similar to Shamir's scheme. Additionally, no party outside of the group, such as a dealer, has access to $s$.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Can you elaborate on your requirements? Who is generating the secret and what are you using it for? $\endgroup$– Aman GrewalCommented Sep 24, 2020 at 18:01
-
1$\begingroup$ Or, do you not care what the secret is (only that any subset with size $k$ can rederive the same secret)? $\endgroup$– ponchoCommented Sep 24, 2020 at 19:15
-
$\begingroup$ @poncho we do not care about the secret, it is just a random value. $\endgroup$– Erfan HosseiniCommented Sep 24, 2020 at 20:32
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
I think this can be done relatively simply with any additive secret sharing scheme (which Shamir's scheme is). The basic idea behind the scheme (to make a $(n, k)$ no-dealer secret sharing scheme) is:
- Each party samples a uniformly random value $s_i\in\mathbb{F}_p$
- Each party makes $n$ shares of this value (using an additive $(n, k)$ secret sharing scheme), which we will call $\{s_{i, j}\}$ for $j\in[n]$
- For all $(i, j)\in[n]^2$, Party $i$ sends $s_{i, j}$ to party $j$.
- For all $i\in[n]$, party $i$ sets $s_i' = \sum_{j\in[n]}s_{i, j}$
- All parties are left with a sharing of $s' = \sum_{i \in[n]} s_i$
The idea for why this should be secure (up to the threshold $k$) is that there are really three things an adversary can do:
- Choose $s_i$ non-uniformly (and among the $k-1$ parties, choose them dependent in some way)
- Send out "incorrect" shares of their secret
- Compute $s_i'$ incorrectly
The first two points can be seen to be equivalent, as sending out "incorrect" shares is the same as sending out correct shares of an incorrectly sampled secret. If you know a group of honest parties will reconstruct the secret, these incorrectly sampled secrets will not be an issue (the sum $s' = \sum_{i\in[n]}s_i$ will be uniformly distributed as long as any $s_i$ is individually uniformly distributed, and all other secrets are independent of this value).
I don't know how tolerant the above will be to corruptions during the reconstruction process, but it doesn't seem like this is what you're asking about. I imagine it would be roughly as tolerant as the "base" additive secret sharing scheme is, but don't have a readily available argument (so will omit this, while mentioning that it's an interesting thing to think about).
This also has relatively high communication complexity ($O(n^2)$ in the sharing process --- it feels like $O(nk)$ might be possible, but I don't want to over-optimize it right now), and can only sample secrets on fields $\mathbb{F}_p$ for which Shamir's is secure (so you must take $p$ to be exponentially large, so it is wasteful in the size of communications (instead of just the number of messages) if you only need a "small" secret to be agreed upon), which seem like the major "downsides" of it to me.
answered Sep 28, 2020 at 17:35
-
$\begingroup$ Thank you for your answer. Would you be able to help me optimize it to a lower communication complexity? $\endgroup$ Commented Oct 18, 2020 at 23:08
-
$\begingroup$ There are two sources of inefficiency. One is the (relatively) large size of Shamir shares (linear in the security parameter). You should be able to use any additively homomorphic threshold secret sharing scheme in the above though, so look for ones with smaller shares (maybe achieving only computational security, I do not know). To reduce the number of shares sent out from $O(n^2)$ to $O(nk)$, you would need to have some argument that each participant can choose some subset of size $O(k)$ to send shares to such that whp all subsets of size $\geq k$ can reconstruct the secret... $\endgroup$– Mark Schultz-Wu ♦Commented Oct 18, 2020 at 23:13
-
$\begingroup$ Things (might) get weird in this setting --- you need to start worrying about the secret value potentially changing depending on which subset reconstructs (If $k$ gets too small this feels like a risk). Regardless the secret value reconstructed should be uniformly random, so this may not be an issue, but essentially if you try to optimize from $O(n^2)\to O(nk)$ it feels like it becomes a much more subtle question that one could work out the details for, but it would take more effort (for me) then I put into stack exchange answers. $\endgroup$– Mark Schultz-Wu ♦Commented Oct 18, 2020 at 23:17
-
$\begingroup$ Thank you for your response. Can you introduce some references so I could read about other threshold secret sharing schemes that have smaller shares than Shamir's? $\endgroup$ Commented Oct 21, 2020 at 2:07
-
$\begingroup$ @ErfanHosseini I am not very familiar with the area, so this would be better asked as a separate question. I believe Shamir's is near-optimal for information-theoretic methods (see for example this paper), but often you can get around these kind of bounds by weakening the notion of secrecy from an information-theoretic one to a computational one. $\endgroup$– Mark Schultz-Wu ♦Commented Oct 21, 2020 at 3:41
$\begingroup$
$\endgroup$
5
One way to do this is to have $k$ participants roll random numbers. Treat them as if they were in a $(k, k)$ sharing scheme. They can then redistribute to a $(k, N)$ sharing scheme.
This can be extended to start with any $m$ participants, $k \le m \le N$, before redistributing to a $(k, N)$ scheme. Starting with $N$ participants avoids having to choose a special subset that starts the protocol.
In the steps below, all operations are done in some finite field, $F$.
Assign each of the $N$ members a public value (this will be used as the x-value in the Lagrange Interpolation).
Choose some $k < N$ participants to establish the secret. They do this by rolling a random number in $F$. These shares combine to the secret $s$, but we as long we don't try to reconstruct it, the secret remains secret.
Then we redistribute to all $N$ members. Each of the $k$ participants treats her share as a secret and deals it out in a $(k, N)$ scheme to all members. Each member reconstructs these $k$ values to get his final share. Now all participants are in a $(k, N)$ scheme that can reconstruct the original secret $s$.
I'm assuming that a distributed key generation is what is wanted. There are several references to this in literature, but usually they're buried within a signature scheme or some other end goal. For example, refer to Section 4.1 in Fast Multiparty Threshold ECDSA with Fast Trustless Setup by Gennaro and Goldfeder or Section 2.3 in FROST: Flexible Round-Optimized Schnorr Threshold Signatures by Komlo and Goldberg.
answered Sep 24, 2020 at 20:41
-
1$\begingroup$ Doing this would require us to reveal the secret to everyone $\endgroup$ Commented Sep 24, 2020 at 21:02
-
1$\begingroup$ No, each participant has a random share for some unknown secret. Redistribution doesn't reveal the secret. $\endgroup$ Commented Sep 24, 2020 at 21:24
-
$\begingroup$ It might be good if you went into more details about how this redistribution phase is done $\endgroup$– ponchoCommented Sep 24, 2020 at 21:30
-
$\begingroup$ Someone must choose which $k$ of the $N$ participants are the ones who get to establish the secret. Nor is it at all clear whether the blessed $k$ each draw random number which somehow get combined into one secret or they somehow collaborate to produce one random number which then becomes the secret. Unless more details are forthcoming soon, I intend to downvote this answer $\endgroup$ Commented Sep 26, 2020 at 19:26
-
$\begingroup$ Yes, there needs to be some way to choose which $k$ participants are involved. Alternatively, you could start in a $(N,N)$ scheme and redistribute it to a $(k,N)$ scheme, which avoids having to choose $k$ participants at the beginning in exchange for more total work. I don't understand the second point you make. $\endgroup$ Commented Sep 26, 2020 at 19:31