Publication

Sublinear Bounds on the Distinguishing Advantage for Multiple Samples

Serge Vaudenay
2020
Conference paper
Abstract

The maximal achievable advantage of a (computationally unbounded) distinguisher to determine whether a source ZZ is distributed according to distribution P0P_0 or P1P_1, when given access to one sample of ZZ, is characterized by the statistical distance d(P0,P1)d(P_0,P_1). Here, we study the distinguishing advantage when given access to several i.i.d. samples of ZZ. For nn samples, the advantage is then naturally given by d(P0n,P1n)d(P_0^{\otimes n},P_1^{\otimes n}), which can be bounded as d(P0n,P1n)nd(P0,P1)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 P0P_0 and P1P_1; thus, in general, a linear increase in the distinguishing advantage is unavoidable. In this work, we show new and improved bounds on d(P0n,P1n)d(P_0^{\otimes n},P_1^{\otimes n}) that circumvent the above pessimistic observation. Our bounds assume, necessarily, certain additional information on P0P_0 and/or P1P_1 beyond, or instead of, a bound on d(P0,P1)d(P_0,P_1); in return, the bounds grow as n\sqrt{n}, rather than linearly in nn. 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 ZZ. By this we mean that instead of obtaining samples of ZZ, 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 ZZ. 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.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.