AtEurocrypt 2015, Ducet al. conjectured that the success rate of a side-channel attack targeting an intermediate computation encoded in a linear secret-sharing, a.k.a.masking with\(d+1\) shares, could be inferred by measuring the mutual information between the leakage and each share separately. This way, security bounds can be derived without having to mount the complete attack. So far, the best proven bounds for masked encodings werenearly tight with the conjecture, up to a constant factor overhead equal to the field size, which may still give loose security guarantees compared to actual attacks. In this paper, we improve upon the state-of-the-art bounds by removing the field size loss, in the cases of Boolean masking and arithmetic masking modulo a power of two. As an example, when masking in the AES field, our new bound outperforms the former ones by a factor\(256\). Moreover, we provide theoretical hints that similar results could hold for masking in other fields as well.

1. 1.

   i.e., the number of shares is\(d+1\) if the independence assumption is met.

2. 2.

   e.g., Young-Minkowski’s convolution inequality for the TV [22] or Plancherel’s formula combined with the convolution theorem for the EN [16].

3. 3.

   For cryptographic reasons, the vast majority of the intermediate computations are uniformly distributed, including the inputs and outputs of Sbox — provided that the plaintext and the key are uniformly distributed as well. The only non-uniform intermediate computations of a block cipher may be the potential intermediate calculations of an Sbox.

4. 4.

   We assume without loss of generality that\(\textsf{m}\) has full support over\(\mathcal {Y}\).

5. 5.

   The interested reader may find a similar convexity result, stated in terms of statistical distance, in the works of Dziembowskiet al.  [12, Cor. 2].

6. 6.

   We have afterwards noticed that the proof of Masureet al. ’s bound [22, Prop. 2, Thm. 3] was suboptimal, so the bound of Masureet al. is actually slightly better than Itoet al. ’s one by a factor\(\frac{1}{2}\). That is why in the remaining of this paper, we mainly compare against the bound of Masureet al..

7. 7.

   For low noise levels, it gets gradually closer to one, but this gain has limited practical relevance since masking only provides high security with sufficient noise.

8. 8.

   https://scalib.readthedocs.io/en/latest/index.html.

9. 9.

   This condition is verified retrospectively on Fig. 3.

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 part by the ERC project number 724725 (acronym SWORD). This work has also partly benefited from the bilateral MESRI-BMBF project “APRIORI” from the ANR cybersecurity 2020 call. The authors also acknowledge financial support from the French national Bank (BPI) under Securyzr-V grant (Contract DOS0144216/00), a RISC-V centric platform integrating security co-processors.

Authors and Affiliations

1. LTCI, Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France

   Julien Béguinot, Wei Cheng, Sylvain Guilley, Yi Liu & Olivier Rioul

2. Secure-IC, Paris, France

   Wei Cheng & Sylvain Guilley

3. ICTEAM Institute, Université catholique de Louvain, Louvain-la-Neuve, Belgium

   Loïc Masure & François-Xavier Standaert

Corresponding author

Correspondence toLoïc Masure.

Editors and Affiliations

1. University of Passau, Passau, Germany

   Elif Bilge Kavun

2. Technical University of Munich, Munich, Germany

   Michael Pehl

A Proof of Proposition3

That it under normalized form

B Technical Statements and Proofs from Sect.4

Proposition 5 (Optimal Reversed Pinsker)

Let\(f_{\textsf{opt}}\) be the optimal reverse Pinsker inequality, i.e.,

where\(L=\lfloor M (1 - \varDelta ) \rfloor \). For all p.m.f.P we have\( \mathsf {D_{KL}}(P\; \Vert \;U) \le f_{\text {opt}}(\varDelta (P,U))\).

Proof

By applying the entropy which is Schur-concave to Eqn. 51 in [25]. We factor\(-\log M\) in each term of the inequality to obtain Prop. 5.    \(\square \)

Theorem 3 (Formal version of Theorem 2)

Let\(\mathcal {H}\) be the class of function that is lower bounded by\(f_{\text {opt}}\), concave when composed with a square root and increasing. Let\(P = \frac{1}{4} \prod _{i=0}^d C \mathop {\mathrm {\textsf{MI}}}\limits \!\left( Y_i ; L_i\right) \), we have

Let\(C_{\alpha }=\sup _{\varDelta \in ]0,1-\frac{1}{M}]} f^*(\varDelta ) \varDelta ^{-2\alpha } = \max _{\varDelta = k/M, k \in \{1,\ldots M-1\}} f^*(\varDelta ) \varDelta ^{-2\alpha }\).

We have

Remark 3

The infinum in Eqn. 13 can be computed with the Legendre-Fenchel transform\(f \mapsto f^*\) (i.e.\(f^*(p) = \sup _x \{ px-f(x) \}\)). Indeed, it is given by\(\varDelta \mapsto - (-f_{\text {opt}}\circ \sqrt{\cdot })^{**}(\varDelta ^2)\) by applying Thm. 10 in [27].

The different inequalities are shown in Fig. 5.\(f_1\) is the best for\(\varDelta \le 1/M\) and else\(f_2\) is the best. Eqn. 16 shows that if we reduce the security exponent to\( \frac{1}{2} \) we can obtain a mild (logarithmic) dependency in the field size.

Illustration of the inequalities for\(M=16\). Pinsker is the dashed blue line. The classical reverse Pinsker is the orange line. The optimal reverse Pinsker\(f_{\text {opt}}\) is the green curve. The dotted curve is\(f_2\) and the red curve\(f_1\). (Color figure online)

Full size image

Proof

All derivations of [22] hold for\(f \in \mathcal {H}\) which shows Eqn. 13. Indeed,

Since\((f \circ \sqrt{\cdot } )\) is concave, we apply Jensen inequality and take the expectation to obtain the desired inequality. The expectation of the product is simplified to the product of the expectations by independence of the terms. Let\( f_1 : \varDelta \mapsto \log (1 + M^2(4^{\frac{1}{M}}-1) \varDelta ^2) \approx M C \varDelta ^2\) and\(f_2 : \varDelta \mapsto (\varDelta + \frac{1}{M}) \log (1 + M \varDelta )\). We show that\(f_1\) and\(f_2\) are in\(\mathcal {H}\). For\(f_2\) it is clear since\(f_2\) is\(f^*\) where we removed the negative 1/M periodic term.\(f_1\) is clearly concave in\(\varDelta ^2\) and increasing. To ensure that\(f_1 \ge f_{\text {opt}}\) we consider the case of equality in\(\frac{1}{M}\). This imposes\(\log (1 + \beta _M M^{-2}) = \frac{2}{M}\) where\(\beta _M = M^2(4^{\frac{1}{M}}-1)\). For\(\varDelta \le \frac{1}{M}\),\( M f_{\text {opt}}(\varDelta ) = (1+M\varDelta )\log (1+M\varDelta ) +(1-M\varDelta )\log (1-M\varDelta ) \le \frac{2}{M} \log (1+M^2\varDelta ^2)\) by Jensen in equality. This upper bound of\(f_{\text {opt}}\) is a lower bound of\(f_1\). Since\(\log \) is increasing the inequality holds if and only if\(1+\beta _M \varDelta ^2 \ge (1+M^2\varDelta ^2)^{\frac{2}{M}}\). Equality holds in 0 and 1/M and we show that the derivative of the difference is increasing then decreasing. The derivative is given by\(2\varDelta (\beta _M-2M(1+M^2\varDelta ^2)^{\frac{2}{M}-1})\) and its sign is given by\(\beta _M - 2M(1+M^2\varDelta ^2)^{\frac{2}{M}-1}\). This quantity is positive in 0 and monotonically decreasing hence the result. It remains to prove the inequality for\(\varDelta \ge \frac{1}{M}\). To do so, we show that\(f_1(\varDelta ) \ge \log (1+M\varDelta ) \ge \frac{1+M\varDelta }{M} \log (1+M\varDelta )\). Since\(\log \) is increasing it is enough to have\(1+\beta _M \varDelta ^2 \ge 1 + M \varDelta \) that is\(\varDelta \ge M/\beta _M\) i.e.,\(4^{\frac{1}{M}} - 1 \ge \frac{1}{M}\). This holds since\(e^x-1 \ge x\) by convexity of the exponential. This shows that\(f_1 \in \mathcal {H}\) and Eqn. 14 is proved. Let\(\mathcal {H}_{\text {poly}} = \{ f_{\alpha } : \varDelta \mapsto C_\alpha \varDelta ^{2\alpha } | \alpha \in [0,1]\}\), we show that\(\mathcal {H}_{\text {poly}} \subset \mathcal {H}\). Functions\(\mathcal {H}_{\text {poly}}\) are concave when composed with a square root since\(\alpha \le 1\), increasing since\(\alpha \ge 0\) and lower bounded by\(f_{\text {opt}}\) by definition of\(C_\alpha \). This proves Eqn. 15. To prove Eqn. 16 we observe that\(C_0 = \log (M)\),\(C_{\alpha }\) is continuous and increasing in\(\alpha \). Consider the values of\(\varDelta \) for which the\(\sup \) in the definition of\(C_\alpha \) is reached. Since\(f_{\text {opt}}\) is square-root convex in the intervals\([k/M,(k+1)/M]\) and\(\varDelta \mapsto C_\alpha \varDelta ^{2\alpha }\) is square-root concave we can only have equality in\(\frac{k+1}{M}\). This shows that\(C_\alpha = \max _{\varDelta = k/M, k \in \{1,\ldots M-1\}} f^*(\varDelta ) \varDelta ^{-2\alpha }\). We verify that the maximum is reached in\(1-1/M\) when\(\alpha = \frac{1}{2} \). The ratio of the sequence\(f^*(k/M) (\frac{k}{M})^{-2\alpha }\) is larger than 1 which proves Eqn. 16.    \(\square \)

Reprints and permissions

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

Policies and ethics