Paper 2022/600

A Nearly Tight Proof of Duc et al.'s Conjectured Security Bound for Masked Implementations

Abstract

We prove a bound that approaches Duc et al.'s conjecture from Eurocrypt 2015 for the side-channel security of masked implementations. Let $Y$ be a sensitive intermediate variable of a cryptographic primitive taking its values in a set $\mathcal{Y}$. If $Y$ is protected by masking (a.k.a. secret sharing) at order $d$ (i.e., with $d+1$ shares), then the complexity of any non-adaptive side-channel analysis --- measured by the number of queries to the target implementation required to guess the secret key with sufficient confidence --- is lower bounded by a quantity inversely proportional to the product of mutual informations between each share of $$ and their respective leakage. Our new bound is nearly tight in the sense that each factor in the product has an exponent of $$ as conjectured, and its multiplicative constant is$$, where $$. It drastically improves upon previous proven bounds, where the exponent was $$, and the multiplicative constant was $$. As a consequence for side-channel security evaluators, it is possible to provably and efficiently infer the security level of a masked implementation by simply analyzing each individual share, under the necessary condition that the leakage of these shares are independent.

Note: Adding comment to point to a similar work https://eprint.iacr.org/2022/576. Minor revision, after we have been notified that Eq. (15) in the previous version was suboptimal.