Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Foundations of privacy (24h, 3 ECTS)

Teachers for 2019-20


  • November 26, 12h45 - 15h45
  • Only printouts of the slides and hand-written notes are allowed.


The course aims at presenting modern approaches to privacy protection, in a wide range of applications such as statistical databases, location based systems, machine learning, and information flow analysis. We will put a particular emphasis on the foundational and formal aspects, proposing rigorous definitions of privacy properties, and providing analyses and proofs of correctness of the methods to achieve them. In accordance with the modern tendency, we will adopt a quantitative point of view, and reason in terms of degree of leakage, risk of privacy violation, etc. In general, this will require to take into account the probabilistic dimension, and formalize the protection of sensitive information in terms of bounds on the probabilistic knowledge of the adversary, and on the probability of success of its attacks.

Plan of the course

Motivations, history and overview (2h)
  • Anonymity
  • k-anonymity
  • De-anonymization attacks
Differential Privacy (4h)
  • Definition
  • Semantics
  • Properties
  • Implementation: Laplace, Geometric, Exponential noise
  • Utility
  • Trade-off between privacy and utility
Local Differential Privacy (4h)
  • Definition
  • Implementation: k-RR
  • Statistical utility
  • Matrix inversion
  • Iterative Bayesian update
d-Privacy (2h)
  • Definition
  • Implementation: Laplace and Geometric noise
  • Application to location privacy: Geo-indistinguishability
Quantitative Information Flow (3h)
  • Vulnerability and leakage – operational interpretation
  • Information-theoretic approaches: Shannon entropy, Renyi min-entropy
  • Decision-theoretic approaches: g-leakage
  • The lattice of information
  • Axiomatization
Privacy issues in Machine Learning (6h)
  • A short introduction to machine learning and to Neural Networks
  • Model inversion attacks
  • Membership inference attacks


Lectures are given in English. The lecture notes and the text of the examinations are in English. The students may answer in French or English.


  • Lecture 1: Anonymity, k-anonymity, de-anonymization attacks. Differential Privacy. Slides
  • Lecture 2: Various mechanisms for Differential Privacy. Sensitivity of a query. Slides
  • Lecture 3: Utility. Local Differential Privacy. d-privacy. Trade-off with statistical utility and quality of service. Slides
  • Lecture 4: Quantitative information flow. The operational model of the adversary and the information-theoretic counterpart. Shannon leakage and Rényi min-entropy leakage. Slides
  • Lecture 5: Introduction to Machine Learning Slides
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA