Leakage-Resilience of the Shamir Secret-Sharing Scheme Against Physical-Bit Leakages

Abstract

Efficient Reed-Solomon code reconstruction algorithms, for example, by Guruswami and Wootters (STOC–2016), translate into local leakage attacks on Shamir secret-sharing schemes over characteristic-2 fields. However, Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO–2018) showed that the Shamir secret sharing scheme over prime-fields is leakage resilient to one-bit local leakage if the reconstruction threshold is roughly 0.87 times the total number of parties. In several application scenarios, like secure multi-party multiplication, the reconstruction threshold must be at most half the number of parties. Furthermore, the number of leakage bits that the Shamir secret sharing scheme is resilient to is also unclear.

Towards this objective, we study the Shamir secret-sharing scheme’s leakage-resilience over a prime-field F. The parties’ secret-shares, which are elements in the finite field F, are naturally represented as $\lambda$-bit binary strings representing the elements $\{0,1,\dotsc ,p-1\}$. In our leakage model, the adversary can independently probe m bit-locations from each secret share. The inspiration for considering this leakage model stems from the impact that the study of oblivious transfer combiners had on general correlation extraction algorithms, and the significant influence of protecting circuits from probing attacks has on leakage-resilient secure computation.

Consider arbitrary reconstruction threshold $k\geqslant 2$, physical bit-leakage parameter $m\geqslant 1$, and the number of parties $n\geqslant 1$. We prove that Shamir’s secret-sharing scheme with random evaluation places is leakage-resilient with high probability when the order of the field F is sufficiently large; ignoring polylogarithmic factors, one needs to ensure that $\log \left|F \right| \geqslant n/k$. Our result, excluding polylogarithmic factors, states that Shamir’s scheme is secure as long as the total amount of leakage $m\cdot n$ is less than the entropy $k\cdot \lambda$ introduced by the Shamir secret-sharing scheme. Note that our result holds even for small constant values of the reconstruction threshold k, which is essential to several application scenarios.

To complement this positive result, we present a physical-bit leakage attack for $m=1$ physical bit-leakage from $n=k$ secret shares and any prime-field F satisfying $\left|F \right|=1\mod k$. In particular, there are (roughly) $\left|F \right|^{n-k+1}$ such vulnerable choices for the n-tuple of evaluation places. We lower-bound the advantage of this attack for small values of the reconstruction threshold, like $k=2$ and $k=3$, and any $\left|F \right|=1\mod k$. In general, we present a formula calculating our attack’s advantage for every k as $\left|F \right|\rightarrow \infty .$

Technically, our positive result relies on Fourier analysis, analytic properties of proper rank-r generalized arithmetic progressions, and Bézout ’s theorem to bound the number of solutions to an equation over finite fields. The analysis of our attack relies on determining the “discrepancy” of the Irwin-Hall distribution. A probability distribution’s discrepancy is a new property of distributions that our work introduces, which is of potential independent interest.

H. K. Maji, H. H. Nguyen and M. Wang—The research effort is supported in part by an NSF CRII Award CNS–1566499, an NSF SMALL Award CNS–1618822, the IARPA HECTOR project, MITRE Innovation Program Academic Cybersecurity Research Awards (2019–2020, 2020–2021), a Purdue Research Foundation (PRF) Award, and The Center for Science of Information, an NSF Science and Technology Center, Cooperative Agreement CCF–0939370.

A. Paskin-Cherniavsky and T. Suad—Research supported by the Ariel Cyber Innovation Center in conjunction with the Israel National Cyber directorate in the Prime Minister’s Office.

1 Introduction

In the presence of an increasing number of side-channel attacks on cryptographic protocols, theoretical cryptography research has been revisiting its implicit assumptions in modeling secure cryptographic protocols. For example, results in reconstructing Reed-Solomon codes [11, 15, 16] imply that leaking even $(m=1)$ bit from the secret shares of Shamir’s secret-sharing scheme over characteristic-2 finite field F renders this secret sharing scheme insecure. That is, there exist two secrets $s^{\left( 0\right) },s^{\left( 1\right) } \in F$ that an adversary can distinguish by leaking only $(m=1)$-bit local leakage from every secret share. We emphasize that in locally leakage-resilient secret-sharing schemes,¹ the entire secret’s reconstruction is not necessary to qualify as a successful attack. It suffices to achieve a non-negligible advantage in distinguishing any two secrets $s^{\left( 0\right) },s^{\left( 1\right) } \in F$ of adversary’s choice. Since secret-sharing schemes (typically, packed [13] Massey secret-sharing schemes [35] corresponding to linear error-correcting codes with “good” properties) are fundamental cryptographic primitives underlying nearly all of conceivable cryptography, such innovative side-channel attacks threaten the security of most cryptographic protocols.

The recent ground-breaking work of Benhamouda, Degwekar, Ishai, and Rabin [3] identified several scenarios where Shamir’s secret-sharing scheme and the additive secret-sharing scheme are resilient to such local leakage attacks;² thus, laying to rest the devastating possibility of side-channel attacks breaking all secret-sharing schemes. Recently, [37] propose even more sophisticated local leakage attacks on secret-sharing schemes. Since the work of Benhamouda et al.  [3], several works [1, 2, 6, 9, 22, 29, 34, 41] have introduced transformations to convert existing secret-sharing schemes into leakage-resilient versions. It seems insurmountable to replace every deployed secret-sharing scheme with its leakage-resilient version. Furthermore, the leakage-resilient versions of these secret-sharing schemes introduce encoding overheads that noticeably reduce these secret-sharing schemes’ information-rate,³ adversely affecting the applications’ efficiency. Towards the objective of retaining the efficiency of existing secret-sharing schemes with minimal changes, other works [7, 21, 30, 33] analyze the resilience of existing secret-sharing schemes or ensembles of secret-sharing schemes with good properties (for example, packed Massey secret-sharing schemes corresponding to (nearly) maximum distance separable linear error-correcting codes) that are already locally leakage-resilient. Currently, our understanding of the local leakage-resilience of existing secret-sharing schemes typically used in cryptography is still in a nascent state. The exact loss in the achievable parameters and information-rate to additionally ensure local leakage-resilience is even less clear. These losses in the feasible parameter regions and information-rate even render secret-sharing schemes unusable for various application scenarios.

For example, Benhamouda et al.  [3] proved that if Shamir’s secret-sharing scheme, one of the most widely used secret-sharing schemes, has a reconstruction threshold $k\geqslant 0.867n$, where n is the total number of parties, then it is leakage-resilient to $(m=1)$-bit local leakage. Observe that using a large reconstruction threshold k introduces inefficiencies, which may not be necessary for various applications. Additionally, an even more concerning fact is that some cryptographic constructions crucially rely on the reconstruction threshold being low. For example, the secure computation of the multiplication of two (already secret-shared) secrets requires the reconstruction threshold $k<n/2$ even against honest-but-curious parties.

Summary of Our Work: Problem Statement and Results. Our work contributes to this research thrust on characterizing the local leakage-resilience of secret-sharing schemes. As a stepping-stone, our work considers the scenario where each party stores their secret-share in its natural $\lambda$-bit binary representation, and the adversary may (independently) probe arbitrary m physical-bits from each secret-share. The particular choice of the physical-bit leakage draws inspiration from, for instance, the crucial role of the studies on oblivious transfer combiners [8, 19, 20, 25, 36] in furthering the state-of-the-art of general correlation extractors [4, 5, 24], and the techniques in protecting circuits against probing attacks [12, 26, 27] impacting the study of leakage-resilient secure computation (refer to the excellent recent survey [28]).

We present both feasibility and hardness of computation results. Roughly, our results prove that Shamir’s secret-sharing scheme with n random evaluation places, for any reconstruction threshold $k\geqslant 2$, is locally leakage-resilient. The adversary can leak m physical-bits from each secret-share if the total amount of leakage $m\cdot n$ is less than the total entropy $k\cdot \lambda$ in the secret-sharing scheme, except with an exponentially small probability in $\lambda$. To complement this result, we also present new local physical-bit leakage attacks demonstrating several sets of bad evaluation places where Shamir’s secret-sharing scheme is not leakage-resilient even when $m=1$ and $n=k$. Technically, our positive result’s analysis proceeds by discrete Fourier analysis relying on the analytical properties of exponential sums involving rank-r generalized arithmetic progressions, and Bézout ’s theorem to upper-bound the number of solutions to a system of equations over finite fields. On the other hand, our attack’s analysis is equivalent to the “discrepancy” of the Irwin-Hall distribution [18, 23], a new mathematical property of probability distributions that we introduce.

1.1 Our Contribution

This section, first, introduces some informal notations to facilitate the introduction of our results and discussion on them. Let $\lambda$ represent the security parameter. Consider a prime-field F of order p such that $2^{\lambda -1}\leqslant p< 2^\lambda$. That is, every element in the finite field (when equivalently interpreted as elements of the set $\{0,1,\dotsc ,p-1\}$) has a $\lambda$-bit binary representation. The parameter $k\in \mathbb {N}$ represents the reconstruction threshold, and $n\in \mathbb {N}$ represents the total number of parties.

Shamir Secret-Sharing Scheme. Suppose the secret is $s\in F$, and the tuple of distinct evaluation places is , such that $i\ne j$ implies $X_i\ne X_j$.⁴ Shamir’s secret-sharing scheme with threshold $k\in \mathbb {N}$, represented by $\mathsf{ShamirSS} (n,k,\vec X)$, picks a random secret-sharing polynomial $P(X)\in F[X]/X^k$ conditioned on the fact that $P(0)=s$. The secret-shares for parties $1,2,\dotsc ,n$ are $s_1=P(X_1), s_2=P(X_2),\dotsc , s_n=P(X_n)$, respectively. Observe that, in a Shamir secret-sharing scheme, it is implicit that the number of parties satisfies $n<p$.

Physical Bit-Leakage. Our work represents all the secret shares $s_1,\dotsc ,s_n\in F$ with the parties as $\lambda$-bit binary representation. An m-bit local physical-bit leakage function specifies probing locations such that $\ell _{i,j}\in \{1,2,\dotsc ,\lambda \}$ for each of the n secret shares. The output of the leakage function provides the $\ell _{i,j}$-th bit⁵ in the i-th secret-share $s_i$, for all $1\leqslant i\leqslant n$ and $1\leqslant j\leqslant m$. For a fixed secret $s\in F$, the output of the leakage function is a distribution over the sample space ${\{0,1\}} ^{mn}$ induced by the random choice of the secret-sharing polynomial P(X) above.

Local Leakage-Resilience Against Physical Bit-Leakage. $\mathsf{ShamirSS} (n,k,\vec X)$ is $(1-\varepsilon )$-secure against local physical-bit leakages if, for any two secrets $s^{\left( 0\right) },s^{\left( 1\right) } \in F$ and an m-bit local physical-bit leakage function, the statistical distance between the leakage distributions is at most $\varepsilon$.⁶

Result I: Feasibility. Suppose we are given as input the number of parties $n\in \mathbb {N}$, the reconstruction threshold $2\leqslant k\in \mathbb {N}$, the length of the binary representations $\lambda \in \mathbb {N}$, the insecurity tolerance $\varepsilon =2^{-t}$, and the number of leakage bits m from each secret-share. Our experiment picks distinct evaluation places $\vec X$ uniformly at random from the set $F^*$. Given a fixed tuple of distinct evaluation places $\vec X$, one tests whether $\mathsf{ShamirSS} (n,k,\vec X)$ is resilient to m-bit local physical-bit leakage resilient or not.

We prove that the $\mathsf{ShamirSS} (n,k,\vec X)$ scheme is $(1-\varepsilon )$-secure (except with an exponentially small probability in $(k-1)\cdot \lambda$ over the random choices of the evaluation places $\vec X$), if the following conditions are satisfied.

• 1. The number of bits $\lambda$ satisfies $\lambda /\log ^2\lambda \geqslant \varTheta \left( t/k\right) ,$ and

• 2. The total leakage mn satisfies $mn\leqslant k\lambda /\log ^2\lambda$.

This result is the summarized in Theorem 4 and Corollary 4.

The constants in the asymptotic notations are all universal positive constants. Given n, k, F parameters, note that one can choose the random evaluation places once (using a trusted setup, e.g., common random string) for all future instantiations of Shamir secret-sharing scheme. The probability that the instantiation is not $(1-\varepsilon )$-secure is exponentially small. We emphasize that the result above holds for any $k\geqslant 2$, which is the best possible result. Therefore, for every $n,k,m,\varepsilon$, our result proves that Shamir secret-sharing scheme for all large-enough prime fields F is leakage-resilient.

A Concrete Example. As a representative example, consider the following scenario. Suppose the reconstruction threshold is $k=2$, the number of bits leaked is $m=1$, and the number of parties $n=10, 100,\text { and }1000$. Assume we wish to achieve insecurity $\varepsilon =2^{-50}$ and succeed in picking a set of good evaluation places with probability (at least) $1-2^{-50}$. Our Theorem 3 states that picking a prime number p with more than 430, 4800, and 62000 bits, respectively, in its binary representation suffices. Intuitively, it scales (roughly) linearly with n. As k increases, even smaller primes suffice. The estimates above correspond to the most difficult case for security.

Reinterpretation: Randomly Punctured Reed-Solomon Code. Given a Reed-Solomon code of dimension k over a prime-field F, one punctures $(p-1)-n$ columns among the columns numbered $\{1,2,\dotsc ,p-1\}$. Suppose the columns numbered $(0,X_1,\dotsc ,X_n)$ survive the puncturing operations. The Massey secret-sharing scheme [35] corresponding to this resulting $[n+1,k]_F$ linear error-correcting code is identical to the $\mathsf{ShamirSS} (n,k,\vec X)$ secret-sharing scheme mentioned above. Consequently, our result proves that all puncturing operations (except an exponentially small fraction of them) result in an $(1-\varepsilon )$-secure leakage-resilient scheme.

Result II: Hardness of Computation. We present an attack strategy for any $k\geqslant 2$, $n\geqslant k$, $m\geqslant 1$, and $p=1\mod k$. For a fixed $k\geqslant 2$, there are infinitely many primes satisfying $p=1\mod k$ due to Dirichlet’s theorem [39]. Our attack leaks only the least-significant bit of the secret-shares, and has a constant advantage in distinguishing two secrets based on this leakage. For given values of k, n, p satisfying the conditions above, there are (roughly) $n^kp^{n-k} \cdot (p-1)/k$ vulnerable tuples of evaluation places where our attack succeeds.

For $k=2,3$ (and any p), we calculate the exact advantage of our attack. Next, for any $k\geqslant 2$, as $p\rightarrow \infty$, we show that the quality of our attack is lower-bounded by the “discrepancy” of the Irwin-Hall distribution [18, 23] (with parameter $(k-1)$, represented by $I_{k-1}$). The “discrepancy” of a distribution (see Definition 9) is a new property of probability distributions that we introduce, which is of potential independent interest. We explicitly calculate the discrepancy of the Irwin-Hall distribution for $(k-1)\in \{2,3,\dotsc ,24\},$ and Fig. 2 provides the details. If the discrepancy of the Irwin-Hall distribution $I_{k-1}$ is non-zero, then the discrepancy is at least 1/k!. However, based on our numerical experiments, we conjecture that the discrepancy of Irwin-Hall distribution (with parameter k) behaves as $\geqslant \exp (-\varTheta \left( k\right) ),$ which is not negligible for $k=\mathcal {O}\left( \log \lambda \right)$. We emphasize that, given a fixed k, the conjectured distinguishing advantage of this attack depends only on k, independent of the security parameter. Intuitively, increasing the size of the prime should only make the scheme more secure, and the conjecture above considers $p\rightarrow \infty$.

Reinterpretation: Attack on Additive Secret-Sharing Scheme. Our physical bit leakage attack on the Shamir secret-sharing scheme directly translates into physical bit leakage attacks on the additive secret-sharing scheme. If the number of shares in the additive secret sharing scheme is $\mathcal {O}\left( \log \lambda \right)$ then, our conjecture above, states that the advantage of our attack is $1/\mathsf {poly}\left( \lambda \right)$.

Benhamouda et al.  [3] proposed a general leakage attack on additive secret-sharing scheme. Their attack tests whether each share is smaller than p/2k and has an advantage of (roughly) $1/k^k$. In comparison, our attack employs a simpler leakage function, i.e., physical-bit leakage, and will achieve similar advantage if our conjecture holds. Since the leakage function is simpler, the threat it poses is even more significant.

1.2 Technical Overview

Let $\lambda$ be the security parameter. Let F be a prime field of order p such that p needs $\lambda$ bits in its binary representation. That is, we have $p\in \{2^{\lambda -1},2^{\lambda -1}+1,\dotsc ,2^\lambda -1\}$.

For a secret $s\in F$, assume that Shamir’s secret sharing scheme uses a random polynomial P(X) of degree $<k=\mathsf {poly}\left( \lambda \right)$ conditioned on $P(0)=s$ to share a secret among $n=\mathsf {poly}\left( \lambda \right)$ parties. Let the evaluation places be $\vec X=(X_1,X_2,\dotsc ,X_n)\in (F^*)^n$ such that $i\ne j\implies X_i\ne X_j$ (i.e., all evaluation places are distinct). The share of party i is the evaluation of the polynomial P(X) at the evaluation place $X_i$. $\mathsf {ShamirSS}(n,k,\vec X)$ represents this secret-sharing scheme.

Fix the local leakage function $\vec \tau$ that leaks m physical-bits from the binary representation of the secret-shares of the n parties. Furthermore, $\vec \tau \left( \mathsf {Share}^{\vec {X}}(s)\right)$ represents the joint distribution of the leakage conditioned on the fact that the secret is $s\in F$. If this joint distribution of the leakage is independent of the secret, then the secret-sharing scheme is locally leakage-resilient to physical bit leakages.

Our objective is to prove that Shamir secret-sharing scheme is locally leakage-resilient for most evaluation places $\vec X$, when $\vec X$ is chosen uniformly at random from the set $(F^*)^n$ under the constraint that $i\ne j\implies X_i\ne X_j$. Theorem 3 formally states this result. To simplify the presentation of key technical ideas, it is instructive to use $m=1$. The analysis for larger m is analogous.

Reduction 1. Fix any two secrets $s^{\left( 0\right) },s^{\left( 1\right) } \in F$. We prove the following two bounds. First, by standard Fourier techniques, we prove

$$\mathsf {SD} \left( {\vec {\tau }\left( \mathsf {Share}^{\vec {X}}(s^{\left( 0\right) })\right) }\;,\;{\vec {\tau }\left( \mathsf {Share}^{\vec {X}}(s^{\left( 1\right) })\right) }\right) \leqslant \sum _{\vec {\ell }\in {\{0,1\}} ^n}\sum _{\vec {\alpha } \in C_{\vec {X}}^\perp \setminus \{0\}} \left( \prod _{i=1}^n \left| \widehat{\mathbbm {1}_{\ell _i}}(\alpha _i) \right|\right) .$$

Here, $\mathbbm {1}_{\ell _i}$ is the indicator function of the set $\{x:L_i(x)=\ell _i\}$; $C_{\vec {X}}$ is the (punctured) Reed-Solomon code that corresponds to Shamir’s secret-sharing with evaluation places $\vec {X}$; $C_{\vec {X}}^\perp$ is the dual code of $C_{\vec {X}}$.

Next, we show that it suffices to prove that, over randomly chosen evaluation places $\vec X\in (F^*)^n$ (under the constraint that $i\ne j\implies X_i\ne X_j$), this upper bound is small. That is,

$$\mathop {\mathrm {E}}\limits _{{\vec {X}}}\left[ {\sum _{\vec {\ell }\in {\{0,1\}} ^n}\sum _{\vec {\alpha } \in C_{\vec {X}}^\perp \setminus \{0\}} \left( \prod _{i=1}^n \left| \widehat{\mathbbm {1}_{\ell _i}}(\alpha _i) \right|\right) }\right] \leqslant \exp (-\varTheta \left( \lambda \right) ).$$

This bound above is sufficient for our objective. One could use a union bound on the leakage function to conclude that most evaluation places yield a locally leakage-resilient Shamir secret-sharing scheme. After that, a Markov inequality yields random evaluation places, except an exponentially small fraction of the evaluation places, result in a locally leakage-resilient Shamir secret-sharing scheme. Note that we avoid the union bound over secrets since the upper bound is insensitive to the secret. The above argument can be found in Sect. 5.2.

Reduction 2. We employ Fourier analysis to estimate the following bound

$$\mathop {\mathrm {E}}\limits _{{\vec {X}}}\left[ {\sum _{\vec {\ell }\in {\{0,1\}} ^n}\sum _{\vec {\alpha } \in C_{\vec {X}}^\perp \setminus \{0\}} \left( \prod _{i=1}^n \left| \widehat{\mathbbm {1}_{\ell _i}}(\alpha _i) \right|\right) }\right] .$$

The analysis in Sect. 5.4 reduces this estimation to two problems, Problems A and B below.

Problem A. For simplicity of presenting the main technical ideas, assume that the parties’ secret-shares are elements from the set ${\{0,1\}} ^\lambda$. The Fourier analysis above relies on bounding certain exponential sums over the subset of elements that agree with an apriori fixed m-bit leakage. In particular, these elements will have m bits identical to the leakage, and all remaining $(\lambda -m)$ bits may either be zero or one. The abstraction of generalized arithmetic progressions (refer to Sect. 3.1) is adequate to capture the analytic properties of such subsets.

We import an estimate of the exponential sum mentioned in Imported Theorem 1. For the particular case of $m=1$, we present a tight estimate of the constant in the above imported theorem (refer to Theorem 2). This tight estimate of the constant translates into near-optimal bounds on the local leakage-resilience of Shamir secret-sharing scheme.

A subtlety in the argument above is that the set of binary representations of a party’s secret-share is not the set ${\{0,1\}} ^\lambda$. It is, in fact, the set of the binary representations of $\{0,1,\dotsc ,p-1\}$. However, this subset can be partitioned into (at most) $\lambda$ subsets such that each set is an MSB-fixing set, a set whose most significant bits are fixed and the least significant bits are uniformly random (for formal definition and examples, refer to Sect. 4). This notion of MSB-fixing sets introduced by us helps perform the simplified analysis mentioned above in the context of our problem.

Problem B. Once problem A is solved, the Fourier analysis requires another bound. Fix any $\vec \alpha \in F^n$. Next, consider the following equation.

$$ \begin{pmatrix} X_1 &{} X_2 &{} \cdots &{} X_n \\ X_1^2 &{} X_2^2 &{} \cdots &{} X_n^2\\ \vdots &{} \vdots &{} \ddots &{} \vdots \\ X_1^{k-1} &{} X_2^{k-1}&{} \cdots &{}X_n^{k-1} \end{pmatrix} \cdot \begin{pmatrix} \alpha _1\\ \alpha _2\\ \vdots \\ \alpha _n \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix}. $$

How many solutions $\vec X\in (F^*)^n$ exist of the equation above, such that $i\ne j\implies X_i\ne X_j$?

Consider the simplification when $\vec \alpha =\vec 1$. Fix any distinct values of $X_{k+1},\dotsc , X_n\in F^*$. If a solution $X_1,\dotsc ,X_k$ exists (where each $X_1,\dotsc ,X_n$ are distinct as well) then every permutation of $X_1,\dotsc , X_k$ is also a solution. Consequently, the number of solutions of the equation above is at least $\min \{0,k!\}$.

We rely on Bézout ’s theorem (in particular, a form that has an easy-to-verify analytic test, refer to Imported Theorem 2) to claim that the number of solutions is, in fact, at most k!. Consequently, overall, the number of solutions $\vec X\in (F^*)^n$ is $\mathcal {O}\left( k!\cdot p^{n-k}\right)$. This bound holds for any $\vec \alpha$, in general, and not just for $\vec \alpha =\vec 1$.

Resolving the problems A and B completes the proof of Theorem 3. Corollary 2 is an easy-to-use corollary of this theorem demonstrating that when $n=\mathsf {poly}\left( \lambda \right)$, $k=\mathcal {O}\left( \frac{t}{\lambda }+ \frac{\log \lambda }{\lambda }\cdot n\right)$ suffices to ensure that $1-\exp (-\varTheta \left( \lambda \right) )$ fraction of the evaluation places yield a Shamir secret-sharing scheme that is locally leakage-resilient to $m=1$ physical-bit leakage with insecurity $\leqslant$ $2^{-t}$.

Generalization to m-Bit Leakage from Each Share. Observe that one can directly consider the leaking m-bit leakage from the secret-shares of the Shamir secret-sharing scheme. Towards this objective, one needs to consider MSB-fixing sets that are consistent with an apriori fixed leakage, which are proper rank-$(m+1)$ generalized arithmetic progressions. However, the constant in Imported Theorem 1 for rank-$(m+1)$ generalized arithmetic progressions is not explicit. Moreover, without an explicit constant, one can not provide concrete bound on the insecurity of the secret-sharing scheme. Consequently, our work relies on a different approach.

We consider secret-sharing scheme where each share of the Shamir secret-sharing scheme is duplicated m-times, and the adversary leaks one physical bit from each secret share. This technique allows using our Theorem 2 that has an explicit and tight constant, which is specifically tailored for our problem. The remainder of the technical analysis proceeds similar to the presentation above. The general result is summarized as Theorem 4.

New Physical-Bit Attack. For reconstruction threshold k, consider the number of parties $n=k$, and the prime $p=1\mod k$. Let F be the finite field of order p. Let $\left\{ \alpha ,\alpha ^2,\dotsc ,\alpha ^{k}=1\right\} \subseteq F^*$ be the set of all solutions to the equation $Z^k-1=0$. Consider $n=k$ evaluation places $X_1=\alpha$, $X_2=\alpha ^2, \dotsc$, and $X_k=\alpha ^k$. Let $f(X) \in F[X]/X^k$ be an arbitrary polynomial with $f(0)=s$, for some secret $s\in F.$ Observe that $f(X_1) + f(X_2) + \cdots + f(X_k) = ks$.

To present the primary technical ideas, consider $k=3$. Let $s_1$ be the secret share of party one. Over the random choice of the polynomial f(X),  the secret share $s_1$ is uniformly random over F. Similarly, the choice of $s_2$, the secret share of party two, is independent and uniformly random over F. However, the secret share of the k-th party satisfies the constraint $s_k = ks - \sum _{i=1}^{k-1} s_i,$ i.e., $s_3 =3s - (s_1+s_2).$

Our leakage functions shall leak the least significant digit of the shares $s_1,s_2,$ and $s_3$ to construct a test that predicts the least significant digit of ks with constant advantage, for an appropriate $s\in F$. For a random secret, our test has (statistically close to) zero advantage. So, our test distinguishes, by an averaging argument, two secrets with a constant advantage.

