Connecting Leakage-Resilient Secret Sharing to Practice: Scaling Trends and Physical Dependencies of Prime Field Masking

Symmetric ciphers operating in (small or mid-size) prime fields have been shown to be promising candidates to maintain security against low-noise (or even noise-free) side-channel leakage. In order to design prime ciphers that best trade physical security and implementation efficiency, it is essential to understand how side-channel security evolves with the field size (i.e., scaling trends). Unfortunately, it has also been shown that such scaling trends depend on the leakage functions and cannot be explained by the standard metrics used to analyze Boolean masking with noise. In this work, we therefore initiate a formal study of prime field masking for two canonical leakage functions: bit leakages and Hamming weight leakages. By leveraging theoretical results from the leakage-resilient secret sharing literature, we explain formally why (1) bit leakages correspond to a worst-case and do not encourage operating in larger fields, and (2) an opposite conclusion holds for Hamming weight leakages, where increasing the prime field modulus p can contribute to a security amplification that is exponential in the number of shares, with \(\log (p)\) seen as security parameter like the noise variance in Boolean masking. We combine these theoretical results with simulated experiments and show that the interest masking in larger prime fields can degrade gracefully when leakage functions slightly deviate from the Hamming weight abstraction, motivating further research towards characterizing (ideally wide) classes of leakage functions offering such guarantees.

1. 1.

   The only known alternative is to rely on fresh re-keying with a leakage-resilient PRF [4], which is only exploitable in tailored designs such as ISAP [17].

2. 2.

   The literature of noise amplification bounds does not directly assume a noise-free setting, as it can be encompassed in the noisy leakage framework. On the opposite, to the best of our knowledge it is more common in the literature about the leakage-resilience of linear secret sharing schemes to rely on this assumption [8, 29].

3. 3.

   The first equality is used in noise amplification papers [20, 34, 40] and aims at quantifying how the distribution of the secret deviates from the prior knowledge whenever some side information \({\textbf {L}}\) is available. The second equality is used in simulation-based proofs [18], and rather aims at quantifying how the side information \({\textbf {L}}\) changes whenever the secret is known.

4. 4.

   This is true regardless of the choice of the metric, i.e., similar trends hold when considering the Mutual Information (MI).

5. 5.

   For a more general statement of Proposition 2 concerning any linear code, see [7].

6. 6.

   The Cauchy-Schwarz trick has already been used in the noise amplification bound of Prouff & Rivain [40, Thm. 1], although applied to another metric.

7. 7.

   This can be formalized by applying the data processing inequality to the \({{\,\mathrm{\textsf{TV}}\,}}\).

8. 8.

   We conjecture based on the numerical calculations of the spectrum that for \(n\ge 13\), \(\left|\widehat{\textbf{1}_{h}}(1)\right|\) maximizes the Fourier transform.

9. 9.

   We empirically observe that all the \(\alpha _i\) are equal to one, however this stronger claim would not seem to improve the upper bound.

François-Xavier Standaert is a senior research associate of the Belgian Fund for Scientific Research (FNRS-F.R.S.). This work has been funded in parts by the German Research Foundation (DFG) CRC 1119 CROSSING (project S7), by the German Federal Ministry of Education and Research and the Hessen State Ministry for Higher Education, Research and the Arts within their joint support of the National Research Center for Applied Cybersecurity ATHENE, by the ERC Consolidator Grant 101044770 (CRYPTOLAYER) and by the ERC Advanced Grant 101096871 (BRIDGE). Views and opinions expressed are those of the authors only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

Authors and Affiliations

1. Department of Computer Science, Technical University of Darmstadt, Darmstadt, Germany

   Sebastian Faust, Elena Micheli & Maximilian Orlt

2. LIRMM, Univ. Montpellier, CNRS, Montpellier, France

   Loïc Masure

3. Crypto Group, ICTEAM Institute, UCLouvain, Louvain-la-Neuve, Belgium

   François-Xavier Standaert

Corresponding author

Correspondence to Elena Micheli .

Editors and Affiliations

1. Zama, Paris, France

   Marc Joye

2. Ruhr University Bochum, Bochum, Germany

   Gregor Leander

A Proofs of Section 2

Proof

of Lemma 1. By definition we have

It follows that the statistical distance for Hamming weight is

We may then leverage Vandermonde’s convolution equality to replace the sum of squared binomial coefficients by \(\left( {\begin{array}{c}2n\\ n\end{array}}\right) - 1\). Finally, using Stirling’s formula, we get the desired result.

As per the MI, notice that it is equal to the entropy of a binomial distribution, truncated from its maximum value \(n\), and re-normalized by a factor \(\frac{2^n}{2^n-1} \approx 1 + 2^{-n}\). We argue hereafter that this slight change to the binomial distribution does not change the entropy approximation. First, the re-normalization factor does not change much the non-truncated terms of the entropy. As per the truncated term, it initially contributed to the entropy at a value \(\frac{n}{2^n} \ll \log \!\left( n\right) \).    \(\square \)

Proof

of Lemma 2. The MI of this leakage model is trivially \(\alpha \cdot n\). As per the bias, first, assume \(\alpha <1\). Then, for every \(h\in \{0,1\}^{\alpha n}\)

Therefore

