DP_Primer.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Copy of Copy of Copy of DP_Primer",
      "provenance": [],
      "collapsed_sections": [
        "591f0t9M42eN",
        "ezEN8gSeqA-T",
        "XIdwwdIJrFZW",
        "YbGS-5X6-zAY",
        "B4koh1BQqDYH",
        "dKYt3LXXqENQ",
        "l6Qz9_YajUY6",
        "qEU91bgGUmv_",
        "4bD1lwPqbdep",
        "y4Yzp56QqEx4",
        "07XyFIPtmDyO",
        "YelDGkItmEJd",
        "mOHK4FW0mDly"
      ],
      "include_colab_link": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.6.4"
    },
    "toc": {
      "base_numbering": 1,
      "nav_menu": {},
      "number_sections": true,
      "sideBar": true,
      "skip_h1_title": true,
      "title_cell": "Table of Contents",
      "title_sidebar": "Contents",
      "toc_cell": true,
      "toc_position": {},
      "toc_section_display": true,
      "toc_window_display": false
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/Kritikalcoder/DP-primer/blob/master/DP_Primer.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "toc": true,
        "id": "CkvXH6VdH3lT",
        "colab_type": "text"
      },
      "source": [
        "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
        "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#Overview\" data-toc-modified-id=\"Overview-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span><strong>Overview</strong></a></span><ul class=\"toc-item\"><li><span><a href=\"#Need-for-Privacy\" data-toc-modified-id=\"Need-for-Privacy-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Need for Privacy</a></span></li><li><span><a href=\"#Earlier-Approaches-to-Privacy\" data-toc-modified-id=\"Earlier-Approaches-to-Privacy-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Earlier Approaches to Privacy</a></span></li><li><span><a href=\"#Motivating-Use-Case\" data-toc-modified-id=\"Motivating-Use-Case-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Motivating Use Case</a></span></li><li><span><a href=\"#Differential-Privacy\" data-toc-modified-id=\"Differential-Privacy-1.4\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Differential Privacy</a></span></li><li><span><a href=\"#Applications\" data-toc-modified-id=\"Applications-1.5\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>Applications</a></span></li><li><span><a href=\"#DP-in-Machine-Learning\" data-toc-modified-id=\"DP-in-Machine-Learning-1.6\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>DP in Machine Learning</a></span></li><li><span><a href=\"#DP-at-OpenMined\" data-toc-modified-id=\"DP-at-OpenMined-1.7\"><span class=\"toc-item-num\">1.7&nbsp;&nbsp;</span>DP at OpenMined</a></span></li><li><span><a href=\"#DP-in-SQL-queries\" data-toc-modified-id=\"DP-in-SQL-queries-1.8\"><span class=\"toc-item-num\">1.8&nbsp;&nbsp;</span>DP in SQL queries</a></span></li><li><span><a href=\"#Practical-DP\" data-toc-modified-id=\"Practical-DP-1.9\"><span class=\"toc-item-num\">1.9&nbsp;&nbsp;</span>Practical DP</a></span></li><li><span><a href=\"#Things-no-one-tells-you-about-DP\" data-toc-modified-id=\"Things-no-one-tells-you-about-DP-1.10\"><span class=\"toc-item-num\">1.10&nbsp;&nbsp;</span>Things no one tells you about DP</a></span></li><li><span><a href=\"#DP-Blog-Series\" data-toc-modified-id=\"DP-Blog-Series-1.11\"><span class=\"toc-item-num\">1.11&nbsp;&nbsp;</span>DP Blog Series</a></span></li><li><span><a href=\"#Glossary\" data-toc-modified-id=\"Glossary-1.12\"><span class=\"toc-item-num\">1.12&nbsp;&nbsp;</span>Glossary</a></span></li><li><span><a href=\"#Resources\" data-toc-modified-id=\"Resources-1.13\"><span class=\"toc-item-num\">1.13&nbsp;&nbsp;</span>Resources</a></span></li></ul></li><li><span><a href=\"#Need-for-Privacy\" data-toc-modified-id=\"Need-for-Privacy-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span><strong>Need for Privacy</strong></a></span></li><li><span><a href=\"#Earlier-Approaches-to-Privacy\" data-toc-modified-id=\"Earlier-Approaches-to-Privacy-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span><strong>Earlier Approaches to Privacy</strong></a></span><ul class=\"toc-item\"><li><span><a href=\"#Data-Perturbation\" data-toc-modified-id=\"Data-Perturbation-3.1\"><span class=\"toc-item-num\">3.1&nbsp;&nbsp;</span><strong>Data Perturbation</strong></a></span></li><li><span><a href=\"#Distributed-ML\" data-toc-modified-id=\"Distributed-ML-3.2\"><span class=\"toc-item-num\">3.2&nbsp;&nbsp;</span><strong>Distributed ML</strong></a></span></li><li><span><a href=\"#Secure-Multi-Party-Computation\" data-toc-modified-id=\"Secure-Multi-Party-Computation-3.3\"><span class=\"toc-item-num\">3.3&nbsp;&nbsp;</span><strong>Secure Multi-Party Computation</strong></a></span></li><li><span><a href=\"#Homomorphic-Encryption\" data-toc-modified-id=\"Homomorphic-Encryption-3.4\"><span class=\"toc-item-num\">3.4&nbsp;&nbsp;</span><strong>Homomorphic Encryption</strong></a></span></li><li><span><a href=\"#Data-Swapping\" data-toc-modified-id=\"Data-Swapping-3.5\"><span class=\"toc-item-num\">3.5&nbsp;&nbsp;</span><strong>Data Swapping</strong></a></span></li><li><span><a href=\"#$k$-Anonymity\" data-toc-modified-id=\"$k$-Anonymity-3.6\"><span class=\"toc-item-num\">3.6&nbsp;&nbsp;</span><strong>$k$-Anonymity</strong></a></span></li><li><span><a href=\"#Rule-Hiding\" data-toc-modified-id=\"Rule-Hiding-3.7\"><span class=\"toc-item-num\">3.7&nbsp;&nbsp;</span><strong>Rule Hiding</strong></a></span></li></ul></li><li><span><a href=\"#Motivating-Use-Case\" data-toc-modified-id=\"Motivating-Use-Case-4\"><span class=\"toc-item-num\">4&nbsp;&nbsp;</span><strong>Motivating Use Case</strong></a></span></li><li><span><a href=\"#Differential-Privacy\" data-toc-modified-id=\"Differential-Privacy-5\"><span class=\"toc-item-num\">5&nbsp;&nbsp;</span><strong>Differential Privacy</strong></a></span><ul class=\"toc-item\"><li><span><a href=\"#Randomized-Algorithm\" data-toc-modified-id=\"Randomized-Algorithm-5.1\"><span class=\"toc-item-num\">5.1&nbsp;&nbsp;</span><strong>Randomized Algorithm</strong></a></span></li><li><span><a href=\"#Informal-Explanation\" data-toc-modified-id=\"Informal-Explanation-5.2\"><span class=\"toc-item-num\">5.2&nbsp;&nbsp;</span><strong>Informal Explanation</strong></a></span></li><li><span><a href=\"#Computation---Privacy---Accuracy-Trade-off\" data-toc-modified-id=\"Computation---Privacy---Accuracy-Trade-off-5.3\"><span class=\"toc-item-num\">5.3&nbsp;&nbsp;</span><strong>Computation - Privacy - Accuracy Trade-off</strong></a></span></li><li><span><a href=\"#Formal-Definitions\" data-toc-modified-id=\"Formal-Definitions-5.4\"><span class=\"toc-item-num\">5.4&nbsp;&nbsp;</span><strong>Formal Definitions</strong></a></span><ul class=\"toc-item\"><li><span><a href=\"#$(\\epsilon,-\\delta)$---DP\" data-toc-modified-id=\"$(\\epsilon,-\\delta)$---DP-5.4.1\"><span class=\"toc-item-num\">5.4.1&nbsp;&nbsp;</span><strong>$(\\epsilon, \\delta)$ - DP</strong></a></span></li><li><span><a href=\"#$(\\epsilon)$---DP\" data-toc-modified-id=\"$(\\epsilon)$---DP-5.4.2\"><span class=\"toc-item-num\">5.4.2&nbsp;&nbsp;</span><strong>$(\\epsilon)$ - DP</strong></a></span></li><li><span><a href=\"#Renyi---DP\" data-toc-modified-id=\"Renyi---DP-5.4.3\"><span class=\"toc-item-num\">5.4.3&nbsp;&nbsp;</span><strong>Renyi - DP</strong></a></span></li></ul></li><li><span><a href=\"#Privacy-Budget---$\\epsilon$\" data-toc-modified-id=\"Privacy-Budget---$\\epsilon$-5.5\"><span class=\"toc-item-num\">5.5&nbsp;&nbsp;</span><strong>Privacy Budget - $\\epsilon$</strong></a></span></li><li><span><a href=\"#Neighbouring-Databases\" data-toc-modified-id=\"Neighbouring-Databases-5.6\"><span class=\"toc-item-num\">5.6&nbsp;&nbsp;</span><strong>Neighbouring Databases</strong></a></span></li><li><span><a href=\"#Function/Query-Sensitivity\" data-toc-modified-id=\"Function/Query-Sensitivity-5.7\"><span class=\"toc-item-num\">5.7&nbsp;&nbsp;</span><strong>Function/Query Sensitivity</strong></a></span></li><li><span><a href=\"#Noise-Mechanisms\" data-toc-modified-id=\"Noise-Mechanisms-5.8\"><span class=\"toc-item-num\">5.8&nbsp;&nbsp;</span><strong>Noise Mechanisms</strong></a></span><ul class=\"toc-item\"><li><span><a href=\"#Laplacian-Mechanism\" data-toc-modified-id=\"Laplacian-Mechanism-5.8.1\"><span class=\"toc-item-num\">5.8.1&nbsp;&nbsp;</span><strong>Laplacian Mechanism</strong></a></span></li><li><span><a href=\"#Gaussian-Mechanism\" data-toc-modified-id=\"Gaussian-Mechanism-5.8.2\"><span class=\"toc-item-num\">5.8.2&nbsp;&nbsp;</span><strong>Gaussian Mechanism</strong></a></span></li><li><span><a href=\"#Exponential-Mechanism\" data-toc-modified-id=\"Exponential-Mechanism-5.8.3\"><span class=\"toc-item-num\">5.8.3&nbsp;&nbsp;</span><strong>Exponential Mechanism</strong></a></span></li><li><span><a href=\"#Sparse-Vector-Technique\" data-toc-modified-id=\"Sparse-Vector-Technique-5.8.4\"><span class=\"toc-item-num\">5.8.4&nbsp;&nbsp;</span><strong>Sparse Vector Technique</strong></a></span></li><li><span><a href=\"#Bernstein-Mechanism\" data-toc-modified-id=\"Bernstein-Mechanism-5.8.5\"><span class=\"toc-item-num\">5.8.5&nbsp;&nbsp;</span><strong>Bernstein Mechanism</strong></a></span></li></ul></li><li><span><a href=\"#Local-DP\" data-toc-modified-id=\"Local-DP-5.9\"><span class=\"toc-item-num\">5.9&nbsp;&nbsp;</span><strong>Local DP</strong></a></span></li><li><span><a href=\"#Global-DP\" data-toc-modified-id=\"Global-DP-5.10\"><span class=\"toc-item-num\">5.10&nbsp;&nbsp;</span><strong>Global DP</strong></a></span></li><li><span><a href=\"#Adversary\" data-toc-modified-id=\"Adversary-5.11\"><span class=\"toc-item-num\">5.11&nbsp;&nbsp;</span><strong>Adversary</strong></a></span></li><li><span><a href=\"#Query-Composition\" data-toc-modified-id=\"Query-Composition-5.12\"><span class=\"toc-item-num\">5.12&nbsp;&nbsp;</span><strong>Query Composition</strong></a></span></li><li><span><a href=\"#Moments-Accountant\" data-toc-modified-id=\"Moments-Accountant-5.13\"><span class=\"toc-item-num\">5.13&nbsp;&nbsp;</span><strong>Moments Accountant</strong></a></span></li><li><span><a href=\"#Simple-Use-Case\" data-toc-modified-id=\"Simple-Use-Case-5.14\"><span class=\"toc-item-num\">5.14&nbsp;&nbsp;</span><strong>Simple Use Case</strong></a></span></li></ul></li><li><span><a href=\"#Applications\" data-toc-modified-id=\"Applications-6\"><span class=\"toc-item-num\">6&nbsp;&nbsp;</span><strong>Applications</strong></a></span></li><li><span><a href=\"#DP-in-Machine-Learning\" data-toc-modified-id=\"DP-in-Machine-Learning-7\"><span class=\"toc-item-num\">7&nbsp;&nbsp;</span><strong>DP in Machine Learning</strong></a></span><ul class=\"toc-item\"><li><span><a href=\"#DP-Classification\" data-toc-modified-id=\"DP-Classification-7.1\"><span class=\"toc-item-num\">7.1&nbsp;&nbsp;</span><strong>DP Classification</strong></a></span></li><li><span><a href=\"#DP-Regression\" data-toc-modified-id=\"DP-Regression-7.2\"><span class=\"toc-item-num\">7.2&nbsp;&nbsp;</span><strong>DP Regression</strong></a></span></li><li><span><a href=\"#DP-Clustering\" data-toc-modified-id=\"DP-Clustering-7.3\"><span class=\"toc-item-num\">7.3&nbsp;&nbsp;</span><strong>DP Clustering</strong></a></span></li></ul></li><li><span><a href=\"#DP-at-OpenMined\" data-toc-modified-id=\"DP-at-OpenMined-8\"><span class=\"toc-item-num\">8&nbsp;&nbsp;</span><strong>DP at OpenMined</strong></a></span></li><li><span><a href=\"#DP-in-SQL-queries\" data-toc-modified-id=\"DP-in-SQL-queries-9\"><span class=\"toc-item-num\">9&nbsp;&nbsp;</span><strong>DP in SQL queries</strong></a></span><ul class=\"toc-item\"><li><span><a href=\"#Common-Relational-Algebra-operations:\" data-toc-modified-id=\"Common-Relational-Algebra-operations:-9.1\"><span class=\"toc-item-num\">9.1&nbsp;&nbsp;</span>Common Relational Algebra operations:</a></span></li></ul></li><li><span><a href=\"#Practical-DP\" data-toc-modified-id=\"Practical-DP-10\"><span class=\"toc-item-num\">10&nbsp;&nbsp;</span><strong>Practical DP</strong></a></span><ul class=\"toc-item\"><li><span><a href=\"#Side-Channel-Attacks\" data-toc-modified-id=\"Side-Channel-Attacks-10.1\"><span class=\"toc-item-num\">10.1&nbsp;&nbsp;</span><strong>Side-Channel Attacks</strong></a></span></li></ul></li><li><span><a href=\"#Things-no-one-tells-you-about-Differential-Privacy\" data-toc-modified-id=\"Things-no-one-tells-you-about-Differential-Privacy-11\"><span class=\"toc-item-num\">11&nbsp;&nbsp;</span><strong>Things no one tells you about Differential Privacy</strong></a></span></li><li><span><a href=\"#Blog-on-DP\" data-toc-modified-id=\"Blog-on-DP-12\"><span class=\"toc-item-num\">12&nbsp;&nbsp;</span><strong>Blog on DP</strong></a></span></li><li><span><a href=\"#Glossary\" data-toc-modified-id=\"Glossary-13\"><span class=\"toc-item-num\">13&nbsp;&nbsp;</span><strong>Glossary</strong></a></span></li><li><span><a href=\"#Resources\" data-toc-modified-id=\"Resources-14\"><span class=\"toc-item-num\">14&nbsp;&nbsp;</span><strong>Resources</strong></a></span></li></ul></div>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "view-in-github"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/Kritikalcoder/DP-primer/blob/master/DP_Primer.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "UkPm9nAgmza5"
      },
      "source": [
        "# **Differential Privacy Primer**\n",
        "\n",
        "## **Overview**\n",
        "\n",
        "### Need for Privacy \n",
        "\n",
        "### Earlier Approaches to Privacy\n",
        "\n",
        "### Motivating Use Case \n",
        "\n",
        "### Differential Privacy\n",
        "- Randomized Algorithm\n",
        "- Informal Explanation\n",
        "- Computation - Privacy - Accuracy Trade-off\n",
        "- Formal Definitions\n",
        "- Privacy Budget\n",
        "- Neighbouring Databases\n",
        "- Function/Query Sensitivity\n",
        "- Adversary\n",
        "- Scaling with Query Composition\n",
        "- Noise Mechanisms\n",
        "- Local DP\n",
        "- Global DP\n",
        "- Query Composition  \n",
        "- Moments Accountant\n",
        "- Online DP\n",
        "- Simple Use Case\n",
        "\n",
        "### Applications\n",
        "\n",
        "### Google's RAPPOR for Local DP\n",
        "\n",
        "### DP in Machine Learning\n",
        "- Deep Learning with DP\n",
        "- DP Stochastic Gradient Descent\n",
        "- DP Classification  \n",
        "- DP Regression  \n",
        "- DP Clustering  \n",
        "\n",
        "### DP at OpenMined\n",
        "- Wrappers for existing libraries  \n",
        "- DifferentialPrivacy.ts\n",
        "\n",
        "### DP in SQL queries\n",
        "\n",
        "### Practical DP\n",
        "- Side-channel attacks  \n",
        "\n",
        "### Things no one tells you about DP\n",
        "- Bounds on data\n",
        "- Bounds on noise distribution\n",
        "\n",
        "### DP Blog Series\n",
        "List of blog topics here\n",
        "\n",
        "### Glossary\n",
        "\n",
        "### Resources"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "IOOxG8WgoKna",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "I3FQLEg0oLF2"
      },
      "source": [
        "## **Need for Privacy**\n",
        "\n",
        "blah blah, fill in later"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "8VZUgPq4pCnt",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "Y-R-CiaLZeE6"
      },
      "source": [
        "## **Additional Approaches to Privacy**\n",
        "\n",
        "### **Data Perturbation**\n",
        "Data perturbation approaches can be grouped into two main categories: the probability distribution approach and the value distortion approach. The probability distribution approach replaces the data with another sample from the same (or estimated) distribution or by the distribution itself, and the value distortion approach perturbs data elements or attributes directly by either additive noise, multiplicative noise, or some other randomization procedures.   \n",
        "\n",
        "### **Distributed ML**\n",
        "Extraction of patterns at a given node in a distributed network by exchanging only the minimal necessary information among the participating nodes.  \n",
        "\n",
        "### **Secure Multi-Party Computation**\n",
        "Evaluate a function of the secret inputs coming from two or more input sources, such that no party learns anything more than the expected output of the function.  \n",
        "\n",
        "### **Homomorphic Encryption**\n",
        "Homomorphic Encryption is a special case of a Secure Multi-Party Computation, where an encryption transformation is applied to the data, such that certain distances and operations on the data are preserved in the encrypted space.    \n",
        "Different types of Homomorphic encryption:  \n",
        "- Fully Homomorphic Encryption\n",
        "- Partial Homomorphic Encryption\n",
        "- Somewhat Homomorphic Encryption \n",
        "\n",
        "### **Data Swapping**\n",
        "Transform the database by switching a subset of attributes between selected pairs of records such that lower order frequency counts are preserved and data confidentiality is not compromised.  \n",
        "\n",
        "### **$k$-Anonymity**\n",
        "The information of each person contained in the publicly released dataset cannot be distinguished from at least $k - 1$ other distinct people.  \n",
        "\n",
        "### **Rule Hiding**\n",
        "Transform the database such that sensitive rules are masked, and at the same time, underlying patterns can still be discovered. Decrease the support of sensitive rules using a user-specified threshold of hiding rules."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "A5CEjnbyZj_H",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "2Nr9vARLovW8"
      },
      "source": [
        "## **Motivating Use Case**\n",
        "\n",
        "**Netflix challenge shows anonymization is not enough!**\n",
        "\n",
        "Anonymity is not enough. In 2006, Netflix announced a \\$1 million prize challenge to improve their movie recommendation service. They publicly released a large dataset containing approximately 100 million movie ratings created by  480 thousand Netflix subscribers over six years. Netflix claimed to have removed all customer identifying information.  \n",
        "\n",
        "But this definition of anonymity is not absolute - they didn't take into account how much a potential adversary (trying to breach the privacy of a user) needs to know about a Netflix subscriber in order to identify his/her record in the dataset. Thus, the question of compromising privacy becomes existential in order to prove that a public release of a dataset does not breach it's participants' privacy and maintains their anonymity.   \n",
        "\n",
        "Shortly after Netflix released it's prize dataset, a linkage attack was created and published which linked the Netflix database with the publicly available view of the IMDB database, resulting in a privacy breach of many of the Netflix subscribers.   \n",
        "\n",
        "Some conventional approaches to privacy are anonymization, sanitization (sampled subset) and controlling access and flow of information. But these do not provide the privacy guarantee.  \n",
        "\n",
        "Privacy of individuals has become a need with rising popularity in today's age of information. This survey of research work over the past few years on differential privacy and privacy preserving machine learning aims to understand the current state of theoretically guaranteed privacy bounds, privacy mechanisms in various scenarios, their implications on the effectiveness of machine learning algorithms and adversarial attacks trying to breach the privacy of participants in a survey or a dataset.   \n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "0Ayhqwr8pDSX",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "-NNVcbu2x0lL"
      },
      "source": [
        "## **Differential Privacy**\n",
        "\n",
        "\"Differential Privacy (DP) is a definition of privacy that involves making sure a data subject is not affected (e.g. not harmed) by their entry or participation in a database, while maximizing utility/data accuracy (as opposed to random/empty outputs) for queries to a database.\"\n",
        "\n",
        "Differentially private database mechanisms can make confidential data widely available for accurate data analysis, without resorting to data clean rooms, data usage agreements, data protection plans, or restricted views. Differential privacy addresses the paradox of learning nothing about an individual while learning useful information about a population.  \n",
        "\n",
        "Differential privacy guarantees that the impact on the participant of a study is the same independent of whether or not he was in the study. It is the conclusions reached in the study that affect the participant, not his presence or absence in the data set.  \n",
        "\n",
        "Differential privacy is a definition, not an algorithm. For a given computational task T and a given value of $\\epsilon$ there will be many differentially private algorithms for achieving T in an $\\epsilon$-differentially private manner. Some will have better accuracy than others. When $\\epsilon$ is small, finding a highly accurate $\\epsilon$-differentially private algorithm for T can be difficult. Therefore, differential privacy makes it impossible to guess whether one participated in a database with large probability.  "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "Mfdsm01Tb0B_",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "jWx3GQyG42NS"
      },
      "source": [
        "### **Randomized Algorithm**\n",
        "\n",
        "A randomized algorithm $M$ with domain $A$ and discrete range $B$ is associated with a mapping $M : A \\xrightarrow{} \\Delta(B)$. On input $a \\in A$, the algorithm $M$ outputs $M(a) = b$ with probability $(M(a))_b$ for each $b \\in B$. The probability space is over the coin flips of the algorithm $M$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "zfZQ2Yh3b0tw",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "14uhkt3Z42Sq"
      },
      "source": [
        "\n",
        "\n",
        "\n",
        "### **Informal Explanation**\n",
        "\n",
        "Modifying the data in a manner such that upon querying the database, no more information about a participant in revealed than the amount revealed if he/she didn't participate in the data survey.\n",
        "\n",
        "\"Adversaries can pinpoint sensitive data of a particular individual using data from multiple databases. For example, researchers were able to find the Governor of Massachusetts's patient profile using de-identified hospital records and a voter registration database. This type of attack is called a linkage attack. Differential privacy helps us avoid linkage attacks by adding noise to true answer of queries to a database. \n",
        "\n",
        "Here's a short, simplified example:\n",
        "\n",
        "1. A data scientist queries a database to find out the number of rows of the database\n",
        "2. The result of the query (i.e. number of rows) is 5\n",
        "3. A differential privacy mechanism adds the number 2 (noise) to the result. \n",
        "4. The final result of the query displayed to the data scientist is the noisy answer 7.\"\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "gFWFj_QJb1PD",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "_0mC41aJYMoj"
      },
      "source": [
        "### **Computation - Privacy - Accuracy Trade-off**\n",
        "\n",
        "- Computational feasibility + speed\n",
        "- Privacy guarantee\n",
        "- Accuracy of result"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "LovUU_FHb12V",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "O2wB8n-m42WE"
      },
      "source": [
        "### **Formal Definitions**\n",
        "\n",
        "#### **$(\\epsilon, \\delta)$ - DP**\n",
        "A randomized algorithm $M$ with domain $\\mathbb{N}^{|\\chi|}$ is $(\\epsilon, \\delta)-$ differentially private if for all $S \\subseteq$ Range $(M)$ and for all $ x,y \\in N^{|\\chi|}$ such that $||x-y||_1 \\leq 1$:  \n",
        "\\begin{equation}\n",
        "Pr[M(x) \\in S] \\leq exp(\\epsilon) Pr[M(y) \\in S] + \\delta\n",
        "\\end{equation}\n",
        "\n",
        "We are interested in values of $\\delta$ in the order of $1/||x||_1$.  \n",
        " \n",
        "$(\\epsilon, \\delta)$ - differential privacy ensures that for all adjacent $x, y,$ the absolute value of the privacy loss will be bounded by $\\epsilon$ with probability at least $1 - \\delta$. Differential Privacy is immune to post processing.  \n",
        "\n",
        "#### **$(\\epsilon)$ - DP**\n",
        "\n",
        "#### **Renyi - DP**\n",
        "\n",
        "Renyi-Differential Privacy (RDP) is a natural relaxation of differential privacy. This new definition shares many properties with the standard definition of $\\epsilon$-DP, while additionally allowing tighter analysis of composite heterogenous mechanisms.   \n",
        " \n",
        "As we have observed in the case of the $(\\epsilon,\\delta)$-DP, it offers relaxation over the standard $\\epsilon$-DP definition. It offers asymptotically smaller cumulative loss under composition and allows greater flexibility in the selection of privacy-preserving mechanisms. The additive $\\delta$ parameter allows suppressing the long tails of the mechanism’s distribution where standard $\\epsilon$-DP guarantees may not hold.   \n",
        "\n",
        "Renyi differential privacy even with very weak parameters never allows a total breach of privacy with no residual uncertainty.  \n",
        "\n",
        "- Renyi Divergence  \n",
        "- KL Divergence  \n",
        "- Renyi DP definition  \n",
        "\n",
        "Properties:  \n",
        "- Renyi divergence is non-negative, monotonic, probability preserving and satisfies the weak triangle inequality.\n",
        "- Renyi divergence of order $\\alpha$ between $P = f(D’)$ and $Q = f(D)$ bounds the $\\alpha^{th}$ moment of the change in $R$, which essentially makes it robust to auxiliary information.\n",
        "- Renyi-DP is preserved by post-processing. \n",
        "- Basic Query Composition: If Query 1 is $(\\alpha, \\epsilon_1)$ - RDP and Query 2 is $(\\alpha, \\epsilon_2)$ - RDP, then the composite Query 3 = (Query 1, Query 2) is $(\\alpha, \\epsilon_1 + \\epsilon_2)$ - RDP.\n",
        "- Group Privacy is ensured\n",
        "$(\\alpha, \\epsilon)$-RDP implies $(\\epsilon + (\\log(1/\\delta) / \\alpha - 1), \\delta)$-DP\n",
        "- Supports advanced Query Composition (the sublinear loss of privacy as a function of the number of queries still holds).\n",
        "- An RDP curve may be sampled in just a few points to provide useful guarantees for a wide range of parameters. If these points are chosen consistently across multiple mechanisms, this information can be used to estimate aggregate privacy loss.\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "bjTGCRcAb2s7",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "591f0t9M42eN"
      },
      "source": [
        "### **Privacy Budget - $\\epsilon$**\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "RGo7G-wnb3XW",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "ezEN8gSeqA-T"
      },
      "source": [
        "\n",
        "### **Neighbouring Databases**\n",
        "\n",
        "Two databases are said to be neighbouring if they differ only in the presence/absence of one record. This helps in calculating the sensitivity of queries to be able to make them differentially private.  \n",
        "\n",
        "The $l_1$ norm of a database $x$ is denoted $||x||_1$ (number of records in the database) and is defined to be:\n",
        "\\begin{equation}\n",
        "||x||_1 = \\sum_{i=1}^{|\\chi|} |x_i|\n",
        "\\end{equation}\n",
        "The $l_1$ distance between two databases $x$ and $y$ is $||x-y||_1$.  \n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "80dftEmTb36Q",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "XIdwwdIJrFZW"
      },
      "source": [
        "### **Function/Query Sensitivity**\n",
        "\n",
        "The $l_1$-sensitivity of a function $f : \\mathbb{N}^{|\\chi|} \\xrightarrow{} R^k$ is:\n",
        " \\begin{equation}\n",
        " \\Delta f = \\max ||f(x) - f(y)||_1\n",
        " \\end{equation}\n",
        " where $||x-y||_1 = 1$ and $x, y \\in \\mathbb{N}^{|\\chi|}$\n",
        " \n",
        "The $l_1$-sensitivity of a function $f$ captures the magnitude by which a single individual's data can change the function $f$ in the worst case. This gives an upper bound on how much we need to perturb the data to preserve privacy. The $l_1$ sensitivity of counting queries is $1$.   \n",
        "\n",
        "The sensitivity of a function captures the magnitude by which a single individual’s data can change the function in the worst case. This directly affects the amount of noise that needs to be added to the data to successfully and surely mask the participation of any single person, acting as a natural upper bound. Differential Privacy preserving mechanisms (such as Laplace Mechanism) use the sensitivity of the query function as a parameter in their noise distributions.   \n",
        "\n",
        "\n",
        "Some of the different types of queries are:  \n",
        "- Small Sensitivity Queries\n",
        "- Large Sensitivity Queries\n",
        "- Numerical Queries (Counting)\n",
        "- Set-Based Queries\n",
        "- Graph-Based Queries\n",
        "- Histograms"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "tA2Mm_SAb4qK",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "YbGS-5X6-zAY"
      },
      "source": [
        "### **Noise Mechanisms**\n",
        "\n",
        "#### **Laplacian Mechanism**\n",
        "\n",
        "Given any function $f : \\mathbb{N}^{|\\chi|} \\xrightarrow{} R^k$, the Laplace Mechanism is defined as:\n",
        "\\begin{equation}\n",
        "    M_L(x,f(.),\\epsilon) = f(x) + (Y_1, Y_2, ... , Y_k)\n",
        "\\end{equation}\n",
        "where $Y_i$'s are independently identically distributed (i.i.d) random variables drawn from the Laplacian distribution $Lap(\\Delta f / \\epsilon)$. The Laplace Mechanism preserves $(\\epsilon, 0)$-differential privacy.    \n",
        "\n",
        "The Laplace mechanism can be used to answer adaptively chosen low\n",
        "sensitivity queries.  \n",
        "\n",
        "- \"Works best for low sensitivity queries \n",
        "- Large epsilon values (aka your privacy budget) are needed to support multiple queries, which can lead to less accurate results.\n",
        "- Negative outputs from the pure Laplacian mechanism are possible, and can be illogical and inconsistent (source: <https://arxiv.org/pdf/1808.10410.pdf>)\"\n",
        "\n",
        "#### **Gaussian Mechanism**\n",
        "\n",
        "- \"The standard deviation is suboptimal in high-privacy regimes, since it grows to infinity.\n",
        "- While the Laplace mechanism can support ε-DP with the relevant standard deviation, the Gaussian mechanism can’t be extended beyond a particular bound. Finding the right noise variance is one solution to this issue.\n",
        "- Source: *Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising:*[ *http://proceedings.mlr.press/v80/balle18a/balle18a.pdf*](https://slack-redir.net/link?url=http%3A%2F%2Fproceedings.mlr.press%2Fv80%2Fballe18a%2Fballe18a.pdf)\" \n",
        "\n",
        "#### **Exponential Mechanism**\n",
        "\n",
        "The exponential mechanism was designed for situations in which we wish to choose the best response but adding noise directly to the computed quantity can completely destroy its value. For example, setting a price of an auction, where the goal is to maximize the revenue is a highly sensitive value.\n",
        "\n",
        "The exponential mechanism $M_E(x,u,R)$ selects and outputs an element $r\\in R$ with probability proportional to $exp({\\epsilon u(x,r)} / {2 \\Delta u})$. The exponential mechanism preserves  $(\\epsilon,0)$-differential privacy.\n",
        "\n",
        "#### **Sparse Vector Technique**\n",
        "\n",
        "Add noise and report only whether the noisy value exceeds the threshold. Privacy degrades only with the number of  queries which lie above the threshold, rather than with the total number of queries.  \n",
        "\n",
        "#### **Bernstein Mechanism**\n",
        "\n",
        "lorem ipsum"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "rNLz3Duvb52i",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "B4koh1BQqDYH"
      },
      "source": [
        "### **Local DP**\n",
        "\n",
        "In the local model of Differential Privacy, the data aggregator does not have access to the real user data. This is made possible by pre-processing data at the user level and adding noise to it, before sending the noisy data to the data aggregator. After collecting this noisy data, the aggregator can compute some statistics, and publish them. This last step doesn't need to be differentially private: the data is anonymous to begin with. In theory, the aggregator could publish the entire dataset they collected.  \n",
        "\n",
        "This model does not require any trust in the data aggregator, but due to the large amounts of noise added, model accuracy faces a serious hit.  "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "VwYR_ec3b6iX",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "dKYt3LXXqENQ"
      },
      "source": [
        "### **Global DP**\n",
        "In the global model of differential privacy, a central aggregator has access to the real data. The differentially private mechanism is only applied once, at the end of the process. The aggregator can then publish the result or share it with third parties. The biggest advantage of this model is the gain in accuracy, as one needs to add much lesser amount of noise to preserve user privacy. This advantage is offered at the price of trust in the central aggregator. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "e-MoffAIb7Jt",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "l6Qz9_YajUY6"
      },
      "source": [
        "### **Adversary**\n",
        "\n",
        "The nature of Differential Privacy is such that the epsilon-DP privacy guarantee holds even in the worst case.  \n",
        "\n",
        "Where the adversary knows everything about all the members of the database except the person of interest. And now it's up to the adversary to guess whether person-of-interest is in the database or not.  \n",
        "\n",
        "- DP ensures that no adversary modeling is required, as the DP guarantee caters to the worst case of adversary, where in, the adversary knows everything about the entire dataset, except the user of interest, and is still unable to infer anything.  "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "0qjqEdk2jUnG",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "qEU91bgGUmv_"
      },
      "source": [
        "### **Query Composition**\n",
        "\n",
        "privacy bounds when composing queries\n",
        "\n",
        "What happens when the same private database is queried multiple times? Are the privacy bounds compromised? Can we prove different theoretical privacy for this setting? Does the new bound depend on the number of queries? Can it be made independent of the number of queries?  \n",
        "\n",
        "**Basic Composition Theorem**\n",
        "\n",
        "Let $M_i : \\mathbb{N}^{|\\chi|} \\xrightarrow{} R_i$ be an $(\\epsilon_i, \\delta_i)$-differentially private algorithm for $i \\in [k]$. Then if $M_{[k]} : \\mathbb{N}^{|\\chi|} \\xrightarrow{} \\prod_{i=1}^k R_i$ is defined to be $M_{[k]}(x) = (M_1(x), M_2(x),...,M_k(x))$, then $M_{[k]}$ is $(\\sum_{i=1}^k \\epsilon_i, \\sum_{i=1}^k \\delta_i)$-differentially private.\n",
        "\n",
        "**Advanced Composition Theorem**\n",
        "\n",
        "For all $\\epsilon,\\delta,\\delta^{'} \\geq 0$, the class of $(\\epsilon,\\delta)$-differentially private mechanisms satisfy $(\\epsilon^{'},k\\delta + \\delta^{'})$-differential privacy under $k$-fold adaptive composition for:\n",
        "\\begin{equation}\n",
        "    \\epsilon^{,} = \\sqrt{2k ln(1/\\delta{'})}\\epsilon + k\\epsilon(e^\\epsilon - 1)\n",
        "\\end{equation}"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "tK62N-1mb7pb",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "4bD1lwPqbdep"
      },
      "source": [
        "### **Moments Accountant**\n",
        "\n",
        "The composability of differential privacy allows us to implement an “accountant” procedure that computes the privacy cost at each access to the training data, and accumulates this cost as the training progresses.  \n",
        "\n",
        "The moments accountant keeps track of a bound on the moments of the privacy loss random variable (dependent on noise added) using the strong composition theorem. The definition of $(\\epsilon,\\delta)$-DP is equivalent to asserting a tail bound on the mechanism’s privacy loss random variable."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "lBcjYTwwb8Zw",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elwxPg9vH54A",
        "colab_type": "text"
      },
      "source": [
        "### **Online DP**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LN4A1JDmH6Du",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "y4Yzp56QqEx4"
      },
      "source": [
        "### **Simple Use Case**\n",
        "\n",
        "Consider a sample database of people which stores their name and their age. This is a key-value database. We want to preserve the privacy of all the users in this database. The given database below has 5 elements and 5 neighbouring databases. \n",
        "\n",
        "Consider the count query. The difference in count() value of any two neighbouring databases is always going to be 1. Since the maximum possible value is 1, the sensitivity of the count query is 1. Thus, to make the count query differentially private, we need to add noise to the data proportional to the sensitivity of the query, which in this case is luckily quite low.\n",
        "\n",
        "\n",
        "Now we consider the sum query. The maximum difference in sum() value of any two neighbouring databases is going to be the maximum age in the database which happens to be 37 (Emma's age). Thus the sensitivity of the sum query is 37. Such an attack can leak Emma's private information, and hence, we need to add noise proportional to the largest value in the database. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "WEbHGSpeb9F6",
        "outputId": "415a3754-a8ff-43aa-c1a6-dc611d691380",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "db = {}\n",
        "db['Alice'] = 20\n",
        "db['Bob'] = 35\n",
        "db['Charlie'] = 27\n",
        "db['David'] = 26\n",
        "db['Emma'] = 37\n",
        "\n",
        "print(db)\n",
        "\n",
        "# neighbouring databases of 'db'\n",
        "\n",
        "nbr_dbs = []\n",
        "# print(len(db))\n",
        "# for i in range(len(db)):"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "{'Alice': 20, 'Bob': 35, 'Charlie': 27, 'David': 26, 'Emma': 37}\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "473PZqdGmDpE"
      },
      "source": [
        "## **Applications**\n",
        "\n",
        "- \"Medical Imaging: Preserving patient privacy without the need for being a privacy expert where datasets from multiple medical organizations are combined for more accurate and diversified training data.\n",
        "- Healthcare + Internet of Things (e.g. heartrate monitoring using smart watches): Local differential privacy allows us to collect and perturb data on the user's device to ensure privacy.\n",
        "- Genomics: Differential Privacy allows us to protect against linkage attacks (where information in a public database overlaps with a sensitive dataset) and help ensure privacy for preset queries. \n",
        "- Geolocation and travel data: Mask the location of individuals and travel data in databases.\n",
        "- [COVID-WATCH ](https://www.covid-watch.org/): Enabling privacy preservation for a contact tracing app. Third parties would like to aggregate statistics based on users private information (like location, age, number of contact points etc...), but the information cannot leave the phone.\"\n",
        "- DP in SQL databases\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "mJBvJTqIb95e",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4V4Ou0r5Ga-k",
        "colab_type": "text"
      },
      "source": [
        "### **Google's RAPPOR for Local DP**\n",
        "\n",
        "RAPPOR is a novel privacy technology that allows inferring statistics about populations while preserving the privacy of individual users. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UNA8ZMQ7GbPu",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "zs5lThV6mDtg"
      },
      "source": [
        "## **DP in Machine Learning**\n",
        "\n",
        "Removing outliers is a good idea for both accuracy and privacy.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "z6DwhabGE2gT",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RGT86V1vE2ol",
        "colab_type": "text"
      },
      "source": [
        "### **Deep Learning with Differential Privacy**\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "M-0HRzfHE2ye",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ywzY5g0pE26S",
        "colab_type": "text"
      },
      "source": [
        "### **DP Stochastic Gradient Descent**\n",
        "\n",
        "In the current era of deep learning, training loss functions are usually non-convex and difficult to minimize. In practice, we perform this minimization using the class of gradient-descent optimization algorithms, in particular, the mini-batch stochastic gradient descent (SGD) algorithm.  \n",
        "\n",
        "As described in Abadi Et. Al.'s Deep Learning with Differential Privacy, the key idea is to:\n",
        "- Clip the L2 norm of the gradients being computed\n",
        "- Compute the average\n",
        "- Add noise in order to protect privacy, and \n",
        "- Take a step in the opposite direction of this average noisy gradient.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "r8atxKyBb-_4",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "07XyFIPtmDyO"
      },
      "source": [
        "### **DP Image Classification**\n",
        "\n",
        "Let us consider the case of image classification. This makes preserving privacy more challenging, as adding a little noise to an image doesn't perturb it enough to make it anonymous, in the case of local DP.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "75dJuZ0_b_bQ",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "YelDGkItmEJd"
      },
      "source": [
        "### **DP Regression**\n",
        "\n",
        "lorem ipsum"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "ayMP98Ttb_7t",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "mOHK4FW0mDly"
      },
      "source": [
        "### **DP Clustering**\n",
        "\n",
        "lorem ipsum"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "mLxnlRnOcAa3",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "L7AQHZavWfWB"
      },
      "source": [
        "## **DP at OpenMined**\n",
        "\n",
        "- Wrappers for existing libraries  \n",
        "- DifferentialPrivacy.ts "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "5O1CeoZQcA3e",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "HepnFnB-l3Tt"
      },
      "source": [
        "## **DP in SQL queries**\n",
        "\n",
        "@Ria - this section is work in progress.\n",
        "\n",
        "Before we dive deeper, let's take a quick look at how we can transform a non-differentially private SQL query into a differentially-private query (this example is taken from [Chorus: Differential Privacy via Query Rewriting, p. 6](https://arxiv.org/pdf/1809.07750.pdf)):\n",
        "\n",
        "Below we have a query that returns a (non–differentially private) count of trips in the database. This query can be transformed into an intrinsically private query as follows:\n",
        "\n",
        "```\n",
        "SELECT COUNT (∗) AS count FROM trips\n",
        "```\n",
        "\n",
        "Note that we can use a uniform random variable to compute a laplacian random variable. The first step to transforming the query into an intrinsically private query is to sample from the uniform distribution (the RANDOM() function is used in SQL to do so) - we definine U as the resulting sample.\n",
        "\n",
        "```\n",
        "WITH orig AS (SELECT COUNT(∗) AS count FROM trips), uniform AS (SELECT ∗, RANDOM()-0.5 AS u FROM orig)\n",
        "```\n",
        "\n",
        "The next step is to use U to compute the corresponding Laplace noise, leading us to the intrinsically private query:\n",
        "\n",
        "```\n",
        "WITH orig AS (SELECT COUNT(∗) AS count FROM trips), uniform AS (SELECT ∗, RANDOM()-0.5 AS u FROM orig) SELECT count-( s/ε )∗SIGN(u)∗LN(1-2∗ABS(u)) AS count FROM uniform\n",
        "```\n",
        "\n",
        "\n",
        "### Common Relational Algebra operations:  \n",
        "\n",
        "Johnson, Near, and Song (2018) use a dataset from Uber consisting of 8.1 million SQL queries with data such as trip logs, rider and driver information, etc. They show that \"all queries in our dataset use the Select operator, more than half of the queries use the Join operator, and fewer than 1 percent use other operators such as Union, Minus, and Intersect.\"\n",
        "\n",
        "#### Core relational algebra:\n",
        "\n",
        "- Selection (σ)\n",
        "- Projection (π)\n",
        "- Join (◃▹), including arbitrary equijoins (including self joins) and all join relationships (one-to-one, one-to-many, and many-to-many)\n",
        "\n",
        "  - Johnson, Near, and Song (2018) found that equijoins are the most common type of join queries, which “are joins that are conditioned on value equality of one column from both relations.”\n",
        "\n",
        "- Counting (Count)\n",
        "- Counting with grouping (CountG1 ..Gn ).\n",
        "\n",
        "#### Queries with nested aggregations\n",
        "\n",
        "#### Additional common operations\n",
        "\n",
        "Additional common operations include:\n",
        "\n",
        "- from\n",
        "- where\n",
        "- group by \n",
        "  - GROUP BY Keys can be leaked and violate the differential privacy guarantees. Consider the following example: An attacker is trying to distinguish between two databases differing in only one record, which is a unique browser agent, that does not appear in D1, but appears once in D2. If the adversaries looks at the query output, they will be able to distinguish between the two databases using the GROUP BY keys irrespective of the value of the noisy counts since the record will appear in the query output for D2 but not for D1. A solution for this issue will be discussed in the next section. (Source: paraphrased from [\n",
        "Differentially Private SQL with Bounded User Contribution, p. 4](https://arxiv.org/pdf/1909.01917.pdf#page4)\n",
        "\n",
        "- sum\n",
        "- average"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "cchadziwk4Mg"
      },
      "source": [
        "Existing approaches used for ensuring differential privacy for SQL queries:\n",
        "\n",
        "**PINQ (and variations)**\n",
        "\n",
        "Advantages:\n",
        "\n",
        "Disadvantages:\n",
        "\n",
        "**Restricted sensitivity**\n",
        "\n",
        "Advantages:\n",
        "\n",
        "Disadvantages:\n",
        "\n",
        "**DJoin**\n",
        "\n",
        "Advantages:\n",
        "\n",
        "Disadvantages:\n",
        "\n",
        "**FLEX, which uses Elastic Sensitivity (discussed below) (https://arxiv.org/pdf/1706.09479.pdf)**\n",
        "\n",
        "Elastic Sensitivity\n",
        "\n",
        "TODO example of elastic sensitivity, and adding differential privacy noise, from paper\n",
        "\n",
        "Advantages:\n",
        "\n",
        "Disadvantages:\n",
        "\n",
        "Unsupported sample queries:\n",
        "\n",
        "```\n",
        "SELECT count(∗) FROM A JOIN B ON A.x > B.y\n",
        "```\n",
        "\n",
        "```\n",
        "WITH A AS (SELECT count(∗) FROM T1), B AS (SELECT count(∗) FROM T2) SELECT count(∗) FROM A JOIN B ON A.count = B.count\n",
        "```\n",
        "\n",
        "**Google's approach (https://arxiv.org/pdf/1909.01917.pdf)**\n",
        "\n",
        "Advantages:\n",
        "\n",
        "Disadvantages:\n",
        "\n",
        "**CHORUS (https://arxiv.org/pdf/1809.07750.pdf)**\n",
        "\n",
        "Advantages:\n",
        "\n",
        "Disadvantages:\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "olLg_Mi_kl0D"
      },
      "source": [
        "Resources (TODO description based on resources and gathering more resources):\n",
        "\n",
        "[Differentially Private SQL with Bounded User Contribution](https://arxiv.org/pdf/1909.01917.pdf)\n",
        "\n",
        "[Towards Practical Differential Privacy for SQL Queries](https://arxiv.org/pdf/1706.09479.pdf)\n",
        "\n",
        "[Chorus: Differential Privacy via Query Rewriting](https://arxiv.org/pdf/1809.07750.pdf) - \"The key insight of our approach is to embed the differential privacy mechanism into the SQL query before execution, so\n",
        "the query automatically enforces differential privacy on\n",
        "its own output. We define a SQL query with this property as an intrinsically private query.\"\n",
        "\n",
        "[Architecting a Differentially Private SQL Engine](https://people.cs.umass.edu/~miklau/assets/pubs/dp/ios19architecting.pdf)\n",
        "\n",
        "https://medium.com/uber-security-privacy/differential-privacy-open-source-7892c82c42b6\n",
        "\n",
        "https://medium.com/uber-security-privacy/uber-open-source-differential-privacy-57f31e85c57a\n",
        "\n",
        "/~https://github.com/uber-archive/sql-differential-privacy\n",
        "\n",
        "..."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "FnQE538Ml3a3",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "M5DcLdLZkQLP"
      },
      "source": [
        "## **Practical DP**\n",
        "\n",
        "### **Side-Channel Attacks**\n",
        "\n",
        "As explained above, DP pessimistically assumes that the attacker know all of the database contents except a single entry. \n",
        "\n",
        "However it also assumes that the only information gained by running a DP query is the query's output, and possibly the privacy budget consumed.\n",
        "\n",
        "This can lead to issues from 'side channels' where running a query gives an attacker more information than just the query result.\n",
        "\n",
        "The easiest way for this to happen is returning the privacy bugdet consumed when using a form of DP that ussumes just the result is returned.\n",
        "\n",
        "The next most common is through 'timing attacts' where the content of the database effects how long it takes a query to run.\n",
        "\n",
        "For example, a naive implmentation of sum above will perform a sum for every value above the one given and sum opperations take time.\n",
        "\n",
        "If we assume that the attacker knows every value in the database except one, then they can find its rank by seeing what queries take the time to run an 'extra' sum.\n",
        "\n",
        "Luckily these attacks can be mittigated in the code, and only matter for some use cases.\n",
        "\n",
        "For API's timing attacks matter. For researchers with full access deciding what results are safe to publish its not really an issue."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "NvqUzhplkQVG",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "p4mgWt3kerm1"
      },
      "source": [
        "## **Things no one tells you about Differential Privacy**\n",
        "\n",
        "- looking into trailing ends of distributions\n",
        "- bounds on data\n",
        "- bounds on query output\n",
        "- bounds on noise distibution\n",
        "- floating point error privacy leakage\n",
        "- laplace formula implementation from formula using own little function\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JYjWxJYy3Y2w",
        "colab_type": "text"
      },
      "source": [
        "@Ria: TODO incorporating information from Design_documentation.md in the typescript repo"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "YqQclh5Qx1jW",
        "colab": {}
      },
      "source": [
        "# looking into trailing ends of distributions\n",
        "# laplace formula implementation from formula using own little function"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "xAITQxIjXJNJ"
      },
      "source": [
        "## **Blog on DP**\n",
        "\n",
        "1. Introduction to DP with a simple use case\n",
        "2. DP noise mechanisms - what they are, strengths & weaknesses, when to use\n",
        "3. DP preserving Machine Learning\n",
        "4. DP preserving Deep Learning\n",
        "5. Practical DP\n",
        "6. Things no one tells you about DP"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "7jH770CRcDNl",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "lrxqbGbamWKG"
      },
      "source": [
        "\n",
        "\n",
        "## **Glossary**\n",
        "\n",
        "- **Local Differential Privacy:** Users perturb data before it is sent to a common server.\n",
        "- **Sensitivity of a Query:** The amount a query’s results change when the database changes.\n",
        "- **Global Sensitivity:** The maximum difference in a query’s result on any two neighboring databases.\n",
        "- **Local Sensitivity:** The maximum difference between the query’s results on a true database and any neighbor of it. \n",
        "- **Sparse Vector Technique:** Add noise and report only whether the noisy value exceeds the threshold. Privacy degrades only with the number of  queries which lie above the threshold, rather than with the total number of queries.\n",
        "- **DP  Online  Learning:** The goal in online learning is to design an algorithm that has the guarantee that \n",
        "  for all possible loss sequences $l \\leq T$ , even adversely chosen, the regret is guaranteed to tend to zero as $T -> \\infty$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "SfTkd0_tUo4s",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "0Lf-D759mSSu"
      },
      "source": [
        "## **Resources**\n",
        "\n",
        "- [Privacy-Preserving AI in Medical Imaging: Federated Learning, Differential Privacy, and Encrypted Computation](https://blog.openmined.org/federated-learning-differential-privacy-and-encrypted-computation-for-medical-imaging/)\n",
        "- [Use Cases of Differential Privacy](<https://blog.openmined.org/use-cases-of-differential-privacy/>)\n",
        "- [DP by Ted](<https://desfontain.es/privacy/>)\n",
        "- [DP at a Bird's eye view](<https://blog.openmined.org/privacy-preserving-ai-a-birds-eye-view/>)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "kbdHn9XXWN6K",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "3uqB0RrnPdxA"
      },
      "source": [
        "To do\n",
        "\n",
        "- Figure out a few different \"levels\" of definitions. \n",
        "The definition we have is extremely concise, specific and accurate but we will need to have a version of that sentence that makes sense for more mainstream/less-savvy audiences\n",
        "- Adding use cases: Likely we will add one around COVID-Watch as well, medical\n",
        "- Section for providing headlines on when/where to use the various perturbation mechanisms\n",
        "- Use DP at bird's eye view "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "rsO1kMytcEYL",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}