Our New Test. Let represent the whole numbers corresponding to the secret shares $s_1,s_2,s_3$. Our test predicts the least significant digit of ks as the parity of the least significant digits of $S_1,S_2,S_3$. Observe that (the addition in the equation below is over the set of whole numbers $\mathbb {N}_0$, and $(ks)\in F$ is interpreted as an element of $\{0,1,\dotsc ,p-1\}$)

$$ S_1 + S_2 + S_3 = p\mathbb {Z}+ (ks).$$

Therefore, if $S_1+S_2+S_3 = ip+ks,$ for an even integer i, then the parity of the least significant digits of $S_1,S_2,S_3$ correctly predicts the least significant digit of ks. On the other hand, if $S_1+S_2+S_3 = ip+ks,$ for an odd integer i, then the parity of the least significant digits of $S_1,S_2,S_3$ incorrectly predicts the least significant digit of ks. Our objective is to prove that there exists $s\in F$ such that the absolute value of the difference between the correct and incorrect prediction probabilities is a constant. Equivalently, the objective is to prove that there exists $s\in F$ such that the probability of correct prediction probability is a constant larger than 1/2 or a constant smaller than 1/2.

So, for independent and uniformly random $S_1,S_2\in \{0,1,\dotsc ,p-1\}$, our objective is to compute the probability that

$$ S_1 + S_2 + S_3 = ip + (ks),$$

where i is even and $S_3\in \{0,1,\dotsc ,p-1\}$. Equivalently, for independent and uniformly random $S_1,S_2\in \{0,1,\dotsc ,p-1\}$, our objective is to compute the probability that

For $k=3$, we can show that this probability is <0.25 by choosing $ks = (p-1)/2$.

Extensions. Note that our attack naturally extends to that the evaluation places form an arbitrary coset in $F^* / \{\alpha ,\dotsc ,\alpha ^k=1\}$. For $n>k$, one can choose the remainder of the evaluation places arbitrarily. Consequently, there are a total of $\sim n^k \cdot p^{n-k} \cdot (p-1)/k$ evaluation places where our attack works.

For a fixed k, and prime $p\rightarrow \infty$, Sect. 6.1 shows that the advantage of our test tends to $\mathsf {disc} (I_{k-1}),$ where $I_{k-1}$ is the Irwin-Hall distribution for parameter $(k-1)$, and Definition 9 defines the discrepancy of a probability distribution $\mathsf {disc} (\cdot )$. Figure 1 shows this discrepancy for $(k-1)=4$ and $(k-1)=5$. Figure 2 shows the conjectured bound for discrepancy for $(k-1)\in \{2,3,\dotsc ,24\}.$

2 Preliminaries

In this work, $\lambda$ represents the security parameter. Let p be a prime whose binary representation has $\lambda$ bits. Or, equivalently, the prime satisfies $2^{\lambda -1} \leqslant p<2^\lambda$. For any positive integer a and $i\geqslant 1$, $\left[ {a}\right] _{i}$ denotes the $i^{th}$ least significant bit in the binary representation of a. For example, let $\lambda = 5$ and $p=19$, the field element $5\in F=\{0,1,...,18\}$ is binary represented as 00101. Its least significant bit is $[5]_1=1$, second least significant bit is $[5]_2=0$, and so on. Using our notations, the binary representation of p is $\left[ {p}\right] _{\lambda }\left[ {p}\right] _{\lambda -1}\cdots \left[ {p}\right] _{1}$.

Fig. 1.

Plot of the Irwin-Hall distribution for parameters $(k-1)=4$ and $(k-1)=5$. The black intervals have width 1, each black interval is separated from the next nearest black interval by distance 1, and the central mass of probability distribution is captured by a black interval. The discrepancy of the respective distributions is the difference between the probability mass inside the black bands and the total probability mass outside the black bands. For $(k-1)=4$ and $(k-1)=5$, the discrepancies are 5/24 and 2/15, respectively.

For any set S, $\mathbbm {1}_S$ denotes its indicator function. That is, $\mathbbm {1}_S(x)=1$ if $x\in S$, and $\mathbbm {1}_S(x)=0$, otherwise.

For any two distributions A and B (over a countable sample space), the statistical distance between two distributions, represented by $\mathsf {SD}(A,B)$, is defined as $\frac{1}{2}\sum _{x}\left|\text {Pr}\left[ A=x\right] -\text {Pr}\left[ B=x\right] \right|$.

We shall use $f(\lambda )\sim g(\lambda )$ if $f(\lambda ) = \left( 1+\text {o}\left( 1\right) \right) g(\lambda )$. Additionally, we write $f(\lambda )\lesssim g(\lambda )$ if $f(\lambda )\leqslant \left( 1+\text {o}\left( 1\right) \right) g(\lambda )$.

2.1 Secret Sharing Schemes

Definition 1

($(n,k)_F$-Secret Sharing Scheme). For any two positive integer $k<n$, an $(n,k)_F$-secret-sharing scheme over a finite field F consists of two functions $\mathsf {Share}$ and $\mathsf {Rec}$. $\mathsf {Share}$ is a randomized function that takes a secret $s\in F$ and outputs $\mathsf {Share}(s) = (\mathsf {Share}(s)_1,\ldots ,\mathsf {Share}(s)_n)\in F^n$. The pair of function $(\mathsf {Share},\mathsf {Rec})$ satisfies the following requirements.

• Correctness. For any secret $s\in F$ and a set of parties $\{i_1,i_2,\ldots ,i_t\}\subseteq \{1,2,\ldots ,n\}$ such that $t\geqslant k$, we have

  $$\text {Pr}\left[ \mathsf {Rec}(\mathsf {Share}(s)_{i_1},\ldots ,\mathsf {Share}(s)_{i_t})=s\right] = 1.$$

• Privacy.⁷ For any two secret $s_0,s_1\in F$ and a set of parties $\{i_1,i_2,\ldots ,i_t\}\subseteq \{1,2,\ldots ,n\}$ such that $t< k$, we have

  $$\mathsf {SD} \left( {\Big (\mathsf {Share}(s_0)_{i_1},\ldots ,\mathsf {Share}(s_0)_{i_t}\Big )}\;,\;{\Big (\mathsf {Share}(s_1)_{i_1},\ldots ,\mathsf {Share}(s_1)_{i_t}\Big )}\right) =0.$$

Fig. 2.

Plot of $-\ln \mathsf {disc} (I_{k-1})$ versus $(k-1)$ for $(k-1)\in \{2,3,\dotsc ,24\}.$

Definition 2

($(n,k,\vec {X})_F$-Shamir Secret-sharing). Let F be a prime field. For any positive integer $k\leqslant n$ and evaluation places $\vec {X}=(X_1,\ldots ,X_n)$ the following conditions are satisfied. (1) For all $1\leqslant i\leqslant n$, $X_i\in F^*$, and (2) for all $1\leqslant i<j\leqslant n$, $X_i\ne X_j$. The corresponding $(n,k,\vec {X})_F$-Shamir secret sharing is defined as follows.

• Given secret $s\in F$, $\mathsf {Share}^{\vec {X}}(s)$ independently samples a random $a_i\in F$, for all $1\leqslant i< k$. The $i^{th}$ share of $\mathsf {Share}^{\vec {X}}(s)$ is

  

• Given shares $\left( \mathsf {Share}^{\vec {X}}(s)_{i_1},\ldots ,\mathsf {Share}^{\vec {X}}(s)_{i_t}\right)$, $\mathsf {Rec}^{\vec {X}}$ interpolates to obtain the unique polynomial $f\in F[X]/X^k$ such that $f(X_{i_j}) = \mathsf {Share}^{\vec {X}}(s)_{i_j}$ for all $1\leqslant j\leqslant t$, and outputs f(0) to be the reconstructred secret.

2.2 Physical-Bit Leakage Function

In this paper, we study the physical-bit leakage. Let F be the prime field of order p. Recall that $2^{\lambda -1}\leqslant p<2^{\lambda }$. For every element $a\in F$, we let a be an element in the set $\{0,1,\ldots ,p-1\}$. We shall use $\lambda$ bits for the binary representation of a, i.e., $\left[ {a}\right] _{\lambda }\left[ {a}\right] _{\lambda -1}\cdots \left[ {a}\right] _{1}$. In particular, we pad with a sufficient number of 0s if $a<2^{\lambda -1}$. For example, when $\lambda =5$ the binary representation of $a=6$ is 00110.

Definition 3

An m-bit physical-bit leakage function $\vec {\tau }=(\tau _1,\ldots ,\tau _n)$ on $(n,k)_F$-secret sharing, leaks m bits from every share locally. This leakage function is specified by indices $u^{(i)}_1,\ldots ,u^{(i)}_m$, for all $1\leqslant i\leqslant n$. Given the indices $u^{(i)}_1,\ldots ,u^{(i)}_m$, the leakage on the $i^{th}$ share is the joint distribution

Furthermore, $\vec {\tau }\left( \mathsf {Share}(s)\right)$ denotes the collection of leakage from every share

$$\left( \tau _1(\mathsf {Share}(s)_1),\tau _2(\mathsf {Share}(s)_2),\ldots ,\tau _n(\mathsf {Share}(s)_n)\right) .$$

