International Association
for Cryptologic Research

Evaluating the security of a device against side-channel attacks is a difficult task. One prominent strategy for this purpose is to characterize the distribution of the rank of the correct key among the different key hypotheses produced by a maximum likelihood attack, depending on the number of measured traces. In practice, evaluators can estimate some statistics of the rank that are used as security indicators---e.g., the arithmetic and geometric mean rank, the median rank, the $\alpha$-marginal guesswork, or the success rate of level $L$. Yet, a direct estimation becomes time-consuming as security levels increase.

In this work, we provide new bounds on these figures of merit in terms of the mutual information between the secret and its side-channel leakages. These bounds provide theoretical insights on the evolution of the figures of merit in terms of noise level, computational complexity (how many keys are evaluated) and data complexity (how many side-channel traces are used for the attack). To the best of our knowledge, these bounds are the first to formally characterize security guarantees that depend on the computational power of the adversary, based on a measure of their informational leakages. It follows that our results enable fast shortcut formulas for the certification laboratories, potentially enabling them to speed up the security evaluation process. We demonstrate the tightness of our bounds on both synthetic traces (in a controlled environment) and real-world traces from two popular datasets (Aisylab/AES\_HD and SMAesH).