Abstract
Threshold secret sharing allows a dealer to split a secret s into n shares, such that any t shares allow for reconstructing s, but no \(t-1\) shares reveal any information about s. Leakage-resilient secret sharing requires that the secret remains hidden, even when an adversary additionally obtains a limited amount of leakage from every share. Benhamouda et al. (CRYPTO’18) proved that Shamir’s secret sharing scheme is one bit leakage-resilient for reconstruction threshold \(t\ge 0.85n\) and conjectured that the same holds for \(t=c\cdot n\) for any constant \(0\le c\le 1\). Nielsen and Simkin (EUROCRYPT’20) showed that this is the best one can hope for by proving that Shamir’s scheme is not secure against one-bit leakage when \(t=c\cdot n/\log (n)\).
In this work, we strengthen the lower bound of Nielsen and Simkin. We consider noisy leakage-resilience, where a random subset of leakages is replaced by uniformly random noise. We prove a lower bound for Shamir’s secret sharing, similar to that of Nielsen and Simkin, which holds even when a constant fraction of leakages is replaced by random noise. To this end, we first prove a lower bound on the share size of any noisy-leakage-resilient sharing scheme. We then use this lower bound to show that there exist universal constants \(c_1,c_2\), such that for sufficiently large n it holds that Shamir’s secret sharing scheme is not noisy-leakage-resilient for \(t\le c_1\cdot n/\log (n)\), even when a \(c_2\) fraction of leakages are replaced by random noise.
Access provided by Autonomous University of Puebla. Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
Threshold secret sharing was introduced by Shamir [Sha79] and Blakley [Bla79] and allows a dealer to split a secret s into shares \(\textsf{sh}_1, \dots , \textsf{sh}_n\), such that any t shares allow for reconstructing s, but no \(t-1\) shares reveal anything about s at all in the information-theoretic sense. Since its introduction, this primitive in general, and Shamir’s secret sharing scheme in particular, has found countless applications in various fields of cryptography. Naturally, it is important to understand the precise security it provides.
The security definitions for regular threshold secret sharing schemes and variants like robust [RB89] or verifiable secret sharing [CGMA85] all assume that some shares are fully known and some shares are fully hidden from the adversary. As it turns out, these all-or-nothing type of security models do not always precisely reflect the security we want in practice. Real-world implementations of cryptographic primitives are susceptible to different types of side-channel attacks, which may give the adversary limited access to secrets that should ideally be fully hidden from her. Cryptographic primitives have, for example, been successfully attacked through leakages obtained via timing [Koc96] and power consumption [KJJ99] side-channels.
Motivated by the emergence of such side-channel attacks, the security definitions of secret sharing have been strengthened to account for additional leakages from the shares that were previously assumed to be fully hidden. Such schemes require that the secret that is shared remains hidden, when the adversary not only receives \(t-1\) shares, but additionally obtains some limited amount of leakage from all other shares. Leakage-resilient secret sharing schemes have received significant interest and many constructions have been proposed over the past few years [DP07, BGK14, GK18b, GK18a, ADN+19, KMS19, SV19, CKOS21, CKOS22]. Realistically, however, it seems unlikely that Shamir’s secret sharing scheme will be replaced by a leakage-resilient alternative any time soon. Shamir’s scheme is a cornerstone of many cryptographic constructions and has been implemented and deployed as part of many different projects. Replacing a scheme that is so deeply embedded into so many different projects, seems like a insurmountable challenge. For this reason, it is crucially important to understand the leakage-resilience of Shamir’s secret sharing scheme itself.
Benhamouda et al. [BDIR18] studied this question in a setting, where the adversary submits arbitrary leakage functions \(\textsc {Leak}_1, \dots , \textsc {Leak}_n\) and obtains leakages \(\textsc {Leak}_i(\textsf{sh}_i)\) for \(i \in [n]\). The only restriction imposed on the leakage functions is that they are having a bounded output length. The authors show that Shamir’s scheme provides some leakage-resilience, when \(t \ge 0.85 n\) and they conjecture that Shamir’s scheme is leakage-resilient against one bit leakages for any \(t = c\cdot n\), where \(0 \le c \le 1\) is a constant. Subsequently, Nielsen and Simkin [NS20] showed that Shamir’s scheme is not secure against one bit leakages when \(t = c \cdot n/\log (n)\), thereby showing that their conjecture is the best one can hope for.
1.1 Our Contribution
The works of Benhamouda et al. [BDIR18] and Nielsen and Simkin [NS20] assume that the adversary is able to obtain the precise outputs of its leakage functions. In practice, however, side-channel attacks are inherently noisy and there are practical techniques that can amplify this noise [CCD00, CK09, MOP07, CJRR99] to counter potential side-channel attacks. One might hope that it is possible to circumvent the lower bound of Nielsen and Simkin by considering a weaker, but more realistic noisy leakage model, where some random subset of the leakages is replaced by uniformly random noise.
In this work we show that this is not the case. We prove a lower bound similar to that of Nielsen and Simkin for Shamir’s secret sharing scheme, which holds even when a constant fraction of leakages is replaced by random noise. To this end, we first prove a lower bound on the share size of any noisy-leakage-resilient secret sharing scheme. We then use this lower bound to obtain the following theorem:
Theorem 1
(Informal). There exist universal constantsFootnote 1 \(c_1, c_2\), such that for sufficiently large n, it holds that \((c_1\cdot n/\log (n))\)-out-of-n Shamir secret sharing is not leakage-resilient against one bit leakage, even when a \(c_2\) fraction of the leakage function outputs are replaced by random noise.
We note that the constants \(c_1\) and \(c_2\) in our lower bound are not too relevant. The main takeaway of our result is that the reconstruction threshold t must be as large as a function of the number of shares n, i.e. it must hold that \(t \in \Omega (n/\log (n))\), even if we relax the notion of leakage-resilience that we aim for considerably.
To prove this lower bound, we construct a generic adversary \(\mathcal {A}\) that can use the noisy leakage to recover the secret shared value, whenever the shares are too small in size. The main idea of this attack is similar to the one in the proof of [NS20, Theorem 2]. We apply a separate uniformly random leakage function to each share. Given the noisy leakage vector, our adversary \(\mathcal {A}\) iterates over all possible secret values and all possible secret sharings thereof.Footnote 2 Whenever there is a vector of shares that would produce a leakage vector that is consistent enough with the obtained noisy leakage vector, the adversary remembers the corresponding secret value in an initially empty set S. Finally, the adversary hopes that S contains exactly one element in which case she returns that element as her guess for what was the actual secret shared value.
In contrast to the previous lower bound of Nielsen and Simkin, our adversary needs to account for the noise in the leakage vector and thus it needs to add values s to S, even if there was no secret sharing of s that produced a fully consistent vector of leakages. Relaxing the conditions under which values s are added to S needs to be done carefully, since we would like to ensure that we do not add too many elements to the S. In a nutshell, our lower bound shows that the noisy leakage vector and any other leakage vector belonging to the incorrect secret, will differ in many positions. Making this intuition formal and arguing that our adversary is successful with a sufficiently high probability requires a careful analysis, which is the main contribution of this work.
1.2 Other Related Works
The work by Guruswami and Wootters [GW16] demonstrated that some linear secret sharing schemes, such as Shamir’s scheme over certain fields, allow for very communication efficient reconstruction of the secret. More precisely, they show that Shamir’s scheme over fields of characteristic two, allows for recovering a multi-bit secret from only one bit of leakage from each share.
Inspired by these results, Benhamouda et al. [BDIR18] investigate to what extend natural secret sharing schemes offer leakage-resilience. They prove that Shamir’s secret sharing scheme is leakage-resilient against one bit leakages, when the reconstruction thresholds is at least 0.92 times the number of parties. This constant was then improved to 0.8675 [MPSW21], then to 0.85 [BDIR21] and later to 0.78 [MNPCW22].
The currently best known constant is 0.69, which was recently proven by Klein and Komargodski [KK23]. The authors additionally show that whenever the leakage functions are guaranteed to be balanced, i.e. approximately half of the domain gives output 1 and the other half gives output \(-1\), then the constant can be reduced to 0.58. Similarly, whenever the leakage functions are guaranteed to be sufficiently unbalanced, then Shamir’s scheme is leakage resilient as long as the reconstruction threshold is at least 0.01 times the number of parties. This result is the first one that breaks the barrier of 0.5, which was known to be inherent in the proof techniques used in the previous works.
Maji et al. [MNP+21] consider much weaker physical-bit leakages, which only allows for a fixed number of bits to be leaked from the binary representation of each secret share. They prove that Shamir’s secret sharing scheme with random evaluation points is physical-bit leakage resilient if the order of the field is sufficiently large. Adams et al. [AMN+21] consider noisy physical-bit leakage, where each physical-bit leakage is replaced by noise with some fixed probability. They prove a lower bound for the reconstruction threshold of \(\log (\lambda )/\log \log (\lambda )\) for Shamir’s secret sharing scheme, when the size of the field is \(2^\lambda \) and the evaluation points can be chosen adversarially. In [MNPC+22] Maji et al. improve their lower bound to \(\log (\lambda )\). This bound is interesting in the setting where the size of the field is much larger than the number of parties. In the setting we consider, we have \(\lambda \approx \log (n)\), in which case their lower says that the reconstruction threshold needs to be larger than \(\log \log (n)\).
In another work, Maji et al. [MNP+22] consider global leakage functions with bounded output length that can compute arbitrary functions over all shares simultaneously. Generally, this would allow the leakage functions to just reconstruct the secret, which is an attack that cannot be prevented. For this reason, the authors artificially restrict their leakage functions to not depend on some of the random choices made by the secret sharing scheme. For the case of Shamir secret sharing with random evaluation points, the authors show that one obtains some leakage-resilience properties, if the leakage functions are not allowed to depend on the evaluation points.
2 Preliminaries
Notation. We write [n] to denote the set \(\{1,\dots , n\}\). For a set X, we write \(x \leftarrow X\) to denote the process of sampling a uniformly random element x from the set X. For a vector \(v = (v_1, \dots , v_n)\) and a vector \(w = (w_1, \dots , w_t) \in [n]^t\), we define \(v_{w} := (v_{w_1}, \dots , v_{w_t})\). We will sometimes abuse notation and write \(v_{w}\), where w is a set, rather than a vector. In this case the elements can be ordered arbitrarily in the vector. We denote by \(\textsc {Noise}(v, \ell , p)\) the algorithm that takes vector \(v = (v_1, \dots , v_n) \in \left( \{0,1\}^\ell \right) ^n\), \(\ell \in \mathbb {N}\), and \(0 \le p \le 1\) as input and returns a new vector \((\tilde{v}_1, \dots , \tilde{v}_n)\), where for \(i \in [n]\) each \(\tilde{v}_i = v_i\) with probability \(1-p\) and \(\tilde{v}_i \leftarrow \{0,1\}^\ell \) with probability p. That means that \(\textsc {Noise}(v, \ell , 1)\) returns a uniformly random vector and \(\textsc {Noise}(v, \ell , 0)\) returns v.
2.1 Leakage-Resilient Secret Sharing
We define threshold secret sharing schemes similarly to how it was done by Nielsen and Simkin [NS20]. The full reconstruction parameter \(\hat{t}\) defines how many shares are needed to reconstruct all shares of a particular secret sharing. Intuitively, \(\hat{t}\) corresponds to a crude measure of how much entropy the vector of shares contains.
Definition 1
(Threshold Secret Sharing Scheme). A t-out-of-n threshold secret sharing scheme is a pair \((\textsc {Share}, \textsc {Rec})\) of efficient algorithms. The randomized sharing algorithm \(\textsc {Share}: \{0,1\}^k \rightarrow \left( \{0,1\}^p\right) ^n\) takes a k-bit secret as input and returns a vector of n secret shares, each p-bits long. The deterministic reconstruction algorithm \(\textsc {Rec}: \left( \{0,1\}^p\right) ^t \rightarrow \{0,1\}^k\) takes t of the shares as input and returns a k-bit string. We require a secret sharing scheme to satisfy the following properties:
-
Perfect Correctness: For \(t, n \in \mathbb {N}\) with \(t \le n\), any \(T \subseteq [n]\) with \(|T| = t\) and any \(x \in \{0,1\}^k\), it holds that
$$ \Pr [\textsc {Rec}(\textsc {Share}(x)_T) = x] =1, $$where the probability is taken over the random coins of \(\textsc {Share}\).
-
Full Reconstruction: \((\textsc {Share}, \textsc {Rec})\) has \(\hat{t}\)-full-reconstruction, if for any x, the vector \(\textsc {Share}(x)\) can be computed from any subvector \(\textsc {Share}(x)_T\) with \(|T| \ge \hat{t}\).
We assume for simplicity that all shares are of the same size p but the proof of our lower bound can easily be adapted to schemes with shares of different sizes.
Definition 2
(Leakage Functions). Let \((\textsc {Share}, \textsc {Rec})\) with \(\textsc {Share}: \{0,1\}^{k} \rightarrow \times _{i=1}^n \{0,1\}^{p}\) be a secret sharing scheme and for \(i \in [n]\), let \(\textsc {Leak}_i :\{0,1\}^{p} \rightarrow \{0,1\}^\ell \). We call \(\textsc {Leak}= \left( \textsc {Leak}_1, \dots , \textsc {Leak}_n\right) \) an \(\ell \)-leakage function for \((\textsc {Share}, \textsc {Rec})\). We define \(\textsc {Leak}(\textsf{sh}_1, \dots , \textsf{sh}_n) :=\left( \textsc {Leak}_1(\textsf{sh}_1), \dots , \textsc {Leak}_n(\textsf{sh}_n) \right) \).
We now define the privacy notion, which is a direct extension of the (noiseless) weak one-way local leakage resilience notion of Nielsen and Simkin [NS20, Definition 5], for which we will prove our lower bounds. The adversary \(\mathcal {A}\) obtains a noisy leakage vector and it knows the probability \(\eta \) with which each leakage is replaced by noise. She does, however, not know which leakage outputs are replaced by random noise. Our privacy notion requires that \(\mathcal {A}\) is not able to learn the secret with probability greater than 1/2.
Definition 3
(Weak One-Way Noisy Local Leakage-Resilience). We say a secret sharing scheme \((\textsc {Share}, \textsc {Rec})\) is \((\ell , \eta )\)-weakly one-way noisy local leakage-resilient \(((\ell , \eta )-\mathsf {WOW\text {-}NLLR})\), if for any \(\ell \)-leakage function \(\textsc {Leak}\) and any adversary \(\mathcal {A}\), it holds that
where the probability is taken over the random coins of \(\textsc {Share}\), \(\textsc {Noise}\) and \(\mathcal {A}\).
We note that this is a very weak privacy notion. We only require a form of one-wayness that prevents the adversary from fully recovering the secret shared value and we only require the adversary to be successful with a probability less than 1/2. Notably, this notion is even weaker than a standard indistinguishability type of notion. Since we are proving a lower bound, working with a weaker privacy notion only strengthens our lower bounds.
3 Lower Bound
In this section we prove our lower bound on the share size of any threshold secret sharing scheme that satisfies \((\ell , \eta )-\mathsf {WOW\text {-}NLLR}\).
Theorem 2
Let \(\mathcal {S}= (\textsc {Share}, \textsc {Rec})\) be a t-out-of-n secret sharing scheme with \(\hat{t}\)-full-reconstruction and shares consisting of p bits each. Let \(\ell \ge 1\) and let \(0 < \eta \le (n-t)/4n\). If \(\mathcal {S}\) is \((\ell , \eta )-\mathsf {WOW\text {-}NLLR}\), then
Remark 1
We note that the theorem requires \(\eta \le (n-t)/4n\). In principle, our lower bound could be tightened to only require, for instance, \(\eta \le (n-t)/1.1n\) by replacing a single Markov inequality in the proofs with a stronger tail bound. We opted for clarity instead of optimizing the constants in our exposition. Next, we note that \(\eta \le (n-t)/n\) is a sensible restriction. If \(\eta > (n-t)/n\) would hold, then with high probability \(n-t+1\) leakages would be replaced by random noise. In this case, our adversary could not hope to recover the secret, even if the leakage functions would leak the full shares.
Remark 2
It can be interesting to compare our lower bound to the one of Nielsen and Simkin [NS20]. Their work shows that any secret sharing scheme that satisfies \((\ell , 0)-\mathsf {WOW\text {-}NLLR}\), needs to satisfy
As \(\eta \) approaches 0, our work effectively proves the same lower bound.
Proof
(of Theorem 2). Towards proving the theorem statement, we provide a generic attacker that successfully wins the \((\ell , \eta )-\mathsf {WOW\text {-}NLLR}\) game against any secret sharing scheme that does not satisfy the constraints on the share size p that are stated in the theorem statement. This adversary works as follows. It picks \(\textsc {Leak}= (\textsc {Leak}_1, \dots , \textsc {Leak}_n)\) by picking each \(\textsc {Leak}_i : \{0,1\}^{p} \rightarrow \{0,1\}^\ell \) for \(i \in [n]\) uniformly and independently at random. The challenger picks a uniformly random secret s and computes \((\textsf{sh}_1, \dots , \textsf{sh}_n) \leftarrow \textsc {Share}(s)\). Adversary \(\mathcal {A}\) submits the \(\ell \)-leakage function \(\textsc {Leak}\) to the challenger, who responds with \((b_1, \dots , b_n)\), where each \(b_i\) is either \(\textsc {Leak}_i(\textsf{sh}_i)\) with probability \(1-\eta \) or a uniformly random value from \(\{0,1\}^\ell \) with probability \(\eta \). Let N be the number of components that were replaced by uniformly random noise values by the challenger and let \(S = \emptyset \). The adversary now iterates over all possible secrets \(s'\) and random coins \(r'\) to compute
and
If \(|{\{i \in [n]\mid b'_i = b_i\}}|\ge n(1- 4\eta )\) for some \(r'\), then add \(s'\) to S. Finally, once \(\mathcal {A}\) iterated over all possible secret sharings, if \(|{S}| = 1\), then it outputs that one element in S and in any other case it returns \(\bot \).
Let us now analyze the success probability of \(\mathcal {A}\). We observe that if the challenger replaced at most \(4n\eta \) coordinates by uniformly random noise, i.e. if \(N \le 4n\eta \), then \(s \in S\). Since in expectation N is equal to \(n\eta \), it holds by Markov’s inequality that
Our adversary is successful, if and only if s is the only element in S. Let \(E_{s'}\) be the event that \(s' \in S\). Then
To prove the theorem statement, we need to show that the adversary’s attack is successful with a sufficiently high probability, i.e. we need to show that \(\Pr \left[ S = \{s\}\right] \ge 1/2\) and thus by the above it suffices to show that
By the union boundFootnote 3 we have that
Let us now fix an arbitrary \(s' \ne s\), fix random coins \(r'\), and let \((\textsf{sh}'_1, \dots , \textsf{sh}'_n) \leftarrow \textsc {Share}(s' ; r')\). Let \(E_{s', r'}\) be the event that the adversary includes \(s'\) into S based on the leakage from \((\textsf{sh}'_1, \dots , \textsf{sh}'_n)\), i.e. the event that \(|{\{i \in [n]\mid b'_i = b_i\}}| \ge n(1- 4\eta )\), where \(b'_i \leftarrow \textsc {Leak}_i(\textsf{sh}'_i)\). Let us bound the probability of \(E_{s', r'}\) conditioned on \(N \le 4n\eta \). From the perfect correctness of the secret sharing scheme and since \(s \ne s'\), we know that there exists a set of indices \(I \subseteq [n]\) with \(|{I}| \ge n-t+1\), such that for all \(i \in I\), it holds that \(\textsf{sh}_i \ne \textsf{sh}'_i\). For each \(i \in I\), there are two cases. Either the leakage \(b_i\) is the real leakage or it is a uniformly random element from \(\{0,1\}^\ell \). In either case, it holds that \(b_i = b'_i\) with probability \(2^{-\ell }\), since the corresponding shares are different and the leakage function \(\textsc {Leak}_i\) is chosen uniformly random and independently of its inputs.
Let \(\mathcal {T}\) be the set of subsets of I of size \(n-t+1-4n\eta \). Note that \(n-t+1-4n\eta > 0\), since \(\eta \le (n-t)/4n\) by assumption. For \(T \in \mathcal {T}\), let \(E_{s', r', T}\) be the event that the noisy leakage vector \((b_1, \dots , b_n)\) and the noiseless vector \((b'_1, \dots , b'_n)\) agree on all coordinates in T. Note that by the union bound
To see this, observe that even if \((\textsf{sh}_1, \dots , \textsf{sh}_n)\) and \((\textsf{sh}'_1, \dots , \textsf{sh}'_n)\) agree on \(t-1\) coordinates, then there must still exist at least \(n-t+1-4n\eta \) distinct indices \(i \in I\) for which it holds that \(b_i = b'_i\) to satisfy the condition \(|{\{j \in [n]\mid b'_j = b_j\}}| \ge n(1- 4\eta )\). It is easy to see that
and thus, it holds that
At this point, recall that each share is p-bits long and that \(\hat{t}\) is the full reconstruction threshold, i.e. that any \(\hat{t}\) shares are enough to uniquely determine all remaining shares of a specific secret sharing. Thus there are at most \(2^{p\hat{t}}\) different secret sharings in total and therefore
As discussed before, the adversary we constructed is successful, if
From here it follows that
must hold, if the secret sharing scheme wants to prevent the attack described above. \(\square \)
The bound in Theorem 2 can be a little unwieldy and for this reason we also provide a slightly weaker, but simpler to state lower bound in the following corollary.
Corollary 3
Let \(t \le n/2\). Let \(\mathcal {S}= (\textsc {Share}, \textsc {Rec})\) be a t-out-of-n secret sharing scheme with \(\hat{t}\)-full-reconstruction and shares consisting of p bits each. Let \(\ell \ge 1\) and let \(0 < \eta \le 1/64\). If \(\mathcal {S}\) is \((\ell , \eta )-\mathsf {WOW\text {-}NLLR}\), then
Proof
For Theorem 2 to be applicable, it must hold that \(0 < \eta \le (n-t)/4n\), which is always satisfied, when \(0 \le \eta \le 1/64\), since \(t \le n/2\). Furthermore, it holds that
From Theorem 2, we know that it must hold that
Thus it must at least hold that
\(\square \)
4 Leakage-Resilience of Shamir’s Secret Sharing
In this section we apply our result to Shamir’s secret sharing scheme.
4.1 Shamir’s Secret Sharing Scheme
In t-out-of-n Shamir secret sharing [Sha79], the secrets are elements of a field \(\mathbb {F}_q\) for some prime q, which is chosen as the smallest prime larger than n. To distribute a secret s, the dealer picks a uniformly random polynomial f of degree \(t-1\) from \(\mathbb {F}_q[X]\) and defines \(\textsf{sh}_i = f(i)\) for \(i \in [n]\). Reconstruction of the secret from a subset of t shares is performed via polynomial interpolation, as any polynomial of degree \(t-1\) is uniquely defined by t evaluation points.
4.2 Noisy Leakage-Resilience
Benhamouda et al. [BDIR18] conjecture that Shamir’s scheme is leakage-resilient against one-bit leakage for any \(t=c\cdot n\), where \(0\le c\le 1\) is a constant. Nielsen and Simkin [NS20] showed that this is the best one can hope for by proving that the scheme is not secure against one-bit leakage when \(t=cn/\log (n)\). In Theorem 4 we show that this lower bound holds even if a constant fraction of leakages is replaced by noise.
Theorem 4
There exist universal constants \(c_1, c_2\), such that for sufficiently large n, it holds that \((c_1\cdot n/\log (n))\)-out-of-n Shamir secret sharing is not \((1, c_2)-\mathsf {WOW\text {-}NLLR}\).
Remark 3
We note again that the precise values of the constants \(c_1\) and \(c_2\) are not too important. As we will see below, setting them to \(c_1<1/3\) and \(c_2=1/64\) suffices. There are multiple ways in which one could optimize these values. As already noted in Remark 1, one could use a tighter tail bound in the proof of Theorem 4. Another way could be to strengthen the notion of \(\mathsf {WOW\text {-}NLLR}\), i.e. slightly weaken the lower bound, to require the adversary to win with some probability smaller than half. These changes would, however, not change the main takeaway of our result, which is that Shamir secret sharing can not be leakage-resilient, unless \(t \in \Omega (n/\log (n))\).
Proof
Let \(c_1 < 1/3\) be arbitrary but fixed and let \(c_2 = 1/64\). By Corollary 3, we know that
has to hold for the secret sharing scheme to be \((1, c_2)-\mathsf {WOW\text {-}NLLR}\). We note that the full reconstruction threshold \(\hat{t} = t\) for Shamir secret sharing, since any t shares allow interpolating any other share. Now plugging in the concrete parameters, we get that
has to hold.
Let q be the first prime larger than n and note that \(p = \log (q)\). By the Bertrand-Chebyshev Theorem, we know that \(n < q \le 2n\) and thus it must hold that
which is clearly not true once n is large enough. \(\square \)
Conclusion. In this work, we strengthened the lower bounds on the share size of leakage-resilient secret sharing schemes of Nielsen and Simkin [NS20] by showing that similar bounds hold, even if we considerably weaken the security notion we aim for. We show that Shamir secret sharing is not noisy leakage-resilient, if \(t \le c_1\cdot n/\log (n)\), where \(c_1\) and \(c_2\) are constants, where t is the reconstruction threshold and n is the number of shares. We leave the reader with an interesting open question. Our lower bound crucially relies on an adversary running in exponential time in n. A natural question to consider is whether one can either improve the running time of the adversary to make the attacks more practical or whether one can prove a form of computational leakage-resilience for Shamir secret sharing under an appropriate computational assumption.
Notes
- 1.
Concretely, we show the statement for \(c_1 < 1/3\) and \(c_2 = 1/64\), but a more careful analysis can allow for better constants, if desired.
- 2.
We are only concerned with information-theoretic security in which case the adversary is unbounded.
- 3.
The union bound also holds for conditional probabilities, meaning that \(\Pr [A \vee B \mid C] = \Pr [(A \vee B) \wedge C]/\Pr [C] \le (\Pr [A \wedge C] + \Pr [B \wedge C])/\Pr [C] = \Pr [A \mid C] + \Pr [B \mid C]\).
References
Aggarwal, D., et al.: Stronger leakage-resilient and non-malleable secret sharing schemes for general access structures. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 510–539. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_18
Adams, D.Q., et al.: Lower bounds for leakage-resilient secret-sharing schemes against probing attacks. In: 2021 IEEE International Symposium on Information Theory (ISIT), pp. 976–981. IEEE (2021)
Benhamouda, F., Degwekar, A., Ishai, Y., Rabin, T.: On the local leakage resilience of linear secret sharing schemes. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 531–561. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_18
Benhamouda, F., Degwekar, A., Ishai, Y., Rabin, T.: On the local leakage resilience of linear secret sharing schemes. J. Cryptol. 34(2), 10 (2021)
Boyle, E., Goldwasser, S., Kalai, Y.T.: Leakage-resilient coin tossing. Distrib. Comput. 27, 147–164 (2014)
Blakley, G.R.: Safeguarding cryptographic keys. In: Proceedings of AFIPS 1979 National Computer Conference, vol. 48, pp. 313–317 (1979)
Clavier, C., Coron, J.-S., Dabbous, N.: Differential power analysis in the presence of hardware countermeasures. In: Koç, Ç.K., Paar, C. (eds.) CHES 2000. LNCS, vol. 1965, pp. 252–263. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44499-8_20
Chor, B., Goldwasser, S., Micali, S., Awerbuch, B.: Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract). In: 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, 21–23 October 1985, pp. 383–395. IEEE Computer Society Press (1985)
Chari, S., Jutla, C.S., Rao, J.R., Rohatgi, P.: Towards sound approaches to counteract power-analysis attacks. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 398–412. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_26
Coron, J.-S., Kizhvatov, I.: An efficient method for random delay generation in embedded software. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 156–170. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04138-9_12
Chandran, N., Kanukurthi, B., Obbattu, S.L.B., Sekar, S.: Adaptive extractors and their application to leakage resilient secret sharing. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 595–624. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_20
Chandran, N., Kanukurthi, B., Obbattu, S.L.B., Sekar, S.: Short leakage resilient and non-malleable secret sharing schemes. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13507, pp. 178–207. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-15802-5_7
Dziembowski, S., Pietrzak, K.: Intrusion-resilient secret sharing. In: 48th Annual Symposium on Foundations of Computer Science, Providence, RI, USA, 20–23 October 2007, pp. 227–237. IEEE Computer Society Press (2007)
Goyal, V., Kumar, A.: Non-malleable secret sharing. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) 50th Annual ACM Symposium on Theory of Computing, Los Angeles, CA, USA, 25–29 June 2018, pp. 685–698. ACM Press (2018)
Goyal, V., Kumar, A.: Non-malleable secret sharing for general access structures. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 501–530. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_17
Guruswami, V., Wootters, M.: Repairing reed-solomon codes. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2016, New York, NY, USA, pp. 216–226. Association for Computing Machinery (2016)
Kocher, P.C., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_25
Klein, O., Komargodski, I.: New bounds on the local leakage resilience of shamir’s secret sharing scheme. Cryptology ePrint Archive, Paper 2023/805 (2023). https://www.eprint.iacr.org/2023/805
Kumar, A., Meka, R., Sahai, A.: Leakage-resilient secret sharing against colluding parties. In: Zuckerman, D. (ed.) 60th Annual Symposium on Foundations of Computer Science, Baltimore, MD, USA, 9–12 November 2019, pp. 636–660. IEEE Computer Society Press (2019)
Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_9
Maji, H.K., Nguyen, H.H., Paskin-Cherniavsky, A., Suad, T., Wang, M.: Leakage-resilience of the shamir secret-sharing scheme against physical-bit leakages. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 344–374. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_12
Maji, H.K., et al.: Leakage-resilient linear secret-sharing against arbitrary bounded-size leakage family. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC 2022. LNCS, vol. 13747, pp. 355–383. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-22318-1_13
Maji, H.K., et al.: Tight estimate of the local leakage resilience of the additive secret-sharing scheme & its consequences. In: Dachman-Soled, D. (ed.) 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol. 230, pp. 16:1–16:19, Dagstuhl, Germany. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
Maji, H.K., Nguyen, H.H., Paskin-Cherniavsky, A., Wang, M.: Improved bound on the local leakage-resilience of Shamir’s secret sharing. In: 2022 IEEE International Symposium on Information Theory (ISIT), pp. 2678–2683. IEEE (2022)
Mangard, S., Oswald, E., Popp, T.: Power Analysis Attacks: Revealing the Secrets of Smart Cards. Springer, New York (2007). https://doi.org/10.1007/978-0-387-38162-6
Maji, H.K., Paskin-Cherniavsky, A., Suad, T., Wang, M.: Constructing locally leakage-resilient linear secret-sharing schemes. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 779–808. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_26
Nielsen, J.B., Simkin, M.: Lower bounds for leakage-resilient secret sharing. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 556–577. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_20
Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In: 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, 15–17 May 1989, pp. 73–85. ACM Press (1989)
Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)
Srinivasan, A., Vasudevan, P.N.: Leakage resilient secret sharing and applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 480–509. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_17
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Hoffmann, C., Simkin, M. (2023). Stronger Lower Bounds for Leakage-Resilient Secret Sharing. In: Aly, A., Tibouchi, M. (eds) Progress in Cryptology – LATINCRYPT 2023. LATINCRYPT 2023. Lecture Notes in Computer Science, vol 14168. Springer, Cham. https://doi.org/10.1007/978-3-031-44469-2_11
Download citation
DOI: https://doi.org/10.1007/978-3-031-44469-2_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-44468-5
Online ISBN: 978-3-031-44469-2
eBook Packages: Computer ScienceComputer Science (R0)