2.3 Local Leakage-Resilient Secret Sharing Scheme Against Physical-Bit Leakage

Definition 4

($\llbracket n,k,m,\varepsilon \rrbracket _F$-LLRSS). An $(n,k)_F$-secret sharing scheme $(\mathsf {Share},$$\mathsf {Rec})$ is an $\llbracket n,k,m,\varepsilon \rrbracket _F$-local leakage-resilient secret sharing scheme against m physical-bit leakage (tersely represented as $\llbracket n,k,m,\varepsilon \rrbracket _F$-LLRSS), if it provides the following guarantee. For any two secrets $s_0,s_1\in F$ and any physical-bit leakage function $\vec {\tau }$ that leaks m physical bits from every share locally, we have

$$\mathsf {SD} \left( {\vec {\tau }(\mathsf {Share}(s_0))}\;,\;{\vec {\tau }(\mathsf {Share}(s_1))}\right) \leqslant \varepsilon .$$

2.4 Generalized Reed-Solomon Code

Definition 5

($(n,k,\vec {X},\vec {\alpha })_F$-GRS). A generalized Reed-Solomon code over prime field F with message length k and block length n consists of an encoding function $\mathsf {Enc}:F^k\rightarrow F^n$ and decoding function $\mathsf {Dec}:F^n\rightarrow F^k$. It is specified by the evaluation places $\vec {X}=(X_1,\ldots ,X_n)$, such that for all $1\leqslant i\leqslant j\leqslant n$, $X_i\ne X_j$, and a scaling vector $\vec {\alpha }=(\alpha _1,\ldots ,\alpha _n)$ such that for all $1\leqslant i\leqslant n$, $\alpha _i\in F^*$. Given $\vec {X}$ and $\vec {\alpha }$, the encoding function is

where .

In particular, the generator matrix of the linear $(n,k,\vec {X},\vec {\alpha })_F$-GRS code is the matrix

$$\begin{pmatrix} \alpha _1\cdot 1 &{} \alpha _2\cdot 1 &{} \cdots &{} \alpha _n\cdot 1\\ \alpha _1\cdot X_1 &{} \alpha _2\cdot X_2 &{} \cdots &{} \alpha _n\cdot X_n\\ \vdots &{} \vdots &{} \ddots &{} \vdots \\ \alpha _1\cdot X_1^{k-1} &{} \alpha _2\cdot X_2^{k-1} &{} \cdots &{} \alpha _n\cdot X_n^{k-1} \end{pmatrix}. $$

Observation 1

The joint distribution of the secret-shares of an $(n,k,\vec {X})_F$-Shamir secret sharing with secret $s=0$ is identical to the uniform distribution over the codewords in the $(n,k-1,\vec {X},\vec {X})_F$-GRS code.

The following standard properties of generalized Reed-Solomon codes shall be helpful.

Theorem 1

(Properties of GRS). 

• 1. The distance of the $(n,k,\vec {X},\vec {\alpha })_F$-GRS is $(n-k+1)$ (i.e., the linear code is maximum distance separable [32]).

• 2. The dual code of $(n,k,\vec {X},\vec {\alpha })_F$-GRS is identical to the $(n,n-k,\vec {X},\vec {\beta })_F$-GRS, where for all $1\leqslant i\leqslant n$,

  

The $\beta _i$’s are the scalars from Lagrange interpolation. A proof for this theorem can be found in, for example, [17, 31].

2.5 Fourier Analysis Basics

In this paper, we shall use Fourier analysis on prime field F of order p. We follow the notation of [38]. Define . For any functions $f,g:F\rightarrow {\mathbb C}$, define

where $\overline{z}$ is the complex conjugate of $z\in \mathbb {C}$. For $z\in \mathbb {C}$, . For any $\alpha \in F$, define the function $\widehat{f}:F\rightarrow {\mathbb C}$ as follows.

The Fourier transform maps the function f to the function $\widehat{f}$. This transformation is a full-rank linear mapping, i.e., only the zero function has zero Fourier. In particular, it satisfies the following identities.

Lemma 1

(Fourier Inversion Formula). $f(x) = \sum _{\alpha \in F} \widehat{f}(\alpha )\cdot \omega ^{\alpha x}$.

Lemma 2

(Parseval’s Identity). $\frac{1}{p}\sum _{x\in F}\left|f(x) \right|^2 = \sum _{\alpha \in F}\left|\widehat{f}(\alpha ) \right|^2$.

3 Imported Theorems

3.1 Generalized Arithmetic Progressions

Our first imported theorem is on the $\ell _1$-norm of the Fourier-coefficients of the indicator function of a generalized arithmetic progression.

Definition 6

(r-GAP). Let F be a finite field. A subset $S\subseteq F$ is a generalized arithmetic progression of rank r (i.e., an r-GAP) if

$$S = \left\{ a_0+a_1h_1+a_2h_2+\cdots +a_rh_r \;:\; 0\leqslant h_i<H_i \text { for every } 1\leqslant i\leqslant r\right\} ,$$

where $a_0,\ldots ,a_r\in F$ and $2\leqslant H_1,\ldots ,H_r\leqslant \left|F \right|$.

Furthermore, the set S is proper if $\left|S \right| = H_1H_2\cdots H_r$.

Intuitively, in a proper GAP every element in the set has a unique decomposition.

Shao [40] proved that for any proper r-GAP S, the $\ell _1$-norm of the Fourier-coefficients of its indicator function $\mathbbm {1}_S$ is small.

Imported Theorem 1

(Theorem 3.1 of [40]).⁸ For every natural number r, there exists a constant $C_r>0$ such that the following bounds holds for any proper r-GAP $S\subseteq F$.

$$\sum _{\alpha \in F}\left|\widehat{\mathbbm {1}_S}(\alpha ) \right| \leqslant C_r\cdot {\log (H_1)\cdots \log (H_r)}.$$

Shao [40] proved this result for vector spaces over F as well. However, we are importing the minimum result sufficient for our derivations.

In our setting, we are interested in a special type of proper 2-GAPs satisfying $a_1=1$ and $a_2=2H_1$. We carefully calculate the constant $D_2$ for this special case because a tight estimate itranslates into tight bounds on the insecurity of the cryptographic constructions. Our results are summarized in Theorem 2.

3.2 Number of Isolated Solutions of a Square Polynomial System

Our next imported theorem is regarding the number of the solutions of a square polynomial system. The specific version of Bézout ’s theorem that we are using is due to Wooley [42]. Before we present Wooley’s theorem, let us introduce the minimal necessary definitions. For this part of the presentation, we follow the notations introduced by [10].

Definition 7

(Degree, Formal Derivative, Determinant, and Jacobian). 

• 1. Let F be a prime field. The degree of a monomial $X_1^{i_1}X_2^{i_2}\cdots X_n^{i_n}$ is $\sum _{\ell =1}^n i_\ell$. For a polynomial $f\in F[X_1,X_2,\ldots ,X_n]$, the degree of f is the largest degree of its monomial.

• 2. Suppose

  $$f = g_t X_i^t+g_{t-1}X^{t-1}_i+\cdots +g_1X_i+g_0,$$

  where $g_0,\ldots ,g_t\in F[X_1,\ldots ,X_{i-1},X_{i+1},\ldots ,X_n]$. Then, the formal derivative of f with respect to $X_i$ is the polynomial in $F[X_1,X_2,\dotsc ,X_n]$ defined below.

  

• 3. For a square matrix $M\in \Big (F[X_1,X_2,\ldots ,X_n]\Big )^{k\times k}$, $\det (M)$ denotes the determinant of M defined as follows.

  

  where ${{\,\mathrm{sgn}\,}}(\sigma )$ represents the $\{+1,-1\}$ sign of the permutation $\sigma$.⁹ Note that $\det (M)\in F[X_1,X_2,\ldots ,X_n]$.

• 4. For polynomials $f_1,\ldots ,f_k\in F[X_1,X_2,\ldots ,X_n]$, their Jacobian is

  

Intuitively, the Jacobian encodes information pertinent to the independence of a system of polynomials.

A square polynomial system has equal number of polynomials and the number of variables. That is, in the presentation above, we have $n=k$. The following theorem bounds the number of isolated solutions of a square polynomial system.

Imported Theorem 2

(Consequence of [42]). Let F be a prime order field. Let $f_1,\ldots ,f_k\in F[X_1,\ldots ,X_k]$ such that the degree of $f_i$ is $d_i$. The number of $(x_1,\ldots ,x_k)\in F^k$ satisfying

$$\begin{aligned} \forall 1\leqslant i\leqslant k,\quad f_i(x_1,\ldots ,x_k)&= 0&\text { and}\\ \det \Big (\mathbf {J}(f_1,\ldots ,f_k)\Big )(x_1,\ldots ,x_k)&\ne 0. \end{aligned}$$

is at most $\left( d_1d_2\cdots d_k\right)$.

Wooley’s theorem covers the case of polynomial congruence equations $\mod p^s$, where $s\geqslant 1$. However, we import the result that suffices for our derivations.

Intuitively, a root with high multiplicity also occurs as a root of the Jacobian. On the other hand, the isolated roots occur only in the polynomials but not in the Jacobian. This theorem presented above, provides an easy-to-verify test to count the isolated roots of a square polynomial system.

