# Homework 11

## Exercise 1: [attack] What are Donald's Favourite Movies?
You have learned in class that it is possible to deanonymize most kinds of “anonymized” datasets. It
just happens so that you have obtained several datasets containing "anonymized" movie ratings. They
are databases stored as csv-files (`com402-i.csv` where `i` is the subexercise number) in the following format:
```
sha256(salt | email), sha256(salt | movie), date, rating
```
The salt is the same within each database. We call these the “COM-402 databases”.

The emails and the movies in the databases are hashed, so they are perfectly private, right? Let's
see if you can circumvent this protection mechanism. To de-anonymize a database, you also get
csv-files with publicly available ratings from IMDb (we call them “IMDb databases”, `imdb-i.csv`) in the following
format:
```
email, movie, date, rating
```

The entries in an IMDb database are a strict subset of the entries in a corresponding COM-402
database. Hence, there is some overlap between the ratings in an anonymized dataset and the
public dataset.

Your goal is to find out what movies a user with email `donald.trump@whitehouse.gov` has rated.
**Disclaimer:** Any coincidences with real people are accidental.

You have three sub-exercises of increasing difficulty, the third being optional (we will not ask
questions about it). Each exercise comes with its own pair of anonymized and public databases.  You
can solve each exercise in any language you like, even paper and pencil if you’re not afraid of
searching for overlaps in 200 emails.

To check the correctness of your answers, you can find the correct output of each subexercise `i` under the `user-i.csv` files. 

### 1. Dates are giving it away
Each user rated the movie at the same date in both the anonymized
COM-402 and public IMDb database.
Database files: `com402-1.csv`, `imdb-1.csv`.

**Hint:** some dates might have more than one rating, so you need to make sure you remove these duplicates.

### 2. More realistic
Here the dates and ratings are random, reflecting the fact that you might not rate a movie on Netflix and on
IMDb on the same day. However, a simple frequency attack on the movies is enough to map the movies
to the hashes. Database files: `com402-2.csv`, `imdb-2.csv`.

**Hint**: First match the movie hashes to their plaintext names by frequencies in the anonymized and
private dataset.

**Hint:** Once you have mapped the hashes of the movies to the plaintext names of the movies,
try to find the Donald's email hash.

### 3. Even more realistic (optional)
Here the dates of ratings in the COM-402 database and IMDb are not the same, but similar. Dates are
within 14 days, and are following a triangular distribution using Python’s `random.choices` and
weights: `[1, 2, …, 14, 13, …, 1]`.

Database files: `com402-3.csv`, `imdb-3.csv`.

**Hint:** First search for email hash/plaintext overlap and fit those to find the hash of the
victim's email. Then you can search for the closest overlap of the public ratings and the
anonymous ratings of your email.

## Exercise 2: [defense] Differentially Private Queries 

This time, you play the role of a company that collects movie ratings, e.g., IMDb, and you want to
securely disclose them.  You have a rating database in clear, where each row has the format `[email,
movie, date, rating]`. By now you know well that creating anonymized datasets is very hard, so
releasing a database with pseudonymized (e.g., hashed) identifiers is not an option. You still want
to enable researchers to learn some useful information from your database, but not at the cost of the
privacy of your users. Hence, you decide to allow the researchers to send you queries that you can
respond to in a differentially private way. This should help preserve the privacy of your users
while still allowing the researchers to learn some insights about the data.

You allow counting queries of a certain format. The researchers should be able to get the number of
people who have rated a given movie greater than or equal to a certain level. If you were to express
this in terms of SQL:

```sql
SELECT COUNT(*)
FROM db
WHERE movie = [queried movie name]
      AND rating >= [queried rating level]
```

This will enable them to learn which movies are rated well and which ones are not. As this is a
typical example of a count query, you search online and learn about the [Laplace
mechanism](https://en.wikipedia.org/wiki/Additive_noise_mechanisms) which ensures differential privacy
(DP). The Laplace mechanism works as follows: to satisfy epsilon-DP, to each response
you will add some noise drawn from Laplace distribution $Lap(b)$. The scale parameter $b$ of the distributaion depends on two things:

1. the sensitivity $\Delta f$ of the count query, characterized by your input (see hint below)
2. the (requested) $\varepsilon$, requested at query time 

Namely, $b = \frac{\Delta f}{\varepsilon}$.

When a user/researcher makes a query, instead of simply answering it directly, you will therefore answer 

$A(q,\varepsilon) = f(q) + Lap(\frac{\Delta f}{\varepsilon})$

where $f(q)$ is the "ground truth" answer for the query.

The researchers pass a thorough vetting process, so you can safely assume they do not collude: will
not share outputs they receive with each other. Each researcher gets their own **privacy budget**:
the total epsilon for all the queries of this researcher. With each individual query the researcher
specifies what value of epsilon should be used for the query. The lower the epsilon, the more noise
will have to be added to the response (and more privacy the users will have). The higher the
epsilon, the more accurate the will response be. Each query will always have to be within the
total epsilon budget of the researcher.

To implement this querying system, you have to code up a class `DpQuerySession` with a property
`remaining_budget` and a method `get_count`. Start with the following annotated template in `dp.py`.

This is an example of using the `DpQuerySession`:
```python
querier = DpQuerier("imdb-dp.csv", privacy_budget=1)
count = querier.get_count("Seven Samurai", rating_threshold=3, epsilon=0.25)
```

**Hint:** In your database, a user can only rate one movie once. This assumption allows you to
compute the sensitivity $\Delta f$ of a single query.

**Hint:** The sequential composition property states that if algorithms A1,  A2, …,  Ak use independent randomness and each  Ai satisfies εi-differential privacy, respectively. Then (A1,  A2, …,  Ak) is (ε1+,ε2+...+ εk)-differentially private. Use it to figure out how to keep
account of the privacy budget and ensure that the queries do not exceed it!

### Verifying your implementation

You can use the `verifier.py` script to test several aspects of your solution. Simply run it in the same directory as your `dp.py` file. We recommend not directly looking at what the `verifier.py` tests, but rather reasoning with your code directly :)
