Paper 2026/444

Leakage-Diagrams, Importance Sampling, and Composition in the Random Probing Model

Abstract

Security evaluation of masking in low-noise regimes remains poorly understood: increasing the masking order does not automatically translate into higher concrete resistance once many correlated intermediates are processed by a full implementation. A common approach is to reduce noisy side-channel leakage to the random probing model (RPM), but existing reductions can be too loose to yield meaningful leakage rates in practice, and current RPM analyses often rely on costly simulations or numerically propagated bounds. This work develops analytic and algorithmic tools for estimating and upper-bounding RPM security of masked gadgets and their compositions. First, for noisy Hamming-weight leakage over $\mathbb{F}_{2^u}$ we compute concrete RPM leakage-rate parameters for a tighter $\mathbb{F}_2$-linear reduction based on binary inner products, providing a tangible link between SNR and probing rate. Second, for $\mathbb{F}_q$-linear circuits we leverage a vector-space representation to characterize RPM leakage as an erasure event, yielding a direct connection to local metrics such as advantage and implying global simulability for refreshed, block-separated executions. Third, we improve Monte Carlo estimation of rare leakage events using importance sampling, enabling evaluation in low-rate/high-order regimes that are infeasible with naive sampling. Finally, we revisit the leakage-diagram technique and derive explicit bounds for refresh gadgets, and we apply the same viewpoint to composition through \emph{bridges}, showing that SNI—while sufficient for threshold probing model (TPM)—does not capture the RPM phenomenon governing refresh boundaries. We implement our methods in \textsf{LAPSE}, a tool that compiles gadget descriptions into linear-algebraic representations and supports exact computation as well as Monte Carlo/importance-sampling estimation of RPM security parameters.