The result follows from further algebraic computation.

If \(\alpha =1\), then the event \(\left\{ \text {L}=1^n\right\} \) has probability 0, and thus we cannot directly use the above analysis. On the other hand, \(\alpha =1\) describes the case where the secret is completely leaked, that is

Since the above equation corresponds to Eq. (5) for \(\alpha =1\), the lemma follows.    \(\square \)

B Proofs of Section 4

The following lemma tells us that the symmetry property of the HW leakage function, coming from the symmetry of the binomial distribution, also translates in the Fourier transform.

Lemma 6

(Symmetry). Let \(n\in \mathbb {N}\) and \(p = 2^n-1\). Then, for all \(h \in \llbracket 0, n\rrbracket \), and for all \(\alpha \in \mathbb {Z}_p\),

Proof

We start by recalling the identity \({{\,\mathrm{\textsf{HW}}\,}}\!\left( x \oplus y\right) = {{\,\mathrm{\textsf{HW}}\,}}\!\left( x\right) + {{\,\mathrm{\textsf{HW}}\,}}\!\left( y\right) - 2 {{\,\mathrm{\textsf{HW}}\,}}\!\left( x \wedge y\right) \). In particular, for \(y = 2^n-1 = 1...1\), and by observing that \(1...1 \oplus x = 2^n-1-x\), we get that

Therefore, applying the change of variable \(x \mapsto 2^n-1-x\) in Eq. 6 gives us that

Finally, taking the absolute value in both side gives us the desired result.    \(\square \)

Proof

of Theorem 7. Using the Parseval formula, and the fact that \(\widehat{\textbf{1}_{h}}(0) = \frac{\left( {\begin{array}{c}n\\ h\end{array}}\right) }{p}\) by definition of a PMF, we get that

We will use the fact that the maximum squared absolute value of the Fourier coefficients (for non-zero harmonic) is upper bounded by the sum in the left hand-side of Eq. 22. However, stated as such, Eq. 22 would imply trivial upper bounds. Nevertheless, we will show that the sum of the left hand-side contains many identical terms. Thus by factoring the sum, we will tighten the bound.

Let \(1 \le \alpha \le p-1\). Lemma 5 tells us that we can find at least \(n\) other Fourier coefficients sharing the same absolute value as \(\left|\widehat{\textbf{1}_{h}}(\alpha )\right|\)—they can be derived by cyclically shifting the bits of \(\alpha \). Therefore, we can partition the set \(\llbracket 1, p-1 \rrbracket \) of harmonics into classes of harmonics \(\alpha \) sharing the same absolute value of Fourier coefficients, each classes containing at least \(n\) elements. We shall prove that each class actually contains at least \(2\cdot n\) elements.

Claim

Each class contains at least \(2\cdot n\) elements.

Proof

Since \(\textbf{1}_{h}\) is real-valued, we have for all \(\alpha \ne 0\), \(\left|\widehat{\textbf{1}_{h}}(\alpha )\right|= \left|\widehat{\textbf{1}_{h}}(p-\alpha )\right|\). In other words, for each of the \(n\) harmonics that are in the same class, we can derive another harmonic having the same Fourier coefficient in absolute value, hence in the class as well. We shall prove that this conjugate harmonic does not coincide with any of the first \(n\) harmonics emphasized. To see why, observe that

(cf. proof of Lemma 6). Moreover, by assumption \(n\) is odd, so the parity of both hand-sides differ. It implies that the Hamming weight of \(\alpha \) is always different from the Hamming weight of \(p-\alpha \). As a consequence, none of the harmonics derived by shifting the bits of \(p-\alpha \) can never coincide with any of the harmonics derived by shifting the bits of \(\alpha \). Hence, there is at least \(2\cdot n\) elements in each class.    \(\square \)

We can now conclude the proof. Let \(\mathcal {F}_\alpha = \left\{ \alpha ' \in \mathbb {F}_{p^{}} : \left|\widehat{\textbf{1}_{h}}(\alpha ') \right|= \left|\widehat{\textbf{1}_{h}}(\alpha ) \right|\right\} \). Then for all class \(\mathcal {F}_i\), let \(\alpha _{\mathcal {F}_\alpha } = \frac{\left| \mathcal {F}_i\right| }{2n}\). Observe that \(\alpha _{\mathcal {F}_\alpha } \ge 1\) by virtue of the claim.^{Footnote 9} Then we can rephrase Eq. 22 as follows:

therefore for any \(\alpha \), we get that

   \(\square \)

Remark 1

We may even prove that for Mersenne primes, the \(\alpha _{\mathcal {F}_\alpha }\) coefficients in Eq. 23 are integer values. To see why, observe that if \(p\) is a Mersenne prime, then \(n\) is necessarily an odd prime. It follows from Fermat’s little theorem that \(2n\) divides \(p-1\), i.e. the number of terms in Eq. 22.

Proof

of Theorem 6. We start from Eq. 17 from which we derive the following inequality.

The latter inequality is injected into Eq. 10, where we also use the following equality, by definition of the Hamming weight leakage model:

It then comes that

hence the inequality in Eq. 16. The asymptotic estimation of the right hand-side is then derived from the following claim [6, Sec. 3.1]:

   \(\square \)

Reprints and permissions

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics