International Association
for Cryptologic Research

To counter side-channel attacks, a masking scheme randomly encodes key-dependent variables into several {\it shares}, and transforms operations into the masked correspondence (called {\it gadget}) operating on shares. This provably achieves the de facto standard notion of {\it probing security}. We continue the long line of works seeking to reduce the overhead of masking. Our main contribution is a new masking scheme over finite fields in which shares of different variables have a part in common. This enables the reuse of randomness / variables across different gadgets, and reduces the total cost of masked implementation. For security order $d$ and circuit size $\ell$, the randomness requirement and computational complexity of our scheme are $\tilde{O}(d^2)$ and $\tilde{O}(\ell d^2)$ respectively, strictly improving upon the state-of-the-art $\tilde{O}(d^2)$ and $\tilde{O}(\ell d^3)$ of Coron et al. at Eurocrypt 2020. A notable feature of our scheme is that it enables a new paradigm in which many intermediates can be precomputed before executing the masked function. The precomputation consumes $\tilde{O}(\ell d^2)$ and produces $\tilde{O}(\ell d)$ variables to be stored in RAM. The cost of subsequent (online) computation is reduced to $\tilde{O}(\ell d)$, effectively speeding up e.g., challenge-response authentication protocols. We showcase our method on the AES on ARM Cortex M architecture. Our results show a speed-up during the online phase compared with state-of-the-art implementations, at the cost of acceptable RAM consumption and precomputation time. To prove security for our scheme, we propose a new security notion intrinsically supporting randomness / variables reusing across gadgets, and bridging the security of {\it parallel} compositions of gadgets to {\it general} compositions, which may be of independent interest.