An Operational Approach to Information Leakage

Ibrahim Issa
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, 2020
Article

Résumé

Given two random variables X and Y , an operational approach is undertaken to quantify the "leakage" of information from X to Y . The resulting measure L (X -> Y) is called maximal leakage, and is defined as the multiplicative increase, upon observing Y , of the probability of correctly guessing a randomized function of X , maximized over all such randomized functions. A closed-form expression for L(X -> Y) is given for discrete X and Y , and it is subsequently generalized to handle a large class of random variables. The resulting properties are shown to be consistent with an axiomatic view of a leakage measure, and the definition is shown to be robust to variations in the setup. Moreover, a variant of the Shannon cipher system is studied, in which performance of an encryption scheme is measured using maximal leakage. A single-letter characterization of the optimal limit of (normalized) maximal leakage is derived and asymptotically-optimal encryption schemes are demonstrated. Furthermore, the sample complexity of estimating maximal leakage from data is characterized up to subpolynomial factors. Finally, the guessing framework used to define maximal leakage is used to give operational interpretations of commonly used leakage measures, such as Shannon capacity, maximal correlation, and local differential privacy.

Official source

https://infoscience.epfl.ch/record/276642?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Network information theory studies the communication of information in a network and considers its fundamental limits. Motivating from the extensive presence of the networks in the daily life, the thesis studies the fundamental limits of particular networks including channel coding such as Gaussian multiple access channel with feedback and source coding such as lossy Gaussian Gray-Wyner network. On one part, we establish the sum-Capacity of the Gaussian multiple-access channel with feedback. The converse bounds that are derived from the dependence-balance argument of Hekstra and Willems meet the achievable scheme introduced by Kramer. Even though the problem is not convex, the factorization of lower convex envelope method that is introduced by Geng and Nair, combined with a Gaussian property are invoked to compute the sum-Capacity. Additionally, we characterize the rate region of lossy Gaussian Gray-Wyner network for symmetric distortion. The problem is not convex, thus the method of factorization of lower convex envelope is used to show the Gaussian optimality of the auxiliaries. Both of the networks, are a long-standing open problem. On the other part, we consider the common information that is introduced by Wyner and the natural relaxation of Wyner's common information. Wyner's common information is a measure that quantifies and assesses the commonality between two random variables. The operational significance of the newly introduced quantity is in Gray-Wyner network. Thus, computing the relaxed Wyner's common information is directly connected with computing the rate region in Gray-Wyner network. We derive a lower bound to Wyner's common information for any given source. The bound meets the exact Wyner's common information for sources that are expressed as sum of a common random variable and Gaussian noises. Moreover, we derive an upper bound on an extended variant of information bottleneck. Finally, we use Wyner's common information and its relaxation as a tool to extract common information between datasets. Thus, we introduce a novel procedure to construct features from data, referred to as Common Information Components Analysis (CICA). We establish that in the case of Gaussian statistics, CICA precisely reduces to Canonical Correlation Analysis (CCA), where the relaxing parameter determines the number of CCA components that are extracted. In this sense, we establish a novel rigorous connection between information measures and CCA, and CICA is a strict generalization of the latter. Moreover, we show that CICA has several desirable features, including a natural extension to beyond just two data sets.

EPFL2021

Chargement

Distributed Constraint Optimization

Thomas Léauté

Distributed Constraint Satisfaction (DisCSP) and Distributed Constraint Optimization (DCOP) are formal frameworks that can be used to model a variety of problems in which multiple decision-makers cooperate towards a common goal: from computing an equilibrium of a game, to vehicle routing problems, to combinatorial auctions. In this thesis, we independently address two important issues in such multi-agent problems: 1) how to provide strong guarantees on the protection of the privacy of the participants, and 2) how to anticipate future, uncontrollable events. On the privacy front, our contributions depart from previous work in two ways. First, we consider not only constraint privacy (the agents' private costs) and decision privacy (keeping the complete solution secret), but also two other types of privacy that have been largely overlooked in the literature: agent privacy, which has to do with protecting the identities of the participants, and topology privacy, which covers information about the agents' co-dependencies. Second, while previous work focused mainly on quantitatively measuring and reducing privacy loss, our algorithms provide stronger, qualitative guarantees on what information will remain secret. Our experiments show that it is possible to provide such privacy guarantees, while still scaling to much larger problems than the previous state of the art. When it comes to reasoning under uncertainty, we propose an extension to the DCOP framework, called DCOP under Stochastic Uncertainty (StochDCOP), which includes uncontrollable, random variables with known probability distributions that model uncertain, future events. The problem becomes one of making "optimal" offline decisions, before the true values of the random variables can be observed. We consider three possible concepts of optimality: minimizing the expected cost, minimizing the worst-case cost, or maximizing the probability of a-posteriori optimality. We propose a new family of StochDCOP algorithms, exploring the tradeoffs between solution quality, computational and message complexity, and privacy. In particular, we show how discovering and reasoning about co-dependencies on common random variables can yield higher-quality solutions.

EPFL2011

Chargement

Symmetry in design and decoding of polar-like codes

Kirill Ivanov

The beginning of 21st century provided us with many answers about how to reach the channel capacity. Polarization and spatial coupling are two techniques for achieving the capacity of binary memoryless symmetric channels under low-complexity decoding algorithms. Recent results prove that another way to achieve capacity is via symmetry, which is the case of the Reed-Muller and extended Bose-Chaudhuri-Hocquenghem (BCH) codes. However, this proof holds only for erasure channel and maximum a posteriori decoding, which is computationally intractable for the general channels.In the first part of this thesis, we talk about the performance improvements that an automorphism group of the code brings on board. We propose two decoding algorithms for the Reed-Muller codes, which are invariant under a large group of permutations and are expected to benefit the most. The former is based on plugging the codeword permutations in successive cancellation decoding, and the latter utilizes the code representation as the evaluations of Boolean monomials. However, despite the performance improvements, it is clear that the decoding complexity grows quickly and becomes impractical for moderate-length codes. In the second part of this thesis, we provide an explanation for this observation. We use the Boolean polynomial representation of the code in order to show that polar-like decoding of sufficiently symmetric codes asymptotically needs an exponential complexity. The automorphism groups of the Reed-Muller and eBCH codes limit the efficiency of their polar-like decoding for long codes, hence we either should focus on short lengths or find another way. We demonstrate that asymptotically same restrictions (although with a slower convergence) hold for more relaxed condition that we call partial symmetry. The developed framework also enables us to prove that the automorphism group of polar codes cannot include a large affine subgroup.In the last part of this thesis, we address a completely different problem. A device-independent quantum key distribution (DIQKD) aims to provide private communication between parties and has the security guarantees that come mostly from quantum physics, without making potentially unrealistic assumptions about the nature of the communication devices. After the quantum part of the DIQKD protocol, the parties share a secret key that is not perfectly correlated. In order to synchronize, some information needs to be revealed publicly, which makes this formulation equivalent to the asymmetric Slepian-Wolf problem that can be solved using binary linear error-correction codes. As any amount of the revealed information reduces the key secrecy, the utilized code should operate close to the finite-length limits. The channel in consideration is non-standard and, due to its experimental nature, it can actually slightly differ from the considered models. In order to solve this problem, we designed a simple scheme using universal SC-LDPC codes and used in the first successful experimental demonstration of DIQKD protocol.

EPFL2022

Chargement

Symmetry in design and decoding of polar-like codes

Kirill Ivanov

EPFL2022

EPFL2021

Distributed Constraint Optimization

Thomas Léauté

EPFL2011