Quantitative Information Flow Day (PRINCESS workshop)  


Tuesday, 16 December 2014 - 9h00.  Room Philippe Flajolet (2nd floor), LIX - Bâtiment Alan Turing, Ecole Polytechnique, Palaiseau

How to get there

This workshop is sponsored by the INRIA Project Lab on Privacy CAPPRIS and by the MSR-INRIA project on Privacy-Friendly Services and Apps (besides the usual sponsoring of the Associate Team PRINCESS)

Participants: Carroll Morgan, Geoffrey Smith, Annabelle McIver, Mário Alvim, Javier Parra, Marco Stronati, Nicolas Bordenabe, Kostas Chatzikokolakis, Catuscia Palamidessi, Jean Quilbeuf, Yusuke Kawamoto, Beatrice Berard, Nataliia Bielova, Eric Fabre, Santiago Zanella Béguelin, Sébastien Gambs.

Preliminary Program

  • 9:00 Coffee, Croissants and Welcome
  • 9:30 Speaker: Geoffrey Smith (FIU) 
    TitleConnections between g-leakage and the Dalenius desideratum
    AbstractIn 1977, statistician Tore Dalenius considered disclosures of information about individuals that can result from releases of statistics; he argued that such disclosures cannot be eliminated in practice. In this talk, we focus on disclosures resulting from correlations among secrets. In particular, we consider the leakage of a secret X caused by an apparently unrelated channel C from Y to Z, in the case when X and Y are correlated. We show how to quantify this “Dalenius” leakage of X using g-leakage, and show moreover that the leakage is upper bounded by the capacity of C, regardless of the correlations J between X and Y. Finally, we observe that any gain function g can be interpreted as a correlation, implying that a channel's g-leakage can also be interpreted as its “Dalenius” min-entropy leakage; this gives greater practical significance to the Coriaceous Theorem.  Slides.
  • 10:00  Speaker: Carroll Morgan (UNSW and NICTA) 
    TitleHyper-distributions: What are they? And why should you care? 
    Abstract: This talk will focus on the so-called hyper-distributions. We will review the definition, properties, and justify their interest in security. Slides.
  • 10:30 Speaker: Catuscia Palamidessi (INRIA Saclay)
    Title: An Axiomatic Approach to Quantitative Information Flow 
    AbstractIn the last years there have been several proposals to formalize the notions of information flow and of secret's vulnerability, most of them justified by operational scenarios and by connections with the related field of information theory. One of the most recent proposals, the g-leakage framework, encompasses most of the other proposals and offers systematic perspective of the field, but one may  still wonder whether this is still a somewhat arbitrary or restricted perspective. We take a step back and try to reflect on the general principles that any "reasonable" notion of vulnerability should satisfy. We consider three "natural" laws: the non-negativity of leakage, the the data processing inequality, and the convexity of vulnerability. Quite surprisingly, we discover that, if we are interested in an average notion of risk, then the above laws are all equivalent, and imply that vulnerability must be g-vulnerability. The popular notion of Shannon vulnerability (corresponding to Shannon entropy) happens to be a special case, obtained by imposing, additionally, the equivalence of secrets and the reversibility of data processing. Slides.
  • 11:00 Coffee Break 
  • 11:30 Speaker: Mário Alvim (UFMG) 
    : Quantifying Information Flow for Dynamic Secrets
     A metric is proposed for quantifying leakage of information about secrets and about how secrets change over time. The metric is used with a model of information flow for probabilistic, interactive systems with adaptive adversaries. The model and metric are implemented in a probabilistic programming language and used to analyze several examples. The analysis demonstrates that adaptivity increases information flow. Slides.
  • 12:00 Speaker: Annabelle McIver (Macquarie U.) 
    TitleMeasuring information flows in preferential voting schemes
    AbstractVoting is a perfect example of a system that should be secure, but cannot be interference-free (in the sense of Goguen/Meseguer). The electors expect their privacy to be preserved; but even the simple announcement of a winner necessarily leaks some information (if only a little bit). It is interesting to try to analyse how much.
    Even more interesting, however -- and demanding -- are the social aspects, viz. that different societies have different expectations of privacy, and indeed have greatly differeng voting systems. 
    One of the most challenging voting systems of all, in the above terms, is the method known as Preferential Voting (used eg in Ireland and in Australia). The counting method used here is complex, specified only by legislation and can leak information at many stages as it progresses.
    This talk concerns our first steps in applying our recent theoretical techniques for quantitative information flow to this difficult problem, made very topical as more and more juristictions (including more than one in Australia) are implementing their voting systems electronically. Without, of course, having a fully rigorous specification of what security properties they should satisfy. Can we supply one?  Slides.
  • 12:30 Lunch Break 
  • 14:00 SpeakerYusuke Kawamoto (INRIA Saclay) 
    Title: Quantitative Information Flow for Scheduler-Dependent Systems
    AbstractIn quantitative information flow, one area of interest is to quantify and estimate the information leakage of composed systems. Prior work has focusedon running disjoint component systems in parallel and reasoning about the leakage compositionally, but has not explored how the component systems are run in parallel or how the leakage of composed systems can be minimised. In this work we consider the manner in which parallel systems can be combined or scheduled, and generalise the attacker's capability, of observing outputs of the system, to consider attackers who may be imperfect in their observations. Our main contribution is to present how scheduling and observation affect information leakage properties. In addition we present an efficient way to construct a scheduler that minimises the min-entropy leakage and min-capacity in the presence of any observer.
  • 14:30 Speaker: Nataliia Bielova (INRIA Sophia Antipolis)
    Title: Browser Randomisation against Fingerprinting: a Quantitative Information Flow Approach
    AbstractWeb tracking companies use device fingerprinting to distinguish the users of the websites by checking the numerous properties of their machines and web browsers. One way to protect the users' privacy is to make them switch between different machine and browser configurations.  We propose a formalisation of this privacy enforcement mechanism.                                                                                                                            We use information-theoretic channels to model the knowledge of the tracker and the fingerprinting program, and show how to synthesise a randomisation mechanism that defines the distribution of configurations for each user. This mechanism provides a strong guarantee of privacy (the probability of identifying the user is bounded by a given threshold) while maximising usability (the user switches to other configurations rarely). To find an optimal solution, we express the enforcement problem of randomisation by a linear program.  We investigate and compare several approaches to randomisation and find that more efficient privacy enforcement would often provide lower usability. Finally, we relax the requirement of knowing the fingerprinting program in advance, by proposing a randomisation mechanism that guarantees privacy for an arbitrary program. Slides.
  • 15:00 Speaker: Kostas Chatzikokolakis (LIX) 
    TitleGeo-indistinguishability: A Principled Approach to Location Privacy  
    AbstractIn this talk I will report on our ongoing project aimed at protecting the privacy of the user when dealing with location-based services. The starting point is the principle of geo-indistinguishability, a formal notion of privacy that protects the user’s exact location, while allowing approximate information– typically needed to obtain a certain desired service – to be released. I will present two mechanisms for achieving geo-indistinguishability, one generic to sanitize locations in any setting with reasonable utility, the other custom-built for a limited set of locations but providing optimal utility. Then I will extend these mechanisms to the case of location traces, where the user releases his location repeatedly along the day and we provide a method to limit the degradation of the privacy guarantees due to the correlation between the points. Finally, I will present evaluation results about these mechanisms on real datasets, compared both among themselves and with respect to the state of theart in the field. Slides.
  • 15:30 Coffree Break 
  • 16:00 SpeakerJavier Parra (INRIA Grenoble)
    Title: Data-perturbative, privacy-enhancing mechanisms for personalized recommendation systems.
    AbstractIn recent times, we are witnessing the emergence of a new generation of information systems that adapt their functionalities to meet the unique needs of each individual. Most of these systems rely on, or lend themselves to, the construction of profiles, either inferred from past activity or directly declared by their users. The ability of such systems to profile users is hence what enables personalization, but at the same time, it is the source of serious privacy concerns. This talk shows a couple of data-perturbative strategies aimed at protecting user privacy in one of those systems, namely, in personalized recommenders. The strategies examined do not require any external entity, are simple in terms of infrastructure requirements, but they pose the inherent trade-off between privacy and data utility common to any perturbative approach. This talk will explore the optimal trade-off posed by the simultaneous use of such strategies. Slides.
  • 16:30 Speaker: Jean Quilbeuf (INRIA Rennes) 
    TitleInformation Leakage by Trace Analysis in QUAIL
    Abstract: Quantitative security techniques have been proven effective to measure the security of systems against various types of attackers. However, such techniques are based on computing exponentially large channel matrices or Markov chains, making them impractical for large programs. We propose a different approach based on abstract trace analysis. Byanalyzing directly sets of execution traces of the program and computing security measures on the results, we are able to scale down the exponential cost of the problem. Also, we are able to apply statistical simulation techniques, allowing us to obtain significant results evenwithout exploring the full space of traces. We have implemented the resulting algorithms in the QUAIL tool. We compare their effectiveness against the state of the art LeakWatch tool on two case studies: privacy of user consumption in smart grid systems and anonymity of voters in different voting schemes. Slides.
  • 17:00 Closing