4 Physical-Bit Witness Set as a Small Number of 2-GAPs

Let $1\leqslant u\leqslant \lambda$ be an arbitrary index. Let $b\in {\{0,1\}}$ be an arbitrary bit. We are interested in

We shall prove that for any u and b, $A_{u,b}$ is the disjoint union of (at most) $\lambda$ number of 2-GAPs.

We first show that the prime field F can be partitioned as $\lambda$ number of most-significant-bit-fixing sets, which is defined as follows.

Definition 8

(Most-significant-bit-fixing Set). A set $S\subseteq F$ is called most-significant-bit-fixing set (MSB-fixing set) if there exists an index $1\leqslant i^*\leqslant \lambda$ and a fixing $a_\lambda , a_{\lambda -1},\ldots ,a_{i^*}$ such that S is identical to the following set.

$$ \left\{ b \in {\{0,1\}} ^\lambda \;\Big \vert \; \forall i^*\leqslant i\leqslant \lambda ,\ \left[ {b}\right] _{i}=a_i \right\} .$$

For example, when $\lambda =5$, the set $S=01{\{0,1\}} ^3$ (i.e., the bit-strings corresponding to the elements in the set $\{8,9,10,\dotsc ,15\}$) is an MSB-fixing set.

Fig. 3.

Given a finite field F, this procedure partitions F into MSB-fixing sets $F_\lambda ,F_{\lambda -1},\ldots ,F_{1}$.

Given a prime field F, Fig. 3 demonstrates how to partition it as most significant bit-fixing sets. Easily, one can verify that $F_\lambda ,F_{\lambda -1},\ldots ,F_{1}$ are all MSB-fixing sets. For example, when $\lambda =5$ and $p=29$, the binary representations of the elements in $\{0,1,\dotsc ,28\}$ partitions into subsets $0{\{0,1\}} ^4$, $10{\{0,1\}} ^3$, $110{\{0,1\}} ^2$, and $\{11100\}$.

Now, given $A_{u,b}$, for $0\leqslant i\leqslant \lambda$, define

One can verify that $A_i$ consists of all bit-strings such that the following conditions hold simutaneously. (1) Some of most significant bits are fixed, (2) the $u^{th}$ least significant bit is fixed to b, and (3) finally, all the remaining positions are uniformly random. Continuing with the example above, the set $S_{2,0}$ is the subset of elements in S with their 2-nd LSB fixed to 0. That is, $S_{2,0} = 01{\{0,1\}} 0 {\{0,1\}}$, the binary representation of elements in the set $\{8,9,12,13\}$. Therefore, one can write $A_i$ as

$$A_i = \left\{ a_0+h_1+a_2h_2 \;:\; 0\leqslant h_i<H_i \text { for } i=1,2\ \right\} ,$$

for some $a_0$, $a_2$, $H_1$, and $H_2$ such that $a_2 = 2H_1$ and $a_2H_2<p$. For example, the elements whose binary representation are in the set $S_{2,0}$ above can be expressed as the proper 2-GAP $8 + \{0,1\} + \{0,4\}$. We have the following theorem regarding the $\ell _1$-norm of the Fourier coefficient of such special type of 2-GAP sets.

Theorem 2

Let p be a prime and

$$S = \left\{ a_0+h_1+a_2h_2 \;:\; 0\leqslant h_i<H_i \text { for } i=1,2\right\} ,$$

for some $a_0$, $a_2$, $H_1$, and $H_2$ such that $a_2 = 2H_1$ and $a_2H_2<p$. Then

$$\sum _{\alpha \in F}\left|\widehat{\mathbbm {1}_S}(\alpha ) \right|\leqslant \left( 1+\text {o}\left( 1\right) \right) \cdot \left( \frac{2}{\pi }\right) ^2\cdot \log (H_1)\log (H_2).$$

We defer the proof of this theorem to the full version. This theorem immediately implies the following corollary.

Corollary 1

For any index $1\leqslant u\leqslant \lambda$ and bit $b\in {\{0,1\}}$,

$$\sum _{\alpha \in F}\left|\widehat{\mathbbm {1}_{A_{u,b}}}(\alpha ) \right| \leqslant \left( 1+\text {o}\left( 1\right) \right) \cdot \frac{1}{{\pi }^2}\cdot \left( \log p\right) ^2\cdot \lambda .$$

Proof

We have

The last inequality uses the fact that $H_1\cdot H_2<p$.

5 Physical-Bit Leakage on Shamir Secret Sharing

In this section, we prove the following theorems.

Theorem 3

For any $\varepsilon >0$, the following bound holds.

$$\mathop {\mathrm {Pr}}\limits _{{\vec {X}}}\left[ {\mathsf {ShamirSS}(n,k,\vec {X}) \text { is }\mathrm {not}\text { an } \llbracket n,k,1, \varepsilon \rrbracket _F\text {-LLRSS}}\right] \lesssim \frac{1}{\varepsilon }\cdot \frac{ 2^n \cdot (\log p)^{3n} \cdot \lambda ^n \cdot (k-1)! }{ \pi ^{2n} \cdot (p-n)^{k-1}}.$$

We emphasize that $\vec X$ is the uniform distribution over the set of all n-tuple of unique evaluation places in $F^*$.

Before we present the proof of this theorem, let us first interpret it through various parameter settings.

Corollary 2

Let $0<d<\ln 2$ be an arbitrary constant. There exists a (slightly) super-linear function $P(\cdot ,\cdot )$ such that the following holds. For any number of parties $n\in \mathbb {N}$, reconstruction threshold $2\leqslant k\in \mathbb {N}$, and insecurity tolerance $\varepsilon =2^{-t}$, if the number of bits $\lambda$ needed to represent the order of the prime-field F satisfies $\lambda > P(n/k,t/k)$, then $\mathsf {ShamirSS}(n,k,\vec {X})$ is an $\llbracket n,k,1, \varepsilon \rrbracket _F\text {-LLRSS}$ with probability (at least) $1 - \exp (-d\cdot (k-1)\lambda )$.

In particular, the (slightly super-linear) function $P\left( n/k,t/k\right) =d'\cdot \left( {\frac{n}{k}+\frac{t}{k}}\right) \cdot \log ^2\left( \frac{n}{k}+\frac{t}{k}\right)$ suffices, for an appropriate universal positive constant $d'$.

In fact, our result can be generalized to multiple-bit physical leakage, which is summarized as follows.

Theorem 4

For any $\varepsilon >0$, for any positive integer m, the following bound holds.

We remark that this result extends to the setting that $m_i$ bits are leaked from the $i^{th}$ share for $i\in \{1,2,\ldots ,n\}$. In this case, the probability that $\mathsf {ShamirSS}(n,k,\vec {X})$ is not leakage resilient is bounded by

$$\frac{1}{\varepsilon }\cdot { \log p \atopwithdelims ()m_1}{ \log p \atopwithdelims ()m_2}\cdots { \log p \atopwithdelims ()m_n}\cdot \frac{2^{M} \cdot (\log p)^{2M}\cdot \lambda ^{M}\cdot (k-1)! }{\pi ^{2n} \cdot (p-n)^{k-1}},$$

where $M = \sum _{i=1}^nm_i$.

The proof of Theorem 4 is analogous to the proof of Theorem 3. Hence, we omit the proof of Theorem 4 and refer the reader to the full version for details.

Similarly, we interpret Theorem 4 as follows.

Corollary 3

Let $0<d<\ln 2$ be an arbitrary constant. There exists a (slightly) super-linear function $P(\cdot ,\cdot )$ such that the following holds. For any number of parties $n\in \mathbb {N}$, reconstruction threshold $2\leqslant k\in \mathbb {N}$, number of bits leaked from each share $m\in \mathbb {N}$, and insecurity tolerance $\varepsilon =2^{-t}$, there exists $\lambda _0 = P\left( mn/k,t/k\right)$ such that if the number of bits $\lambda$ needed to represent the order of the prime-field F satisfies $\lambda > \lambda _0$, then $\mathsf {ShamirSS}(n,k,\vec {X})$ is an $\llbracket n,k,m, \varepsilon \rrbracket _F\text {-LLRSS}$ with probability (at least) $1 - \exp (-d\cdot (k-1)\lambda )$.

In particular, function $P\left( mn/k,t/k\right) = d'\cdot \left( \frac{mn}{k} +\frac{t}{k} \right) \cdot \log ^2\left( \frac{mn}{k}+\frac{t}{k}\right)$, for an appropriate universal positive constant $d'$, suffices.

On the other hand, one can also interpret Theorem 4 as follows.

Corollary 4

Let $0<d<\ln 2$ be an arbitrary constant. For any number of parties $n\in \mathbb {N}$, reconstruction threshold $2\leqslant k\in \mathbb {N}$, and insecurity tolerance $\varepsilon =2^{-t}$, there exists $\lambda _0 = \left( t/k\right) \cdot \log \left( t/k\right)$ such that if the number of bits $\lambda$ needed to represent the order of the prime-field F satisfies $\lambda > \lambda _0$, then for all m such that

