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

$$ \Pr \left[ \begin{aligned} x \leftarrow \{0,1\}^k \\ (\textsf{sh}_1, \dots , \textsf{sh}_n) \leftarrow \textsc {Share}(x) \\ (\textsc {Leak}_1, \dots , \textsc {Leak}_n) \leftarrow \mathcal {A}(n)\\ (\tilde{b}_1, \dots , \tilde{b}_n) \leftarrow \textsc {Leak}(\textsf{sh}_1, \dots , \textsf{sh}_n) \\ (b_1, \dots , b_n) \leftarrow \textsc {Noise}((\tilde{b}_1, \dots , \tilde{b}_n), \ell , \eta ) \\ x' \leftarrow \mathcal {A}(b_1, \dots , b_n) \end{aligned} : x' = x \right] \le \frac{1}{2}, $$

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

$$ p \ge \frac{\ell (n-t)}{\hat{t}} - \frac{4n\eta (\ell + \log (1/\eta ))+1}{\hat{t} }. $$

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

$$ p \ge \frac{\ell (n-t)}{\hat{t}}. $$

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

$$ (\textsf{sh}'_1, \dots , \textsf{sh}'_n) \leftarrow \textsc {Share}(s' ; r') $$

and

$$ (b'_1, \dots , b'_n) \leftarrow \textsc {Leak}(\textsf{sh}'_1, \dots , \textsf{sh}'_n). $$

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

$$\begin{aligned} \Pr [s\in S] =&\Pr [s\in S \mid N \le 4n\eta ] \cdot \Pr [N \le 4n\eta ]\\ +&\Pr [s\in S \mid N> 4n\eta ] \cdot \Pr [N> 4n\eta ] \\ =&\Pr [N \le 4n\eta ] + \Pr [s\in S \mid N> 4n\eta ] \cdot \Pr [N > 4n\eta ] \\ \ge&\Pr [N \le 4n\eta ] \ge 3/4. \end{aligned}$$

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

$$\begin{aligned} \Pr \left[ S = \{s\}\right] = \Pr \left[ \left( \bigwedge _{s' \ne s} \lnot E_{s'}\right) \wedge E_s \right] \ge&\Pr \left[ \left( \bigwedge _{s' \ne s} \lnot E_{s'}\right) \wedge N \le 4n\eta \right] \\ \ge&\Pr \left[ \left( \bigwedge _{s' \ne s} \lnot E_{s'}\right) \mid N \le 4n\eta \right] \cdot 3/4 \\ =&\left( 1 - \Pr \left[ \bigvee _{s' \ne s} E_{s'} \mid N \le 4n\eta \right] \right) \cdot 3/4. \end{aligned}$$

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

$$ \Pr \left[ \bigvee _{s' \ne s} E_{s'} \mid N \le 4n\eta \right] \le 1/3. $$

By the union boundFootnote 3 we have that

$$ \Pr \left[ \bigvee _{s' \ne s} E_{s'} \mid N \le 4n\eta \right] \le \sum _{s' \ne s} \Pr \left[ E_{s'} \mid N \le 4n\eta \right] . $$

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

$$ \Pr \left[ E_{s', r'} \mid N \le 4n\eta \right] \le \sum _{T \in \mathcal {T}} \Pr \left[ E_{s', r', T} \mid N \le 4n\eta \right] . $$

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

$$ \Pr \left[ E_{s', r', T}\mid N \le 4n\eta \right] \le 2^{-(n-t+1-4n\eta )\ell } $$

and thus, it holds that

$$\begin{aligned} \Pr \left[ E_{s', r'}\mid N \le 4n\eta \right] \le&|{\mathcal {T}}| \cdot 2^{-(n-t+1-4n\eta )\ell }\\ =&\left( {\begin{array}{c}n-t+1\\ n-t+1-4n\eta \end{array}}\right) \cdot 2^{-(n-t+1-4n\eta )\ell } \\ =&\left( {\begin{array}{c}n-t+1\\ 4n\eta \end{array}}\right) \cdot 2^{-(n-t+1-4n\eta )\ell } \\ \le&\left( \frac{e(n-t+1)}{4n\eta }\right) ^{4n\eta }\cdot 2^{-(n-t+1-4n\eta )\ell }\\ \le&\left( \frac{n-t+1}{n\eta }\right) ^{4n\eta }\cdot 2^{-(n-t+1-4n\eta )\ell }\\ \le&\left( \frac{1}{\eta }\right) ^{4n\eta }\cdot 2^{-(n-t+1-4n\eta )\ell } \end{aligned}$$

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

$$ \sum _{s' \ne s} \Pr \left[ E_{s'} \mid N \le 4n\eta \right] \le \left( \frac{1}{\eta }\right) ^{4n\eta }\cdot 2^{p \hat{t}-(n-t+1-4n\eta )\ell }. $$

As discussed before, the adversary we constructed is successful, if

$$\begin{aligned}&\left( \frac{1}{\eta }\right) ^{4n\eta }\cdot 2^{p \hat{t}-(n-t+1-4n\eta )\ell } \le 1/3 \\ \iff&\log (1/\eta )4n\eta + p \hat{t}-(n-t+1-4n\eta )\ell \le -\log 3 \\ \iff&p \hat{t} \le (n-t+1-4n\eta )\ell - \log (1/\eta )4n\eta - \log 3 \\ \iff&p \hat{t} \le (n-t+1)\ell - \log 3 - 4n\eta (\ell + \log (1/\eta )). \end{aligned}$$

From here it follows that

$$ p \ge \frac{(n-t)\ell -1 - 4n\eta (\ell + \log (1/\eta ))}{\hat{t} } $$

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

$$ p \ge \frac{\ell (n-2t)}{2\hat{t}} -1. $$

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

$$\begin{aligned} \frac{4n\eta (\ell + \log (1/\eta ))+1}{\hat{t} } \le&\frac{n \ell }{16\hat{t}} + \frac{4n\eta \log (1/\eta )}{\hat{t}} + 1\\ \le&\frac{n \ell }{16\hat{t}} + \frac{3n}{8\hat{t}} + 1 \le \frac{7n\ell }{16\hat{t}} + 1 \le \frac{n\ell }{2\hat{t}} + 1 \end{aligned}$$

From Theorem 2, we know that it must hold that

$$ p \ge \frac{\ell (n-t)}{\hat{t}} - \frac{4n\eta (\ell + \log (1/\eta ))+1}{\hat{t} }. $$

Thus it must at least hold that

$$\begin{aligned}&p \ge \frac{\ell (n-t)}{\hat{t}} - \frac{n\ell }{2\hat{t} } - 1\\ \iff&p \ge \frac{\ell (n-2t)}{2\hat{t}} -1. \end{aligned}$$

   \(\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

$$ p \ge \frac{n-2t}{2\hat{t}} -1 $$

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

$$\begin{aligned}&p \ge \frac{n-2c_1n/\log (n)}{2c_1n/\log (n)} - 1\\ \iff&p \ge \frac{\log (n)}{2c_1} - 2 \\ \iff&p \ge \frac{3\log (n)}{2} - 2 \end{aligned}$$

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

$$\begin{aligned}&\log (2n) \ge \frac{3\log (n)}{2} - 2 \\ \iff&4 \ge 3 \log (n) - 2\log (2n) \\ \iff&4 \ge \log \left( \frac{n^3}{4n^2}\right) , \end{aligned}$$

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.