Talk by Dr. Catuscia Palamidessi（INRIA, Ecole Polytechnique）on April 22, 14:00pm

TITLE: F-BLEAU: Fast Black-box Leakage Estimation
AUTHORS: Giovanni Cherubin, Konstantinos Chatzikokolakis, Catuscia Palamidessi

ABSTRACT:
We consider the problem of measuring how much a system reveals about its
secret inputs. We work under the black-box setting: we assume no prior
knowledge of the system’s internals, and we run the system for choices of
secrets and measure its leakage from the respective outputs. Our goal is to
estimate the Bayes risk, from which one can derive some of the most popular
leakage measures (e.g., min-entropy, additive, and multiplicative leakage).

The state-of-the-art method for estimating these leakage measures is the
frequentist paradigm, which approximates the system’s internals by looking at
the frequencies of its inputs and outputs. Unfortunately, this does not scale
for systems with large output spaces, where it would require too many
input-output examples. Consequently, it also cannot be applied to systems with
continuous outputs (e.g., time side channels, network traffic).

We exploit an analogy between Machine Learning (ML) and black-box leakage
estimation to show that the Bayes risk of a system can be estimated by using a
class of ML methods: the universally consistent learning rules; these rules
can exploit patterns in the input-output examples to improve the estimates’
convergence, while retaining formal optimality guarantees. We focus on a set
of them, the nearest neighbor rules; we show that they significantly reduce
the number of black-box queries required for a precise estimation whenever
nearby outputs tend to be produced by the same secret; furthermore, some of
them can tackle systems with continuous outputs. We illustrate the
applicability of these techniques on both synthetic and real-world data, and
we compare them with the state-of-the-art tool, leakiEst, which is based on
the frequentist approach.