Secret sharing, introduced by the seminal works of Shamir [
23] and Blakley [
1], is the following problem (in its most basic formulation): suppose we wish to encode and distribute a secret
\(s \in \mathbb {F}_2^k\) among
n parties in such a way that (i) the
n parties can reconstruct the original secret
s by revealing their respective shares; and, (ii) for some integer parameter
\(t > 0\) (called the
privacy parameter), any group of
t parties cannot infer any information about the secret from their collection of shares. In coding-theoretic terms, the goal is to encode
s (using randomness) into a sequence
\(Y_1, \ldots , Y_n\) over some alphabet of size
Q, in a way that
s can be reconstructed from the encoding and moreover, for any
\(i_1, \ldots , i_t \in [n]\), the sequence
\(Y_{i_1}, \ldots , Y_{i_t}\) has the same distribution regardless of the message
s.
Shamir proposed a beautiful scheme that provides an optimal solution to the problem. The scheme regards the secret as an element of the finite field \(\mathbb {F}_Q\), for some prime power \(Q \ge n\), and then samples a uniformly random univariate polynomial of degree at most t over \(\mathbb {F}_Q\) with the constant term set to be s. The coding-theoretic interpretation of this solution is that s is amended with t uniformly random and independent elements of \(\mathbb {F}_Q\) and the result is encoded using a Reed-Solomon code of length n and dimension \(t+1\). Shamir’s solution works even if the adversary uses an adaptive strategy; i.e., when each of the query positions \(i_1, \ldots , i_t\) depends on the observation outcomes at the previous locations. Adaptive security is a property that is generally sought after for secret sharing schemes.
Due to its coding-theoretic nature, Shamir’s scheme provides at least two additional benefits. First, any group of parties is able to recover
s as long as the size of the group is larger than
t. This so-called “threshold property” is due to the fact that the Reed-Solomon code is an MDS code. Second, any Reed-Solomon code of rate
R is able to tolerate any fraction of errors up to
\((1-R)/2\) and this can be achieved by an efficient decoder (such as the Berlekamp–Massey decoding algorithm, cf. [
22, Chap. 6]). As a result, a straightforward calculation shows that Shamir’s secret sharing scheme is
robust, in the sense that it can tolerate malicious parties that submit incorrect shares. In particular, the correct secret
s can be always reconstructed even if up to a third of the parties reveal their shares incorrectly. In fact, this holds true even if the malicious parties are able to arbitrarily communicate with each other and choose the incorrect shares adversarially.
More strongly, Shamir’s scheme is secure against the so-called “rushing” adversaries. In the rushing setting (also known as “secret sharing with reconstructor”), reconstruction is done by each party broadcasting their (possibly corrupted) shares in an order determined by the protocol. This means that the adversary may attempt to, adaptively, manipulate shares at any point in the reconstruction phase (up to its allotted budget) based on its (adaptive) observation of up to
t shares as well as all the shares (including those of the honest parties) that are revealed so far. Naturally, the requirement is then that each party should be able to correctly reconstruct the secret in isolation, with high probability, from the information received from the
n parties. The error resilience of Shamir’s scheme is based on the minimum distance of Reed-Solomon code, and thus the power of the adversary is irrelevant for this scheme as long as the number of manipulations is less than the minimum distance of the code. In fact in the reconstruction phase the adversary may observe
everyone’s shares and then decide which ones to corrupt, and the set of corrupted shares may or may not overlap with the set of
t shares observed by the adversary before reconstruction (an interesting property that is not in general required in robust secret sharing, but is nevertheless satisfied by some known constructions that rely on error-correcting codes to provide robustness; e.g., [
24]).
Table 1
Summary of results in robust secret sharing scheme, and their key features and limitations
|
k
| Yes | Only robust against collusions of size \(t < n/3\) |
|
\(k+O(\log (1/\eta ))\)
| Yes | Only robust in the sense of error detection |
|
\(k+O(\log (1/\eta ))\)
| Yes | Only secure against local adversaries |
|
\(k+O(n + \log (1/\eta ))\)
| No | |
|
\(k+\tilde{O}(n + \log (1/\eta ))\)
| Yes | Secure against rushing adversaries |
|
\(k+O(n \log (1/\eta ))\)
| Yes | Secure against rushing adversaries |
|
\(k+\tilde{O}(n^2 + n\log (1/\eta ))\)
| Yes | For \(n = 2t+1\) |
| O(1) | Yes | Monte-Carlo, reconstruction from \(t+\Omega (n)\) of the shares, for large n, and \(\eta = \exp (-\Omega (n))\). |
|
\(k+O(\log (1/\eta ) (\log ^4 n+(\log ^3 n) \log k))\)
| Yes | For \(n = 2t+1\) |
This work |
\(k(1+o(1)) + O(\log (1/\eta ))\)
| Yes | |
This work | O(1) | Yes | |
Reconstruction from any \(t+\rho n\) shares, for any constant \(\rho > 0\), assuming \(\frac{t}{n} \le \frac{1}{2} - \rho \), large n and \(\eta = \exp (-\Omega (n))\) (Corollary 18). |
1.1 Previous work
The robust notion of secret sharing has been studied in the literature, and some of the key results in the area are summarized in Table
1. It is known that robust secret sharing is impossible when the fraction of dishonest parties is at least 1 / 2; i.e., when
\(n \le 2t\) [
19]. It is also impossible to always reconstruct the secret correctly (i.e., with probability 1) when the fraction of dishonest parties may be 1 / 3 or larger, in which case a small probability of error
\(\eta \) is unavoidable. Therefore, Shamir’s scheme provides optimal robustness for a scheme with zero probability of error.
When an honest majority exists, Rabin and Ben-Or [
21] provide a secret sharing scheme based on Shamir’s scheme combined with message authentication codes. The share length
\(q := \log Q\) in this scheme is, ignoring small terms,
\(k + \Omega (n \log (1/\eta ))\), where
\(\eta > 0\) is the probability of incorrect reconstruction. In contrast, an appealing feature of Shamir’s scheme is that the shares are
compact; namely, the bit length of each share is equal to the bit length of the secret (under the natural assumption that
\(n \le 2^k\)). This turns out to be optimal for schemes with perfect privacy satisfying the threshold property [
25].
Another scheme, due to Cramer et al. [
7] (and based on [
12] and also using Shamir’s scheme) improves the share length to
\(\max \{k, O(n + \log (1/\eta ))\}\). However, the reconstruction time for this scheme is in general exponential in
n (more precisely, at least
\(\left( {\begin{array}{c}n\\ t\end{array}}\right) \)), and the scheme is insecure against rushing adversaries (cf. [
10]).
Cevallos et al. [
10] propose a scheme similar to [
21] that achieves more compact shares, namely of length
\(k + O(\log (1/\eta ) + n(\log n + \log k))\). This scheme provides efficient share and reconstruction procedures and is also secure against rushing adversaries.
Cramer et al. [
8] introduce the notion of
algebraic manipulation detection (AMD) codes, which is a natural variant of error-detection codes in situations where the adversary’s perturbations on a codeword are chosen independently of the codeword. By using this primitive as a pre-code in Shamir’s secret sharing scheme (or any secret sharing scheme with linear decoder), they are able to make the scheme robust against adversarial manipulations. The key difference in their model is the notion of robustness; i.e., the requirement is that if the adversary corrupts any of the shares, the reconstruction should
detect the adversary and fail (rather than output the correct share) with high probability.
More recently, Lewko and Pastro [
2] defined a variation of robust secret sharing in which the robustness requirement is against
local adversaries. That is, the error in each share corrupted by the adversary can only depend on the particular share being corrupted. Intuitively, this corresponds to the case where a number of adversaries take control of different shares and have to decide on submitting an incorrect share only based on the local information that they possess (the adversaries may agree on a strategy beforehand but cannot communicate after observing their respective shares). They show that even in this restricted model, the minimum required share length is
\(k+\log (1/\eta )-O(1)\) (under the standard threshold assumption that any set of
\(t+1\) must reconstruct the secret with probability at least
\(1-\eta \)). Furthermore, they construct efficient schemes in the local model that attains a nearly optimal share length of
\(k+O(\log (1/\eta ))\).
In another recent work, Cramer et al. [
6] combine AMD codes with universal hash functions and (folded) list decodable codes to construct a secret sharing scheme with potentially constant share length (more precisely, share length
\(\Theta (1+\log (1/\eta )/n)\)). Their construction is with respect to a randomly chosen hash function from a universal family and is thus a Monte-Carlo construction. That is, the code construction relies on the probabilistic method (and thus may not result in the desired secret sharing scheme with unfortunate choices of the randomness), however the encoder and decoders are efficient once the randomness of the code construction is set to an appropriate choice. Moreover, this construction considers the “ramp model” in which it is not necessary to be able to reconstruct the secret from any
\(t+1\) of the shares. This relaxation is in fact necessary for any secret sharing scheme with share length smaller than the secret length
k.
Finally, Safavi-Naini and Wang [
24] construct secret sharing schemes based on codes for the wiretap channel problem for the case
\(n = 2t+1\). This construction is based on wiretap codes that are in turn based on list decodable Reed-Solomon codes, subspace-evasive sets and AMD codes, and attains a share length of
\(k+O(n^2 (\log n) (\log \log n)+ n\log (1/\eta ))\).
Subsequent to a preliminary draft of the present work, Bishop et al. [
3] construct an efficient and nearly optimal robust secret sharing scheme for
\(n = 2t+1\) that achieves share length
\(k+O(\log (1/\eta ) (\log ^4 n+(\log ^3 n) \log k))\). In general, this is incomparable with the bound we achieve (while both being very close to the optimal
\(k+O(\log (1/\eta ))\). This work follows the authentication graph idea of Rabin and Ben-Or [
21] (in which a MAC signature is used for every party in each share to authenticate the shares for every other party) and its improvement by Cevallos et al. [
10]. In particular, [
3] considers a subsampled authentication graph, leading to nearly optimal share lengths, which is then shown to provide robustness via a delicate analysis based on the approximation algorithms for the minimum graph bisection problem. It is, however, not shown whether this improvement maintains robustness against rushing adversaries.
1.2 Our contributions
In this work, we construct an essentially optimal robust secret sharing scheme against possibly adaptive, but non-rushing, adversaries. Somewhat surprisingly, our construction turns out to be strikingly similar to some of the known constructions mentioned in Sect.
1.1 and involves a simple modification of Shamir’s original secret sharing scheme.
More precisely, the construction first amends the secret with a tag using an AMD code (such as the one in [
8]). Then, it uses Shamir’s scheme to encode the result into
mn shares, for a carefully chosen integer parameter
\(m > 1\). Finally, the resulting shares are bundled into
n groups of size
m each which are distributed among the
n parties. In other words, we use a variant of Shamir’s scheme based on
folded Reed-Solomon codes (instead of plain Reed-Solomon codes) combined with an AMD pre-code. This is very similar to what used in [
8] to provide robustness in the sense of error-detection, as well as the coding-theoretic construction of Safavi-Naini and Wang [
24] (the latter additionally uses subspace-evasive sets that we do not need). Combining Shamir’s scheme with some type of information-theoretic pre-code (such as a message authentication code) can also be seen as the underlying idea of other existing constructions such as [
7].
The techniques that we use are remarkably simple to describe as well. To prove robustness, we first use an efficient list decoding algorithm of folded Reed-Solomon codes [
15] to show that the reconstruction procedure always outputs a short list containing an AMD encoding of the correct secret. Second, we use an elegant observation by Guruswami and Smith [
16] that was used by them to construct “stochastic” error-correcting codes. The observation is that, for any list decodable code that is linear over some base field, the list of potential messages corresponding to any given received word is the translation of the original message by elements of a set that only depends on the noise vector. In particular, the list of potential messages, shifted by the correct message, is only determined by the code and the error vector chosen by the adversary. For our application in secret sharing, privacy of Shamir’s scheme implies that the perturbations of the adversary, and thus the set of error vectors in the message domain, must be independent of the original message and the internal randomness of the AMD code. As a result, the error detection guarantee of the AMD code ensures that, with high probability, all the incorrect potential messages are correctly identified by the reconstruction procedure so that only the correct secret remains at the end.
Our construction and underlying ideas share an overlap with the above-mentioned recent result of Cramer et al. [
6] in which the authors construct a Monte-Carlo secret sharing scheme with small share length in the ramp model (where obtaining a sharp threshold; i.e., reconstructability from any
\(t+1\) shares, is not a requirement
1). The construction in that work can be described as follows: First, the secret
s is encoded with an AMD code, and then the result
x is mapped to a random element in
\(h^{-1}(x)\), where
h is a
fixed and appropriately chosen linear hash function. The resulting sequence is finally encoded using a list decodable code. Unfortunately, this result does not determine an explicit suitable choice for
h. However it shows, using the probabilistic method, that most functions in a universal family of hash functions are suitable choices for the hash function
h. In other words, if
h is randomly
2 picked from a universal family of hash functions, with high probability over the choice of
h the resulting scheme is robust with the desired parameters. Therefore, the hash function
h is determined by the
code construction once and for all, and the probabilistic method shows that most choices of
h would result in equally good secret sharing schemes. It is not clear, however, whether one can efficiently and deterministically find a suitable choice for the hash function
h without running an exponential-time computation (as is usual in random coding arguments). Compared with this result, our work completely eliminates the need for the hash function, and thus we finally obtain a fully explicit construction of efficient secret sharing schemes with nearly optimal parameters in all aspects. Namely, our main result in this work can be stated as follows.
Another feature of our work is its complete modularity and simplicity which can help retain the practicality of Shamir’s scheme. Our main result (Theorem
8) can be applied to any linear secret sharing scheme based on linear error-correcting codes that provides privacy via a dual distance argument (Shamir’s original scheme being a special case). As a result, we are able to instantiate the result with virtually any algebraic family of linear list decodable codes, and particularly do so for the cases of (folded) Reed-Solomon and algebraic geometry codes. In contrast, the result of Cramer et al. [
6] is only presented and proven when the underlying code is an algebraic geometry code, as the main goal of [
6] is to obtain constant share lengths. Furthermore, as discussed above, [
6] only provides a Monte-Carlo construction, since the choice of the hash function that pre-processes the secret is random which, in addition to adding to the description complexity of the final scheme, may cause the entire scheme to fail with an unfortunate choice of the (unverifiable) random hash function.
Same as Shamir’s scheme and [
24], our result does not necessarily require the observations of the adversary to coincide or overlap with the set of manipulated shares. In fact, the number of adaptive observations by the adversary may in general be different from the number of incorrect shares, and this is allowed as long as the total fraction of observations and incorrect shares add up to a quantity sufficiently smaller than 1.
Although a share length of at least
k bits is necessary for any robust secret sharing scheme [
25] (even against local, or oblivious, adversaries [
2]), it is possible to obtain smaller shares at cost of slightly relaxing the threshold property. That is, instead of requiring the secret to be reconstructible (either with probability 1 or close to 1) from any set of more than
t shares, we may require reconstructability from any set of more than
\(t+g\) shares, for a small “gap” parameter
g. A desirable level for the gap parameter is when
g is a small fraction of the number of shares, and it is reasonable to argue that a secret sharing scheme that attains such a relaxed threshold property may be of interest to most applications.
We adapt our secret sharing scheme to nonzero gap parameters and, moreover, show that when
g is a small fraction of
n, the alphabet size may be reduced to an absolute constant (depending on the fraction
g /
n and assuming that
t /
n is smaller than 1 / 2 by some constant). This is achieved by using folded algebraic geometry codes instead of folded Reed-Solomon codes and their corresponding list decoding algorithms (namely, the state-of-the-art algorithm due to Guruswami and Xing [
18]). Using algebraic geometry codes, we can prove the following.
Previously, the best known construction achieving small share length was due to Cramer et al. [
6] in which the share length is
\(\Theta (1+\log (1/\eta )/n)\) and thus grows with the security parameter (see Table
1). Moreover, as mentioned above, this construction is not fully explicit and requires a randomly chosen hash function that is fixed once and for all and there is no clear efficient way of explicitly finding an appropriate hash function.
The efficiency of the scheme in Theorem
2 is dictated by the efficiency of the underlying list decoding algorithm for algebraic geometry codes. The encoding and list decoding algorithms in [
18] that we use run in polynomial time provided that a polynomial amount of pre-processed information about the code is available to the algorithms. Naturally, any subsequent improvements in list decoding algorithms of folded algebraic geometry (and for that matter, folded Reed-Solomon) codes would automatically improve the performance of the above secret sharing schemes.
We remark that the natural idea of reducing share length by using algebraic geometry codes rather than Reed-Solomon codes in secret sharing schemes dates back to a result of Chen and Cramer [
5] and has been extensively studied since (cf. [
9]), especially in the context of arithmetic secure multiparty computation.
It should be pointed out that, as discussed before, the focus of the present work is in showing that a simple modification of the existing Shamir’s secret sharing scheme (i.e., the idea of amending the secret with an AMD tag that was actually proposed in [
8] and shown to provide robustness in the sense of error-detection) essentially makes it optimally robust. This means that
existing systems employing Shamir’s scheme can be easily modified to provide stronger robustness against tampering adversaries, and this can be a very appealing improvement for practitioners that use Shamir’s or related coding-theoretic schemes. In contrast, graph-based constructions such as [
3,
10,
21] pursue a very different approach. Another appealing feature of coding-theoretic constructions such as our construction and Shamir’s original scheme is that they allow an imbalance between the adversarial leakages and corruptions. In particular, for our constructions the adversary can read any
\(\tau \) fraction of the shares and use this information to corrupt any
\(\delta \) (whether including the shares previously read or not) fraction of the shares, and both privacy and robustness can be guaranteed as long as
\(\tau +\delta \) is nontrivially bounded away from 1.
Organization. The rest of the article is organized as follows. We explain the notation in Sect.
1.3. Preliminaries, including the exact notion of secret sharing schemes that we use in this work, are discussed in Sect.
2. Our general construction is presented and analyzed in Sect.
3. We then instantiate the construction using folded Reed-Solomon codes in Sect.
4.1 and folded algebraic geometry codes in Sect.
4.2. Finally, Sect.
4.3 proves optimality of the obtained bounds using a reduction from the wiretap channel problem.