Lecture

Differential Privacy: Privacy Guarantees and Mechanisms

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

CS-422: Database systems

This course is intended for students who want to understand modern large-scale data analysis systems and database systems. It covers a wide range of topics and technologies, and will prepare students to be able to build such systems as well as read and und ...

Description

This lecture introduces differential privacy, a concept in randomized algorithms ensuring statistical insignificance in results between neighboring databases. The instructor explains the strength of differential privacy in preventing inference about individual records and presents the Laplace Mechanism as a tool to achieve it. The lecture covers the global noise sensitivity, Laplace mechanism-based algorithms, and the implications of differential privacy in algorithm design. It concludes by discussing the tradeoff between privacy and accuracy, emphasizing the pessimistic nature of differential privacy.

Instructor

Anastasia Ailamaki

Expertise Database management systems, scientific applications, computer architecture Teaching & PhD PhD Students Hamish Nicholson, Anna Herlihy, Yi Jiang, Eleni Zapridou, Georgiy Konstantinovich Lebedev, Ioanna Tsakalidou Past EPFL PhD Students Farhan Tauheed, Radu Ioan Stoica, Manos Athanassoulis, Pinar Tözün, Adrian Daniel Popescu, Ioannis Alagiannis, Renata Borovica-Gajic, Danica Porobic, Iraklis Psaroudakis, Manos Karpathiotakis, Matthaios Alexandros Olma, Mirjana Pavlovic, Eleni Tzirita Zacharatou,

Official source

Related concepts (17)

Privacy law

Privacy law is the body of law that deals with the regulating, storing, and using of personally identifiable information, personal healthcare information, and financial information of individuals, which can be collected by governments, public or private organisations, or other individuals. It also applies in the commercial sector to things like trade secrets and the liability that directors, officers, and employees have when handing sensitive information.

Privacy

Privacy (UK, US) is the ability of an individual or group to seclude themselves or information about themselves, and thereby express themselves selectively. The domain of privacy partially overlaps with security, which can include the concepts of appropriate use and protection of information. Privacy may also take the form of bodily integrity. There have been many different conceptions of privacy throughout history. Most cultures recognize the right of an individual to withhold aspects of their personal lives from public record.

Right to privacy

The right to privacy is an element of various legal traditions that intends to restrain governmental and private actions that threaten the privacy of individuals. Over 150 national constitutions mention the right to privacy. On 10 December 1948, the United Nations General Assembly adopted the Universal Declaration of Human Rights (UDHR), originally written to guarantee individual rights of everyone everywhere; while right to privacy does not appear in the document, many interpret this through Article 12, which states: "No one shall be subjected to arbitrary interference with his privacy, family, home or correspondence, nor to attacks upon his honour and reputation.

Algorithmically random sequence

Intuitively, an algorithmically random sequence (or random sequence) is a sequence of binary digits that appears random to any algorithm running on a (prefix-free or not) universal Turing machine. The notion can be applied analogously to sequences on any finite alphabet (e.g. decimal digits). Random sequences are key objects of study in algorithmic information theory. As different types of algorithms are sometimes considered, ranging from algorithms with specific bounds on their running time to algorithms which may ask questions of an oracle machine, there are different notions of randomness.

Randomness

In common usage, randomness is the apparent or actual lack of definite pattern or predictability in information. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual random events are, by definition, unpredictable, but if the probability distribution is known, the frequency of different outcomes over repeated events (or "trials") is predictable. For example, when throwing two dice, the outcome of any particular roll is unpredictable, but a sum of 7 will tend to occur twice as often as 4.

Related lectures (64)

Introduction to Jupyter Exercises

Introduces Jupyter exercises on Differential Privacy, covering random generators, understanding data intrusion impact, and practical applications.

Algorithms to Live By: Optimal Stopping and Logarithmic Regret

Explores optimal stopping, explore/exploit, Bayes' Rule, and logarithmic regret in bandit solutions.

Solving Parity Games in Practice

Explores practical aspects of solving parity games, including winning strategies, algorithms, complexity, determinism, and heuristic approaches.

Constraint Satisfaction: Formulation and Algorithms

Covers the formulation of constraint satisfaction problems and systematic algorithms for solving them efficiently.

Privacy-Preserving Data Mining