$$ m\leqslant \frac{k\lambda }{n\log ^2\lambda },$$

it holds that $\mathsf {ShamirSS}(n,k,\vec {X})$ is an $\llbracket n,k,m, \varepsilon \rrbracket _F\text {-LLRSS}$ with probability (at least) $1 - \exp (-d\cdot (k-1)\lambda )$.

5.1 Claims Needed to Prove Theorem 3

We prove Theorem 3 by proving the following claims.

In the first claim, we prove an upper bound on the statistical distance between the leakage of secrets $s_0$ and $s_1$. We emphasize that this upper bound is not sensitive to the actually secrets, but only sensitive to the leakage function $\vec {\tau }$ and evaluation places $\vec {X}$.

Claim 1

Let $(\mathsf {Share}^{\vec {X}}, \mathsf {Rec}^{\vec {X}})$ be an $(n, k, \vec {X})$ Shamir secret sharing. Let $C_{\vec {X}}$ be the set of all possible secret shares of the secret 0.¹⁰ Let $C_{\vec {X}}^\perp$ be the dual code of $C_{\vec {X}}$. For every 1-bit physical leakage function family $\vec {\tau } = (\tau _1, \tau _2, \dotsc , \tau _n)$, for every leakage $\vec {\ell } \in {\{0,1\}} ^n$, and for every pair of secrets $s_0$ and $s_1$, the following inequality holds.

$$\mathsf {SD} \left( {\vec {\tau }\left( \mathsf {Share}^{\vec {X}}(s_0)\right) }\;,\;{\vec {\tau }\left( \mathsf {Share}^{\vec {X}}(s_1)\right) }\right) \leqslant \sum _{\vec {\ell }\in {\{0,1\}} ^n}\sum _{\vec {\alpha } \in C_{\vec {X}}^\perp \setminus \{0\}} \left( \prod _{i=1}^n \left| \widehat{\mathbbm {1}_{\ell _i}}(\alpha _i) \right|\right) .$$

Here, we abuse the notation and use $\mathbbm {1}_{\ell _i}$ to stand for the indicator function $\mathbbm {1}_{\tau _i^{-1}\left( \ell _i\right) }$. That is, $\mathbbm {1}_{\ell _i}(s_i) = 1$ if $\tau _i(s_i) = \ell _i$ and $\mathbbm {1}_{\ell _i}(s_i) = 0$ otherwise.

Our next claim states that the average of the upper bound proven in Claim 1 over all evaluation places $\vec {X}$ is sufficiently small.

Claim 2

Let $(\mathsf {Share}^{\vec {X}}, \mathsf {Rec}^{\vec {X}})$ be an $(n, k, \vec {X})$ Shamir secret sharing. For every 1-bit physical leakage function family $\vec {\tau } = (\tau _1, \tau _2, \dotsc , \tau _n)$, the following inequality holds.

$$\mathop {\mathrm {E}}\limits _{{\vec {X}}}\left[ {\sum _{\vec {\ell }\in {\{0,1\}} ^n}\sum _{\vec {\alpha } \in C_{\vec {X}}^\perp \setminus \{0\}} \left( \prod _{i=1}^n \left| \widehat{\mathbbm {1}_{\ell _i}}(\alpha _i) \right|\right) }\right] \lesssim \frac{2^{n} \cdot (\log p)^{2n}\cdot \lambda ^n\cdot (k-1)! }{\pi ^{2n} \cdot (p-n)^{k-1}}.$$

We defer the proofs to Sect. 5.3 and Sect. 5.4. We shall first present why these claims imply Theorem 3.

5.2 Proof of Theorem 3 Using Claim 1 and Claim 2

By definition, we have¹¹

This completes the proof of Theorem 3.

5.3 Proof of Claim 1

We start with the following calculation, which can be proven using standard techniques in Fourier analysis. We refer the readers to the full version for a proof.

Claim 3

For any leakage $\vec {\ell }\in {\{0,1\}} ^n$, we have

$$ \mathop {\mathrm {Pr}}\limits _{{\vec {s} \leftarrow \mathsf {Share}^{\vec {X}}(s)}}\left[ { \vec {\tau }(\vec {s}) = \vec {\ell }}\right] = \sum _{\vec {\alpha } \in C_{\vec {X}}^\perp } \left( \prod _{i=1}^n \widehat{\mathbbm {1}_{\ell _i}}(\alpha _i)\right) \omega ^{s(\alpha _1 + \cdots + \alpha _n)}.$$

Now, given Claim 3, Claim 1 can be proven as follows.

5.4 Proof of Claim 2

The proof of Claim 2 crucially relies on the following claim, which bounds the number of solutions to a polynomial system. We state and prove this claim first.

Claim 4

Let $\vec {\alpha } = (\alpha _1, \alpha _2, \dotsc , \alpha _n)$ be a non-zero vector in $F^n$. Then the number of solutions $\vec {X} = (X_1, X_2, \dotsc , X_n) \in (F^*)^n$ of the equation $G_{\vec {X}} \cdot \vec {\alpha }^T = \vec {0}$ such that $X_i \ne X_j$ for every $1\leqslant i<j\leqslant n$ is at most $(p-1) (p-2) \cdots (p -(n-k+1)) \cdot (k-1)!$. Here, $G_{\vec {X}}$ stands for the generator matrix of $C_{\vec {X}}$, which is

$$\begin{aligned} G_{\vec {X}} = \begin{pmatrix} X_1 &{} X_2 &{} \cdots &{} X_n\\ X_1^2 &{} X_2^2 &{} \cdots &{} X_n^2\\ \vdots &{} \vdots &{} \ddots &{} \vdots \\ X_1^{k-1} &{} X_2^{k-1} &{} \cdots &{} X_n^{k-1} \end{pmatrix}. \end{aligned}$$

Proof

Note that $G_{\vec {X}} \cdot \vec {\alpha }^T = \vec {0}$ implies that $\vec {\alpha }\in C_{\vec {X}}^\perp$. By Theorem 1, we know $C_{\vec {X}}^\perp$ has distance k, which implies that there are at least k non-zero coordinates in $\vec {\alpha }$. Therefore, without loss of generality, assume $\alpha _i \ne 0$ for every $1\leqslant i \leqslant k-1$. Now, for $i = k, \dotsc , n$, we fix $X_i$ to be arbitrary distinct non-zero values . Note that there are $(p-1) (p-2) \dotsc (p -(n-k+1))$ possible ways of doing this fixing. Let for $i = 1, 2, \dotsc , k-1$. We can rewrite the equation $G_{\vec {X}} \cdot \vec {\alpha }^T = \vec {0}$ as a system of polynomial equations as follows.

Since $\alpha _i \ne 0$, it is a square polynomials system with $\deg (f_i) = i$, for every $1\leqslant i \leqslant k-1$. Next, to apply Imported Theorem 2, we shall show that

$$\det \Big (\mathbf {J}(f_1, f_2, \dotsc , f_{k-1})\Big )(X_1, X_2, \dotsc , X_{k-1}) \ne 0 \text { if } X_i \ne X_j \text { for every } i\ne j.$$

We have

$$\begin{aligned} \mathbf {J}\Big (f_1, f_2, \dotsc ,f_{k-1}\Big )(X_1, X_2, \dotsc , X_{k-1}) = \begin{pmatrix} \alpha _1 &{} 2\alpha _1 X_1 &{} \cdots &{} (k-1)\alpha _1 X_1^{k-2}\\ \alpha _2 &{} 2\alpha _2 X_2 &{} \cdots &{} (k-1)\alpha _2 X_2^{k-2}\\ \vdots &{} \vdots &{} \ddots &{} \vdots \\ \alpha _{k-1} &{} 2\alpha _{k-1} X_{k-1} &{} \cdots &{} (k-1)\alpha _{k-1} X_{k-1}^{k-2} \end{pmatrix} \end{aligned}$$

By the properties of determinant,

$$\begin{aligned}&\det \Big (\mathbf {J}\left( f_1, f_2, \dotsc , f_{k-1}\right) \Big )(X_1, X_2, \dotsc , X_{k-1}) \\&= \left( \prod _{i=1}^{k-1} \alpha _i\right) \cdot \det \begin{pmatrix} 1 &{} 2 X_1 &{} \cdots &{} (k-1) X_1^{k-2}\\ 1 &{} 2 X_2 &{} \cdots &{} (k-1) X_2^{k-2}\\ \vdots &{} \vdots &{} \ddots &{} \vdots \\ 1 &{} 2 X_{k-1} &{}\cdots &{} (k-1) X_{k-1}^{k-2} \end{pmatrix} \\&= \left( \prod _{i=1}^{k-1} \alpha _i\right) (k-1)! \cdot \det \begin{pmatrix} 1 &{} X_1 &{} \cdots &{} X_1^{k-1}\\ 1 &{} X_2 &{} \cdots &{} X_2^{k-1}\\ \vdots &{} \vdots &{} \ddots &{} \vdots \\ 1 &{} X_{k-1} &{} \cdots &{} X_{k-1}^{k-1} \end{pmatrix} \\&\ne 0, \end{aligned}$$

since $\alpha _i$ are non-zeros and the Vandermonde matrix is full-rank. By Imported Theorem 2, there are at most $(k-1)!$ solutions for the above square polynomial system. Since there are total $(p-1)(p-2) \dotsc (p -(n-k+1))$ possible ways of fixing $X_{k}, X_{k+1}, \dotsc , X_n$, the number of solutions of the equation $G_{\vec {X}} \cdot \vec {\alpha }^T = \vec {0}$ is at most $(p-1) (p-2) \dotsc (p -(n-k+1)) \cdot (k-1)!$, which completes the proof of Claim 4.

Given Claim 4, we are ready to prove Claim 2 as follows.

This gives us the desired upper bound.

6 Physical-Bit Leakage Attack on Shamir Secret-Sharing Scheme

Consider the Shamir secret-sharing scheme with $k$ degree polynomials, where $k\in \{2,3\}$, for n parties over a prime field F of order $p>2$. Fix a secret $s\in F$. Suppose the random polynomial used for secret-sharing is $f(X)\in F[X]/X^k$ such that $P(0)=s$.

Suppose $p = 1\mod k$, that is there exists a solution of the equation $Z^k-1=0$ in the multiplicative group $F^*$. Let $\alpha \in F$ be such that be the multiplicative sub-group of order k containing all k solutions of the equation $Z^k-1=0$.

Suppose $n\geqslant k$, and the evaluation places for the first k parties be $\{1,\alpha ,\alpha ^2,\dotsc , \alpha ^{k-1} \} \subseteq F^*$, respectively. Remaining evaluation places are inconsequential as we shall leak only one bit from the shares of only the first k parties.

Define , for $1\leqslant i\leqslant k$, to be the secret-share of party i. Observe that we have the following properties

• 1. The secret shares $s_1,\dotsc ,s_{k-1}$ are independently and uniformly random over the set F, and

• 2. The secret share $s_k = ks - (s_1 + \cdots + s_{k-1}).$

Let $0\leqslant S_1,S_2,\dotsc ,S_k\leqslant p-1$ be the whole numbers (i.e., the set ) corresponding to the elements $s_1,s_2,\dotsc ,s_k\in F$. Note that

Define . For $k\in \{2,3\}$, we note that¹²

$$\text {Pr}\left[ \sum _{i=1}^{k-1} S_i \in I_{k,\varDelta }\right] \geqslant 0.75. $$

Express $\varDelta = u\cdot p + \delta$, where $u\in \mathbb {N}_0$ (the set of all whole numbers), and $\delta \in \{0,1,\dotsc ,p-1\}$. Define the secret .

Following technical claim, which holds for any secret $s\in F$, is key to our attack strategy.

Claim

(Parity of the “Parity of Shares”). Let $P\in {\{0,1\}}$ represent the LSB (or, equivalently, the parity) of ks when expressed as a whole number. For $1\leqslant i\leqslant k$, let $P_i\in {\{0,1\}}$ represent the LSB (or, equivalently, the parity) of the secret share $S_i$. Define the following subsets of whole numbers

If $S_1+S_2+\cdots +S_{k-1} \in S_{\mathsf {same}}$, then $P_1 \oplus P_2 \oplus \cdots \oplus P_k = P$. Otherwise, if $S_1+S_2+\cdots +S_{k-1} \in S_{\mathsf {diff}}$, then $P_1 \oplus P_2 \oplus \cdots \oplus P_k = 1\oplus P$.

Proof

Since $s_1+s_2+\cdots +s_k = ks$, we have

$$S_1+S_2+\cdots +S_k = ks + ip,$$

for some $i\in {\mathbb N} _0$.

Observe that $P_1\oplus P_2\oplus \cdots \oplus P_k$ is the parity of $S_1+S_2+\cdots +S_k$, which is identical to the parity of ks (i.e., P) if and only if i is even.

Finally, since $S_k\in \{0,1,\ldots ,p-1\}$, the constraint “$S_1+S_2+\cdots +S_k = ks + ip$ for some even i” is equivalent to

$$\begin{aligned} S_1+S_2+\cdots +S_{k-1} \in S_{\mathsf {same}}. \end{aligned}$$

The above claim gives us an attack for the case $k=3$ because of the following argument.

Fix $k=3$, the parity of ks is exactly the parity (LSB) of secret s. Observe that if u is odd, then $I_{k,\varDelta }\subseteq S_{\mathsf {same}}$. In this case, the parity $P_1 \oplus P_2 \oplus \cdots \oplus P_k$ is identical to the LSB of the secret with probability >0.75. Otherwise, if u is even then $I_{k,\varDelta }\subseteq S_{\mathsf {diff}}$. In this case, the parity $P_1 \oplus P_2 \oplus \cdots \oplus P_k$ is the opposite to the LSB of the secret with probability >0.75. In any case, since the adversary knows u, she can predict the LSB of the secret with probability >0.75.

For a randomly chosen secret, on the other hand, one can predict the LSB (using the strategy above) only with probability (statistically close to) 0.5.

Remark 1

Let $\rho \in F$ be the primitive root of the equation $Z^p-1=0$. That is, $\rho$ is a generator for of the multiplicative group $F^*$. The discussion above holds for all evaluation places of the form

$$ \left\{ \rho ^i\cdot \alpha , \rho ^i\cdot \alpha ^2, \dotsc , \rho ^i\cdot \alpha ^k \right\} ,$$

where $i\in \{0,1,\dotsc ,(p-1)/3\}.$ More generally, let $G\subseteq F^*$ be the multiplicative subgroup formed by the roots of the equation $Z^k-1=0$. Any coset $F^*/G$ suffices for our purposes.

Consequently, there is not just one k-tuple of evaluation places that witnesses our attack. There are, in fact, $k!\cdot (p-1)/k$ such tuples that witness our attack.

Therefore, the following result holds.

Theorem 5

Let F be a prime field of order $p>2$. Consider any natural number n such that $p>n\geqslant k=3$ and $p=1\mod k$. There exist distinct secrets $s^{\left( 0\right) },s^{\left( 1\right) } \in F$, distinct evaluation places $X_1,\dotsc ,X_n\in F^*$, and one physical-bit local leakage function $\vec \tau$ such that, based on the leakage, an adversary can efficiently distinguish the secret being $s^{\left( 0\right) }$ or $s^{\left( 1\right) }$ with advantage $>2\cdot (0.75- 0.5) = 0.5$.

Remark 2

We emphasize that our attacker leaks one bit from the first k shares and tries to predict the secret based solely on this. In particular, we do not rely on the information regarding the remaining $n-k$ shares. Asymptotically, this approach is doomed to fail as k grows. As Benhamouda et al.  [3] prove that, Shamir secret sharing is resilient to arbitrary one-bit leakage from each share, as long as $k \geqslant n-n^c$ for some small constant $c>0$. Therefore, to find more devastating attacks, one has to utilize the fact that n is larger than k and we are leaking from every share.

6.1 Our Attack and Discrepancy of Irwin-Hall Distribution

Consider any $2\leqslant k\in \mathbb {N}$ and prime $p=1\mod k$. The following analysis is for the case when $p\rightarrow \infty .$

Observe that $S_i$ is uniformly random over the set $\{0,1,\dotsc ,p-1\}$. Instead of $S_i$, we normalize this random variable and consider $\widehat{S}_i$ that is uniformly random over the set $[0,1)\subset \mathbb {R}$. Now, the random variable $S_1+\cdots + S_{k-1}$ over whole numbers corresponds to the normalized distribution $\widehat{S}_1+\cdots + \widehat{S}_{k-1}$ over the set $[0,k-1)\subset \mathbb {R}$. It is well-known that the sum of $(k-1)$ independent and uniform distributions over the unit interval [0, 1) is the Irwin-Hall distribution [18, 23] with parameter $(k-1)$, represented by $I_{k-1}$.

Let $\delta \in [0,1)$ be an offset. Define the intervals (as a function of $\delta$)

$$\begin{aligned} \widehat{S}_{\mathsf {same}}&= (1+\delta ,2+\delta ] \cup (3+\delta ,4+\delta ] \cup (5+\delta ,6+\delta ] \cup \cdots ,\text { and}\\ \widehat{S}_{\mathsf {diff}}&= (\delta ,1+\delta ] \cup (2+\delta ,3+\delta ] \cup (4+\delta ,5+\delta ] \cup \cdots . \end{aligned}$$

Intuitively, these two sets correspond to the normalized $S_{\mathsf {same}}$ and $S_{\mathsf {diff}}$ sets defined above. The attack above corresponds to finding the offset

and the advantage corresponding to that attack is

Intuitively, this offset $\delta ^*$ witnesses the largest discrepancy and, in turn, determines the most vulnerable secret.

Definition 9

(Discrepancy of a Probability Distribution). Let X be a real-valued random variable. The discrepancy of the random variable X, represented by $\mathsf {disc} (X)$, is

where $I(\delta )$ is the set $\delta + 2\mathbb {Z}+ (0,1]$.

Then, $\mathsf {disc} (I_{k-1})$ represents the advantage of our attack presented above, as $p\rightarrow \infty$.