Programming exercise 1.

The goal of this exercise is to write a program implementing the
(exponential time) reconstruction attack we saw in class which you can
find described in Chapter 8 of the book DR linked from the course
webpage - you can also look at the original paper linked here:
http://www.wisdom.weizmann.ac.il/%7Edinuri/mypapers/db_privacy.pdf

More in details, the goal of the exercise is to define a
function "attack" which takes in input a dataset D consisting
of n records with 1 binary attribute and generate a database D’ which
is at hamming distance less than 4E from D. The function attack can
access the database D only using queries that are protected via
uniform noise with perturbation E=sqrt(n).

Test your attack by defining a function which checks that the dataset
that the function attack outputs is at most at hamming
distance 4E from D. I suggest that you repeat
this test on several datasets D. To make it feasible I suggest you to
use very small values of n, for example n=10 and n=12.

Please, summarize the results of the test with some plot that can be
used to visualize them (e.g. you could print the hamming distance for
each testcase, etc.)


Programming exercise 2.

The goal of this exercise is to write a program implementing the
algorithm RandomizedResponse that I presented - you can find it on the
slides. I remind you that in this algorithm the input q:X→{0,1} is a
predicate, and we are interested in the average number of record
satisfying this predicate.

Write a plotting function visualizing a bar plot comparing several runs of
this algorithm on two different datasets. In this case we want to see
that as we consider more and more runs of the algorithm the
privacy_loss variable tends to be experimentally bound by ϵ.
Additionally, we want some plotting function that could help us
visualize the accuracy guarantee. To do this, write a plotting
function that plot several output of the algorithm on a single
database, and a single query, set a threshold alpha based on values
of β accordingly to the accuracy theorem for differential privacy, and
use this threshold to show how many points are above or below the
threshold (counting them can also be helpful). Repeat several tests
for different values of the parameters: n, ϵ, β . 

NOTE: I am aware that the two programming exercises are not fully
specified, especially in the plotting part, and this is
intentional. Part of the exercise is trying to understand the concepts
of privacy and accuracy guarantees and how to manipulate them and I
think the best way to do this is by trial and error.

Requirements for the submission: please submit a zip file containing
both your code and few plots visualizing both the privacy and accuracy
guarantees.

Theoretical exercise 1

Suppose that we answer n counting queries q_1,...,q_n which are
eps-differentially private, using laplace noise and sequential
composition. Let's denote a_1,...,a_n the result of these queries on
the dataset D.

Prove that
Pr[max_i (|q_i(D) - a_i|> ln(k/b)*(n/eps) ] <= b

Theoretical exercise 2

Consider a noise addition mechanism similar to the laplace mechanism but where
we sample the noise variable Y from a distribution P_x defined on a bounded interval
[-x,+x] for some number x. That is:
Mech(q,D)= q(D) + y where y~P_x  (y is an element in [-x,x] with probability described by P_x)
Prove that this mechanism is not (eps,0)-differentially private for any real number eps.