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 (9h)
  • A short introduction to machine learning and to Neural Networks
  • Model inversion attacks
  • Membership inference attacks
  • Other security issues: Adversarial examples


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
  • Lecture 6: Introduction to multi-layered neural network. Optimization (back-propagation. Regularization and Dropout. The vanishing gradient issue. Slides
  • Lecture 7: Introduction to privacy and security risks, motivations. Membership inference attacks. Slides
  • Lecture 8: Introduction to privacy and security risks, Feature inference. Learning anonymized representation. Adversarial attacks. Slides

Other reading material

The following books are recommended for understanding the topics more in depth. They are not mandatory.

  • For the Differential Privacy part: “The Algorithmic Foundations of Differential Privacy”, by Cynthia Dwork and Aaron Roth. Available on line
  • For the Information Flow part: “The Science of Quantitative Information Flow”, by Mario Alvim et al. Available on line
  • For the Machine Learning part: “Pattern Recognition and Machine Learning”, by Christopher M Bishop. Available on line

Exercises and previous exams

Note: the part on Quantitative Information Flow was treated more in depth in the past years. So, please do not worry if you do not know some of the notions relative to the exercises/exams in Quantitative Information Flow.

This year's exam – with solutions

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