Sublinear Bounds on the Distinguishing Advantage for Multiple Samples

The maximal achievable advantage of a (computationally unbounded) distinguisher to determine whether a source $Z$ is distributed according to distribution $P_0$ or $P_1$, when given access to one sample of $Z$, is characterized by the statistical distance $d(P_0,P_1)$. Here, we study the distinguishing advantage when given access to several i.i.d. samples of $Z$. For $n$ samples, the advantage is then naturally given by $d(P_0^{\otimes n},P_1^{\otimes n})$, which can be bounded as $d(P_0^{\otimes n},P_1^{\otimes n}) \leq n \cdot d(P_0,P_1)$. This bound is tight for some choices of $P_0$ and $P_1$; thus, in general, a linear increase in the distinguishing advantage is unavoidable. In this work, we show new and improved bounds on $d(P_0^{\otimes n},P_1^{\otimes n})$ that circumvent the above pessimistic observation. Our bounds assume, necessarily, certain additional information on $P_0$ and/or $P_1$ beyond, or instead of, a bound on $d(P_0,P_1)$; in return, the bounds grow as $\sqrt{n}$, rather than linearly in $n$. Thus, whenever applicable, our bounds show that the number of samples necessary to distinguish the two distributions is substantially larger than what the standard bound would suggest. Such bounds have already been suggested in previous literature, but our new bounds are more general and (partly) stronger, and thus applicable to a larger class of instances. In a second part, we extend our results to a modified setting, where the distinguisher only has indirect access to the source $Z$. By this we mean that instead of obtaining samples of $Z$, the distinguisher now obtains i.i.d. samples that are chosen according to a probability distribution that depends on the (one) value produced by the source $Z$. Finally, we offer applications of our bounds to the area of cryptography. We show on a few examples from the cryptographic literature how our bounds give rise to improved results. For instance, importing our bounds into the analyses of Blondeau et al. for the security of block ciphers against multidimensional linear and truncated differential attacks, we obtain immediate improvements to their results.