Strong Asymptotic Composition Theorems for Mutual Information Measures

Abstract: Consider a system containing sensitive information X, an adversary interacting with the system to obtain Y, and an information leakage measure denoted by L(X→Y). One of the key challenges in privacy and security problems is to characterize the growth of L(X→Yⁿ) when the adversary makes multiple observations; such results are called composition theorems. We characterize this growth when the observations are conditionally independent and identically distributed given X, and the leakage measure is any of the Sibson and Arimoto mutual informations or α-maximal leakage, of any order that is at least unity. Each of these measures increases exponentially fast to a limit that is order and measure-dependent, with an exponent that is order- and measure-independent (related to the Chernoff information). For the special case of binary X and the maximal leakage metric, we derive an adaptive composition theorem, i.e., the adversary interacts with the system in stages: At each stage i, the adversary may choose an action to interact with the system containing X to obtain Y_i. The action may depend on previous realizations of the observations, but the leakage at each stage is limited. We bound the maximal leakage from X to Yⁿ in terms of the leakage of each stage. Notably, the upper bound is achieved when the observations are conditionally independent outputs of the binary erasure channel (with an appropriate parameter).
=====
Ibrahim Issa is currently a visiting professor with the Laboratory for Information in Networked Systems (LINX) at EPFL (for Spring 2023), and an assistant professor at the Electrical and Computer Engineering department at the American University of Beirut (since January 2019). Prior to this, he finished his PhD in August 2017 at the School of Electrical Engineering at Cornell University (Ithaca, NY), where his thesis on information leakage earned the Outstanding ECE PhD Thesis Research Award. He then joined LINX at EPFL as a postdoctoral researcher from August 2017 to December 2018. His research interests include privacy and security, information theory, machine learning, and quantum information theory.