hi everyone thanks Daniel for the
introduction so I'm very excited to be
here and today I will present our paper
when the signal is in the noise
exploiting the vixx's sticky noise first
I will give a little bit of context so
suppose you have a nice data set and you
would like to share this data set with
an analyst how do you make sure that the
analyst can analyze the data without
compromising the privacy of the people
who contributed with their data
well you could anonymize the data which
essentially means removing direct
identifiers from the records such as
phone number name and so on the problem
is that we know by now that
anonymization does not really work
because anonymous datasets can often be
reified so the issue with anonymization
is that in the end the analyst still
gets to see the individual level data
and she can do whatever she wants with
it and this is a problem and so we need
a safer solution and a possible approach
our data query systems so here the idea
is that the data is kept behind a
protected server and the analyst can
send queries to the server and get
results they in return but what if the
analyst is malicious in this case the
analyst could try and send queries to
infer sensitive information to extract
summited sensitive information about a
single individual in the data set so
intuitively you would like to allow only
queries that perform some kind of
aggregation however in practice this is
not easy to do for example consider the
following query how many people named
Bob have a salary less than 2,000 pounds
of course you would like to block this
kind of query and more generally you
would like to block any query that
selects a small number of users in the
data set however such a man
is easily circumvented by using two
queries the first one is how many people
have a salary less than 2,000 pound and
the second one is how many people not
named Bob have a salary less than 2,000
pounds and of course what these two
queries could wouldn't select many users
so they would be allowed but by taking
the difference in the output this can be
either 0 or 1 depending on Bob's salary
this is called a different difference in
attack but many more attacks are known
in the literature so a core idea to
protect against these kind of attacks is
randomness addition and here the idea is
that the data curator adds a little bit
of random noise to the output before we
listen them to the analyst and the noise
could be for example drawn by from a
normal distribution centered in 0 so
that the the small smaller values of the
noise are more likely to be extracted
however implementing noise addition is
not easy
and indeed in 2003 dinner and Nixon
proposed the first reconstruction attack
and without going into details they
showed that if the noise is not enough
then an attacker can reconstruct the
full dataset in polynomial time and
since then data has been generalized and
improved many times so how can we add
enough noise and how can we do so what's
the right way to add noise so a possible
answer is given by a differential
privacy which was proposed in a 2006 and
I'm sure many of you have heard about it
already so differential privacy is a
very broad topic and it's very hard to
make statements that are a hundred
percent correct but I think that most
people would agree that differential
privacy has positive and negative
aspects on the upside it gives
meaningful improvable guarantees of
privacy
and it provides a mathematical framework
to reason about the privacy utility
trade-off on the other hand au courant
differential privacy mechanisms often
add too much noise to the outputs making
utility pretty bad and moreover it's
pretty hard with differential privacy to
allow many queries to the analyst and to
provide good usability and flexibility
in the platform for the analyst and for
these reasons people have been starting
to look for alternatives to differential
privacy that are perhaps not based on
mathematical guarantees of privacy but
rather on heuristics and the fix is one
of them so the fix is a patented
commercial system developed by the
company err clock and some researchers
at the Max Planck Institute for software
systems and specifically D fix is a
privacy-preserving database system that
in practice operates as an SQL proxy
between the analyst and the database and
diffict provides some unique features
such as are its SQL syntax little noise
added to the outputs and infinitely many
queries allowed to every analyst and
these features are precisely meant to
address the limitation of the
limitations of differential privacy so
the way we fix protects privacy is by
means of a novel noise addition
mechanism that they call sticky noise so
here is how it works so suppose that an
analyst submits account query Q to D fix
such as this one that selects all the
users with condition which satisfy
condition one condition two and so on so
the fixes output to this query would be
the true count of the query plus static
noise plus dynamic noise so without
going into the details of how these
noises are computed the main ideas are
that first static the static
depends only on the query syntax of Q
the dynamic noise depends on the query
syntax and also on the user set of Q
which is the set of user IDs that are
selected by Q in the data set and both
noises are sticky which means that
repeating the same query to the fix will
always give the same nice value for that
query so another thing that to keep in
mind about the fix is that both the
static noise and the dynamic noise are
made of smaller noise values and
specifically one per condition so for
example in a query with three conditions
we would have that the output of the fix
is the true count plus three noise
values for the static noise and three
noise values for the dynamic noise and
it's noise value is drawn from a
standard normal distribution so in the
paper that describes defects the authors
explain why this mechanism protects
against some known some attacks that are
known in the literature and also the
they explain they present other measures
that are implemented in the fix but I
will not cover them in in this
presentation okay so we I can finally
present our attack or noise exploitation
attacks on D fix and the reason why we
call them noise exploitation is that
they actually exploit the fact that part
of the noise defects ads actually
depends on the data and we can use this
as a signal for sensitive information so
here is the attack model first we take a
data set that has the attributes and
particularly the last attribute is as
secret attribute and the attacker
targets one user at a time which we call
Bob and the attackers goal is to infer
Bob's
at Bob's secret attribute s so for
simplicity here we assume that the
secret attribute is binary but actually
can be generalized to non-binary
attributes we also assume that the
attacker has some auxiliary information
about Bob first she knows that Bob's
record is in the data set and second she
knows that the value she knows the value
of K attributes about Bob and here's an
example with D equals three and K equals
two so as before we can have that the a
data set that includes attributes age
department and high salary the secret
attribute would be high salary and Bob's
record would be as equals 40 compute
apartment equals computing and high
salary equals true but what the attacker
would know is only that Bob is four
years old and is in Department of
computing and she would like to find out
that Bob has high salary equals true so
here's our first attack which we call
differential attack and assume that Bob
is the only person in the data set which
is four years old and is in the
department of computing then we would
issue the two queries that you see at
the top we would get the answers from
defects with the noise and we would
consider the difference between the two
outputs so q1 minus q2 would be of
course the difference between the true
counts plus all the noise layers for q1
and all the noise layers for q2 and this
is quite a bit of noise but actually
with a little bit of work we can see
that some of the noise layers are the
same and actually we more even more
interestingly we can see that some nice
layers cancel out depending on Bob's
attribute specifically if Bob has high
salary equals true then for static noise
layers cancel out but if bob has has not
high salary then also for dynamic noise
layers
cancel out so what this means is that q1
minus q2
you follows two different distributions
depending on Bob's secret attribute high
salary and specifically it follows
distribution a normal distribution with
mean zero and C and a standard deviation
two if high salary equals true and it
follows a distribution a normal
distribution with mean one and standard
deviation 2k plus two if the high salary
is false and here K again is the number
of attributes known to the attacker
about the victim so in practice the
differential attack has several
limitations and the main ones are that
first it assumes that Bob is unique in
the data set and second some attack
queries are likely to be suppressed by
an additional measure that diff
exploiting put in place and I didn't
explain so ultimately this means that
the accuracy is not great in some cases
for this attack and this is the reason
why we developed a second attack and
improve the attack which we call cloning
attack which achieves much better
accuracy so unfortunately I will not
have time to describe this attack
because it's quite complicated but I
would like to mention that it relies on
a weaker notion of uniqueness that we
named value uniqueness so we say that
our record is value unique with respect
to a set of attributes if all records
sharing the same attributes also have
the same secret attribute and you can
see an example here so the first record
which is Bob's record is value unique
because it shares the same age and
department attributes with the second
record and it also shares the secret
attribute high salary because it's the
same on the other hand the last record
alice's record is not val unique because
the high salary attribute is not the
same between the 3rd and
the fourth record I would also like to
clarify that we do not assume that the
attacker knows that Bob's record is
value unique this is because actually
value uniqueness is detected
automatically by our cloning attack with
pretty good confidence and here are the
results of the cloning attack on three
real-world data sets and one synthetic
data set so on the x-axis you have the
number of attributes known to the
attacker about the victim and on the
y-axis you have the fraction of all
records in the data set so the gray line
indicates the fraction of value unique
records and so you see that as K grows
almost all users become value niek and
the black line is the fraction of users
in the data set that are attacked and
correctly inferred and you can see that
for larger numbers of non large numbers
of known attributes the number of
correctly inferred users goes almost up
to the entire data set around 90% of all
users so this the de Kooning attack in
its original form uses about a few
hundred queries for its user but
actually we modified the attack in a way
that targets about half of the users in
the data set but can work with as little
as 32 queries per user and that's you've
still almost perfect accuracy so air
clock proposed paths for our attack and
the path is supposed to be implemented
in defects by the fourth quarter of this
year so the paths essentially removes
dangerous conditions from the queries
and it does so in a way that again
depends on the data and so the technical
details are not yet available for their
paths but our comment is that in our
opinion
the patch does not really address the
core vulnerability that we pointed out
in our attacks namely that data
dependent noise leaks information about
the data and potentially this patch
introduces new vulnerabilities because
it is again data dependent so I'd like
to mention that other attacks have been
proposed on addy fix the first one is a
membership attacked by jollies and
others and it is based on a previous
paper that they published in and ESS in
2019 the second one is a linear
reconstruction attack by kana Cohen and
miss him and actually this is based on
the original attack from 2003 but it was
actually tweaked quite a bit to work
against defects so to conclude we think
that data query systems are the right
response to the failure of anonymization
and they are the way forward for privacy
preserving their publishing however we
think that incorrectly implementing data
query systems is hard and for this
reason we rely on a single mechanism to
protect privacy such as sticky noise is
risky so we believe that deployed system
should also implement some defense in
that measures such as for example
pre-audit in query rate limiting and so
on but also we think that alternatives
to differential privacy are useful and
actually a system like the fix with some
modification can achieve a reasonable
privacy utility trade-off in some
settings especially in trusted
environment of course in all cases
transparency is fundamental to give the
researchers the possibility to study the
system and assess potential
vulnerabilities and actually we welcome
the fact that Eric lock decided to
publish
in publicly the specification of defects
and we can we hope that they will
continue to do so in the future thank
you for your attention and I'll be happy
to take any questions you may have
[Applause]
[Music]
thanks for the presentation so is it
easy to generalize your technique so
that you can recover non-binary
attributes yes so it's a relatively easy
one of the possible ways to do this is
by replacing the last condition with sex
whether exactly the exact value of the
condition with actual and inequality and
then essentially narrow down the with
inequalities today to the right
attribute of course this might require
more queries but actually the fix is
implemented in a way that allows
infinitely many queries so this is a
this would be actually possible
yesterday photos was not in this area
I'm wondering if you can give us a sense
of the impact of this what types of
systems use this kind of setup like who
are customers of this company that
provides defects so the the customers
for defects are not publicly available
but we think that it might be primarily
companies that would like to share data
across different departments of the same
company we are not sure but this is our
guess so
yeah this would be probably I mean this
is this for the moment at least this is
not used to share data as open data for
example okay thank you very much not
around here class
[Applause]