Not optimal but efficient: a distinguisher based on the Kruskal-Wallis test

Research about the theoretical properties of side channel distinguishers revealed the rules by which to maximise the probability of first order success (``optimal distinguishers'') under different assumptions about the leakage model and noise distribution. Simultaneously, research into bounding first order success (as a function of the number of observations) has revealed universal bounds, which suggest that (even optimal) distinguishers are not able to reach theoretically possible success rates. Is this gap a proof artefact (aka the bounds are not tight) or does a distinguisher exist that is more trace efficient than the ``optimal'' one? We show that in the context of an unknown (and not linear) leakage model there is indeed a distinguisher that outperforms the ``optimal'' distinguisher in terms of trace efficiency: it is based on the Kruskal-Wallis test.