Latest / Strachey Lectures / Strachey Lecture: How Can Algorithms Help to Protect our Privacy

Transcript

Strachey Lecture: How Can Algorithms Help to Protect our Privacy · Strachey Lectures

• 0:11
  Thank you. Thank you, Leslie, for this very kind introduction.
• 0:14
  And thank you very much for inviting me to come here. I'm really excited to be here.
• 0:18
  And, uh, yeah, to tell you a little bit about differential privacy in general and about my research then specifically in this field.
• 0:27
  So the talk, as we say, is should be algorithms who protect the privacy.
• 0:32
  So algorithms, you know,
• 0:33
  are everywhere these days because every computer program and also every integrated circuit is actually implementing an algorithm.
• 0:41
  And so if you use your phone or your laptop or your home appliance or your car or your cleaning robot or certain medical devices, um,
• 0:51
  you will obviously have algorithms running there, and they're usually very useful,
• 0:56
  but they can also collect data about you right now, data is also collected in other ways.
• 1:02
  For example, governments collect data about their citizens.
• 1:06
  In the U.S., for example, they do a census every ten years.
• 1:10
  Or if you participate in research studies, there will also be data collected about you.
• 1:15
  Um, this data is usually collected for a certain purpose.
• 1:18
  So for example, governments collect data so they can decide how to distribute funds who are not.
• 1:24
  So uh, um, also insurances use it to decide, you know, how much it costs you to costs to insure you banks to make loan decisions or, uh,
• 1:36
  doctors use, uh, AI algorithms right now in order to decide whether they should do certain medical procedures on you or not on your phone.
• 1:47
  Um, if you use, for example, Google keyboards, they suggest word sentence completions.
• 1:54
  And that's usually done, um, based on data that is collected by their users.
• 2:00
  So in general, this sounds like it's great. There's certain usefulness in this data.
• 2:05
  So there's this utility. But on the other side, of course, immediately comes to the concern.
• 2:10
  What about our privacy? So you have two conflicting goals. On the one side, you can use this data to do something useful in the world.
• 2:16
  Um, but on the other side, how can you protect the privacy?
• 2:20
  And this is really the goal of these algorithms that I will be talking about.
• 2:24
  So they want you. They want you to be able to use the data, but in such a way that the privacy of the individuals is protected.
• 2:31
  And try to explain to you how they are trying to achieve that.
• 2:37
  Um, now, what are the challenges for, uh, privacy?
• 2:40
  Uh, there's actually one challenge. Let me start with a second one here. Uh, one simple challenge is already that statistics.
• 2:47
  If your database gives you exact data, might already leak a lot of information.
• 2:52
  For example, if we know the average salary of the people in this room, and then one person leaves,
• 2:58
  and then I give you the average salary, again, you can easily figure out if you know how many people were here.
• 3:02
  You can easily figure out what was the salary of the person leaving. Right. Some simple math.
• 3:07
  Um, so in general, by giving exact answers, you might already leak a lot of information that you might not want to leak.
• 3:13
  Um, even worse in machine learning. Very often this, uh, algorithms actually memorise data.
• 3:21
  So, um, for example, there was some paper in 2018 by collinear oil where they showed that the Smart Compose,
• 3:28
  which is the sentence completion in Gmail,
• 3:31
  uh, was leaking the Social Security number of one of the users, okay, because they had used training data that had that information in it.
• 3:38
  And it's happened to learn that by heart. So how can you deal with this?
• 3:43
  Well, so the first idea that people had was to say, oh, why don't we just anonymize data?
• 3:48
  Isn't that good enough? Yeah. So I might release data, but I just don't put the names.
• 3:53
  And there are all kind of famous examples that showed that this was a bad idea.
• 3:58
  One of them was, uh, uh, published by Narayan and Sharma Cough in 2008.
• 4:06
  Um, what they did was they used data that Netflix had published, so Netflix had published.
• 4:12
  Uh, so here every row was a user and every column was a movie.
• 4:17
  And so the information was whether this user liked this movie or not.
• 4:21
  And they had anonymized the data by removing the names of the users.
• 4:26
  But what these authors showed was, oh, if you combine this information together with some public information that the Internet Movie Database had,
• 4:36
  because many of the users that gave their information to Netflix or the then published on the
• 4:40
  Internet Movie Database saying which movies they watched and whether they liked them or not,
• 4:45
  and they gave their names. And so if you combine these two data sources, uh, they were able to actually figure out the names for many of the users.
• 4:54
  And they showed that basically, on average, four movies uniquely identify a user.
• 4:59
  Okay, so it's a bad idea to just anonymize the data.
• 5:03
  Because if you combine different sources, you might be able then to de anonymize it.
• 5:09
  Okay. So. So the first idea doesn't really work by itself.
• 5:12
  Of course you have to anonymize, but you have to do more.
• 5:15
  And so we what it also shows us this example is that we need techniques that can handle composition of data sources.
• 5:22
  Yeah. When you analyse what happens if you combine different data sources.
• 5:26
  So here are the two data sources the Netflix in the Internet Movie Database.
• 5:32
  And then the second idea, the researchers, which was cannot be generalised to randomised response.
• 5:37
  Now let me explain to you what is randomised response. And then I will explain to you how they generalised it.
• 5:44
  So randomised response is a technique which was invented by Varner, a sociologist,
• 5:49
  in the 1960s, and this has been used ever since without any big privacy concerns.
• 5:55
  Okay. It's a good knowledge, um, to have.
• 5:58
  And so for later in the talk. And so it has it solves the following problem.
• 6:03
  Assume you have some population and you want to find out what percentage P of
• 6:08
  the population has property A now property A might be something embarrassing.
• 6:13
  You don't wanna admit that you have property A like snoring at night, for example.
• 6:17
  Uh. Worst things. Yeah, I leave it up to your imagination.
• 6:20
  So nobody wants to imagine that they have prob ever wants to admit that they have property.
• 6:24
  A still you want to find out what percentage P of people has this property.
• 6:30
  And now here is a solution that Warner came up with. So you have your volunteers who participate.
• 6:37
  And instead of asking them whether they have the property or not, they would just lie to you.
• 6:41
  You ask them to run this simple algorithm. So they should first throw a coin and not tell anyone about the outcome of the coin flip.
• 6:49
  And then if it was hit, then they should answer truthfully.
• 6:53
  If it was no, it was not hit. Then they should throw the coin again.
• 6:58
  And now they should just answer according to the coin throwing.
• 7:01
  So if it was, heads say yes and otherwise say no. Okay, but they should not tell anyone, uh, how often they threw the coin.
• 7:09
  They should not tell anyone the outcome of the first coin flip. Okay.
• 7:13
  That's the private information. And so they should just give this information back now.
• 7:18
  Yes or no depending on this algorithm. And then what you do is you determine the percentage Q of yes.
• 7:24
  Answers from this algorithm. And then you output two times q minus at half as estimate for p, the two answer.
• 7:33
  And it turns out that this is an unbiased estimator for the true answer.
• 7:37
  So it will give you a good estimate. Now why does this also pursue privacy?
• 7:43
  Well, because you have what's called plausible deniability.
• 7:47
  So everyone has to answer yes with probability at least the fourth.
• 7:51
  If you have the property, then you will answer yes here with probability half here and then here.
• 7:57
  Or as it was probably half, you said no and then again with probability a half. So all together with probability fourth you will also answer yes here.
• 8:03
  So if you have the property you will have a probability of three fourths of answering.
• 8:07
  Yes. If you don't have the problem with the property, you will still have probability of one fourth right of entering.
• 8:15
  Yes. So everyone has a probability of at least the fourth of entering.
• 8:18
  Yes. So if you answered yes and then I come to you and say, oh, you have property, I, you can say, no, no, no, I actually don't have it right.
• 8:25
  It was just the coin flips, not me. It's a coin flips.
• 8:29
  Right. You can blame the coin flips for you, I answer, and nobody can prove you otherwise.
• 8:34
  Okay, so it's private. And note also that you need randomisation.
• 8:39
  Without randomisation, this would not work right that you need to keep private for yourself.
• 8:44
  Okay, but randomisation is very important. Okay.
• 8:47
  So now the question was how can we make this more formal and more general.
• 8:52
  And that's exactly what differential privacy does. So it's a mathematically rigorous definition.
• 8:56
  You will see it in a second. Um and it measures the privacy protection given by an algorithm.
• 9:03
  And the goal is, first of all, to make it very unlikely that if you combine, uh, that user data can be reconstructed.
• 9:11
  If no matter how many data sources are combined.
• 9:15
  It gives you a way to measure how much impact on your privacy the combination of data sources has.
• 9:21
  And then you can have a threshold and say I'm only allowing so much privacy loss.
• 9:25
  And if this combination would be a profit, then I'm not allowing this combination.
• 9:29
  Meaning I'm not giving out my data anymore.
• 9:32
  Um, and it also gives a prime, a parameter that tells you for each algorithm how much data leakage stays, how much privacy loss stays.
• 9:43
  And there are several current deployments. And I'll talk about this, uh, later in the talk.
• 9:48
  Okay. So now let me give you the informal definition before giving you the formal definition.
• 9:53
  The informal definition is as follows. So assume you have a database and it has a thousand people in it.
• 9:59
  And you ran some randomised algorithm on it. Maybe computing the average salary or something okay.
• 10:05
  And so you run some randomised algorithm on it and it gives you some noisy answer.
• 10:10
  Okay. Noisy meaning because there was some randomisation involved. And now assume that you have the same database except the last person has changed.
• 10:19
  There is no person 1000. Everything else is the same. And now you run the same algorithm on it.
• 10:25
  And you also get a noisy answer.
• 10:28
  And now what you want is that you should return the same answer for D and for B prime, with almost the same probability.
• 10:36
  So mathematically speaking,
• 10:39
  the first the algorithm executed on the first database gives you some probability distribution on the output potential outputs it.
• 10:46
  And the one on the second input gives you another probability distribution.
• 10:51
  And what you want is that this probability distributions are very close, very similar.
• 10:57
  So it's some kind of smoothness requirement on the output of the algorithms.
• 11:01
  Okay. So if the inputs are very similar like here, they only define the last person.
• 11:06
  Then the output distributions for your answers should be very similar.
• 11:12
  Okay. And if this is the only thing you remember from this talk. You got it.
• 11:16
  Okay. I will have it again on a later slide.
• 11:20
  Now, why is this? Why is this a good definition?
• 11:23
  Well, because then, based on the answer of the mechanism, it is very unlikely that you can distinguish between d or d prime,
• 11:31
  that you can figure out that the input was d, or that the input was d prime.
• 11:35
  You will not be able to distinguish because the output distributions are so close.
• 11:39
  It would be very unlikely that you can distinguish I should say. Okay.
• 11:43
  That's the idea behind it. Now, more formally speaking, um, so we say two inputs are neighbouring.
• 11:50
  If they define at most one entry and other be more formal in the next slides because it depends on the application.
• 11:56
  What does it mean? One entry. Okay. And so epsilon is some number larger than zero.
• 12:02
  And now we say a randomised algorithm. Sometimes they call it mechanism A with a set p of possible outputs.
• 12:11
  Is epsilon differential private. So p is all possible outputs.
• 12:14
  Is epsilon differential private if for all possible subsets S of P and all possible neighbouring inputs D and D prime,
• 12:23
  the probability that the mechanism started on t outputs S is at most e to the epsilon
• 12:30
  times the probability that a mechanism with uh input d prime outputs an element of s.
• 12:37
  That's why I gave you the informal definition beforehand, because this is somewhat of a mess.
• 12:41
  Yeah. But let me try to interpret this. So Epsilon you should think of as a small number close to zero.
• 12:47
  So e to the epsilon is just a little bit larger than one. Okay.
• 12:51
  So what you want is the probability. And instead of saying element of s you can just think for simplicity here.
• 12:57
  Um, that's is just one element of P. And that this is equal to S.
• 13:02
  It makes it easier. So you can think the probability that the mechanism outputs an element of S is almost the same.
• 13:10
  If you the input was d, what if the input was d prime.
• 13:15
  That's what this definition says. And the randomness here, I should emphasise, is only over the randomness of the here,
• 13:22
  for the probability is only over the random choices of the algorithm.
• 13:26
  Okay, the input is worst case. We are saying for all possibility and d prime okay, there's no input distribution.
• 13:33
  This is only on the randomness of the algorithm.
• 13:38
  And of course, because we say for all possible neighbouring D and D prime, you can also by symmetry exactly get the inverse statement right.
• 13:45
  So you get that the probability then you started on D prime is a most e to the epsilon times higher than the probability when you started on D.
• 13:53
  So really what you get is an upper and a lower bound for the probability.
• 13:57
  When you started on D it's upper bounded by at most e to the epsilon times the
• 14:02
  probability for d prime and its lower bounded times e to the minus epsilon.
• 14:06
  And so if epsilon is small close to zero then this is roughly one.
• 14:11
  And it gives you a good privacy guarantee.
• 14:14
  Now, uh, one thing, however, you should keep in mind that in practice, Epsilon is not a small nor close to zero.
• 14:21
  Uh, you think of epsilon is more like 7 or 8 when used by companies.
• 14:26
  So E to the epsilon is already pretty big. But even worse, in the US census they used epsilon equals 19.
• 14:34
  So you might argue well you know this has probability over individuals.
• 14:39
  And you know that 300 million Americans, the accountant blah blah blah.
• 14:42
  But then you only count a subset of them anyway. And so but still, you know, e to the 19 seems like it's a big number.
• 14:50
  Okay. But in theory epsilon is small, close to zero.
• 14:56
  Okay. And so the crucial thing is, uh, this definition of neighbouring.
• 15:00
  Right. So we have this constraint on the probability distributions for neighbouring data sets.
• 15:07
  Okay. So here again this is the one thing you should remember from this talk is differential privacy
• 15:12
  means there's a strong requirement on the output distributions for neighbouring inputs.
• 15:17
  The sort of a smoothness requirement. They need to be very close. And this is completely different from anything I've seen in algorithms before.
• 15:25
  Okay. This was not studied before. And that's why this is also such an interesting research area.
• 15:29
  If you had not thought about such kind of algorithms before.
• 15:34
  Okay. Now why is this useful to have this definition? So now I can informally.
• 15:40
  So assume that the use of data AI is used in database D, but not in D prime.
• 15:47
  Then. Now you could write down. Well, what is the harm for a user ie.
• 15:52
  If the output was a s and you can multiply this with the probability that the output was s, and now you can sum over all possible s.
• 16:00
  So here you get the exact expected harm that you have.
• 16:04
  If I say data was used in the database.
• 16:08
  And here you can do the same thing for D prime D primaries where ice data was not used.
• 16:14
  And now because you know this bound here, you know that this expect the term here um is a multiplied with e to the epsilon is
• 16:21
  an upper bound to the harm that you get if the data was used okay or was differently.
• 16:27
  Any harm for user I that happens with the inclusion of data.
• 16:31
  I is that most effect that e to the epsilon higher then the harm the expected harm without ice data.
• 16:39
  Okay. So your. This definition is useful because you can found the expected harm that you have by being included.
• 16:47
  And again epsilon close to zero is good. Epsilon 19 might not be quite as good.
• 16:53
  Okay. And each of the epsilon is called a risk multiplier.
• 16:57
  Okay. So now, what is a good definition of neighbouring?
• 17:01
  Uh, now, especially in the early days, people in differential privacy mostly looked at databases, which they thought of as tables.
• 17:08
  Okay, so they saw the tables. So you have some table.
• 17:11
  Every row is a user and every column tells you something about the user.
• 17:15
  And then the standard definition of neighbouring goes to databases are neighbouring.
• 17:19
  If they define at most one row okay. So one user is different.
• 17:26
  But, um, then they said, isn't this maybe too generous?
• 17:29
  And they restricted it more. And they say two databases are neighbouring.
• 17:33
  If they differ only in the inter entrance for one row, so one entry in one row is different.
• 17:40
  What even more restrictive one entry in one row differs by at most one.
• 17:47
  Okay. And so as you notice, these definitions of neighbouring become more and more specific.
• 17:53
  And thus the requirements become less and less strict.
• 17:56
  Right. Because you're only required to have very similar distributions if you're neighbouring,
• 18:02
  if you're neighbouring here in this one, in this way you also neighbouring here and you also neighbouring here.
• 18:07
  While there are cases where your neighbouring here and not neighbouring here.
• 18:10
  So here you have more requirements because you have more neighbouring relationships than down here.
• 18:16
  Okay.
• 18:17
  And now, uh, people have studied this kind of different kind of, uh, requirements because depending on the application, that might be more suitable.
• 18:25
  And you may be able to get better balance down here.
• 18:29
  Now balancing both. Well, we'll get to that in a second.
• 18:32
  In the error that you get. Okay. So there are epsilon differential private algorithm for all of this.
• 18:39
  But the error on second formalise error.
• 18:42
  The error is better if the if you have fewer constraints can you handle a smaller.
• 18:47
  You will get a smaller error. You might also look at graphs.
• 18:52
  Think of social networks. Uh, each graph, you know, each user is a node.
• 18:56
  If there's a friendship relationship, you have a link edge.
• 19:01
  And now you could look at vertex neighbourhood of graphs. There are two graphs are neighbouring if they define at most one node.
• 19:08
  Or you can say h neighbouring where the nodes are actually known.
• 19:12
  And you want to protect the privacy of the edges. And so you say, uh, two graphs are neighbouring if they define one edge.
• 19:20
  And well, you could just say that neighbouring if you have weighted graphs, the graphs are actually known but the weights are not known.
• 19:26
  And so only the weight of one edge can differ. Okay.
• 19:30
  Um. So say it. You know, this way, while I was talking, the notion of neighbouring is very closely related to what you are protecting, right?
• 19:38
  So if you're only protecting the weights of the edges, um, then you're not protecting anything else.
• 19:44
  You're not protecting the nodes or the edges in the graph, meaning they might just as well be publicly known.
• 19:50
  If you're each neighbouring, then the nodes might just as well be publicly known because you're not protecting them.
• 19:55
  You're only protecting the H relationship. Who is in relation with whom.
• 19:59
  And if your vertex neighbouring this is the strongest again, then you're protecting even the nodes in the graph.
• 20:05
  Okay, so what do you protect? You mean what you want to protect immediately carries over to what?
• 20:11
  Your definition of neighbouring.
• 20:12
  And depending on your definition of neighbouring, the more was the more strict or the less strict to this it carry carryover to how much era you need.
• 20:20
  And since there's so many possible applications and combinations of what what this right definition of neighbouring, there's lots of work to be done.
• 20:30
  Now let's go back and analyse randomised response. I claim randomised response is differentially private.
• 20:35
  The question is just for which value of epsilon. Okay.
• 20:39
  Now um but before doing that we need to have a definition of neighbouring.
• 20:44
  Right.
• 20:45
  Because I told you, um, you the most important thing in the definition of differential privacy is you need to exactly specify what is neighbouring.
• 20:54
  So here for, uh, randomised response, um, you want to protect the bit of each individual user.
• 21:02
  Okay, so then you say two inputs are neighbouring.
• 21:06
  If they differ in the bit of at most one user.
• 21:10
  Okay. So. Think of the initial inputs here as being a string d, then two inputs D and d prime are neighbouring.
• 21:19
  If one bit this is different. It's flipped.
• 21:23
  Okay. That's the neighbouring definition that you would use here. Now, why is differential privacy such a great definition?
• 21:31
  Well, it fulfils two main properties. And the first property is the post-processing theorem which says assume you have a
• 21:40
  mechanism that is epsilon differential private and it maps the data to some set R.
• 21:45
  And then you have some function that applies to R and compute some r prime.
• 21:50
  Then if you do the combination where you first run em and then run F on the output of em, this would be again epsilon differential private.
• 22:00
  Okay, so informally speaking, you had some data that was sensitive.
• 22:04
  You ran it through some mechanism. There was epsilon differential private.
• 22:08
  And now the data is clean, meaning you can do any post-processing on this output of the mechanism, not on the original data.
• 22:14
  Yeah. This does not allow F to touch the original data.
• 22:18
  F is not allowed to see the original data.
• 22:19
  The only is allowed to see the output of the mechanism, but if it only looks at the output of the mechanism, it will be fine.
• 22:26
  The whole thing. The combination of first running the mechanism and then this function is again epsilon differential private.
• 22:31
  So for randomised response this means as follows. You can really sorry this was not a good idea.
• 22:37
  This animation here. Um so you can really break it into two pieces.
• 22:42
  The first part which is what every participant had to do.
• 22:46
  Yeah this is the first part. This is really the mechanism. And you get this answers yes or no.
• 22:53
  This is the first part. This would be the mechanism. And we will show that this here is epsilon differential private.
• 22:58
  And then taking all this answers,
• 23:00
  figuring out the percentage Q of yes answers and outputting two columns Q minus a half is just a function F is just post-processing.
• 23:09
  Okay of this differentially private output that we got here from the mechanism.
• 23:13
  Okay. So. So now in order to analyse randomised response I only need to analyse this first part.
• 23:20
  I don't need to analyse the second part because the second part does not look at the initial data of the real users.
• 23:26
  Again has no contact to the user. Okay, so doesn't look at the initial data, only looks at the output of this mechanism.
• 23:34
  Okay. So this is one good theorem. And now you can actually do this analysis.
• 23:38
  I will not do it. I will just say you can actually do this.
• 23:41
  You know always look at the ratio of you know if you are in there or not in there and what's the probability that you say something, blah, blah, blah.
• 23:47
  What you will find out is that this ratio is at most over three, which is E to the L and three.
• 23:54
  Okay. So for randomised response this is your homework to do this yourself.
• 23:57
  But for randomised response I'm a professor right. Whenever it gets hard it's the homework.
• 24:03
  So for randomised response epsilon is LN3 okay.
• 24:07
  And I have to say there are different variants of randomised response where you would not use a fair coin.
• 24:12
  You would use a biased coin in your coin flips.
• 24:15
  And if you do this then you can make it also epsilon differentially private for any epsilon larger than zero.
• 24:21
  Just this simple variant that I showed to you was LN3. Okay, so this is the first useful thing.
• 24:27
  The second useful property of differential privacy is composition.
• 24:31
  Okay. So assume you have a first mechanism that's epsilon one differentially private.
• 24:36
  In the second one that's epsilon two differentially private. And now you want to have a mechanism that you can achieve.
• 24:43
  You want to have a mechanism that just outputs both outputs M1 and m2 the output of M1 and the output of M2.
• 24:51
  Then the theorem says that this is epsilon one plus epsilon two differentially private.
• 24:57
  And that's not too hard to show based on the definition of differential privacy.
• 25:01
  And now to do a post-processing. So once you output these things then you can now throw any function g on these two outputs.
• 25:09
  Basically post-processing is before. And that now tells you that also some function g arbitrary function g based on the
• 25:15
  output of these two things is also epsilon one plus epsilon two differentially private.
• 25:20
  So this allows you to analyse the harm or the influence on your privacy done by having multiple mechanisms,
• 25:27
  looking at the same data and outputting something about it. Okay.
• 25:31
  So if we look for example back to this movie data.
• 25:35
  So let's say D is a true data. So for all the users, whatever they looked at and whether they liked it or not.
• 25:42
  And then some of the data might be Netflix. Okay, so Netflix would be the first mechanism.
• 25:49
  And it is it discloses something.
• 25:52
  Now, as we said before, Netflix only anonymized the data and you can show that the station does not fulfil epsilon differential privacy.
• 26:01
  Epsilon differential privacy, meaning the epsilon would be infinite. Yeah.
• 26:05
  Now the second one is the Public Internet Movie Database.
• 26:09
  And the users might not write about all the movies they have seen.
• 26:12
  So this might be, again, just some incomplete set of the truth T and that's just disclosed.
• 26:18
  There's also mechanism to just write down whatever, I guess. Again, not at all private.
• 26:23
  Okay. So you have a second mechanism with epsilon being infinite.
• 26:27
  Okay. So now not surprising that the combination of the two is again no privacy.
• 26:32
  But if this first one would have had some privacy epsilon one in the second one would have had privacy epsilon two.
• 26:38
  Then the combination of the two having both of them out there would be now a privacy loss of epsilon one plus epsilon two.
• 26:46
  Okay. So this is the second very nice property of differential privacy.
• 26:51
  Um, now I there's one thing that people then usually ask me at this point in time.
• 26:56
  So I'm, I created a slide for it, which is there is two different notions of differentially private mechanisms.
• 27:03
  There's the one that you just saw, uh, which is called local differentially private algorithm.
• 27:09
  Uh, it's like a randomised response. So here the user has a two data whether they have property A or not.
• 27:16
  And they output some noise variant of it because they flip this coin.
• 27:20
  So they output a noisy variant of it and they give to the server the noisy variant and all.
• 27:24
  What the server does is post-processing. Okay.
• 27:27
  And as we know, the server cannot do any harm because the data was already private.
• 27:32
  Um. That's how I've always thought the notion of central differential private privacy,
• 27:36
  that's more of what you would see in medical databases where, uh, the users actually give the raw data to the server, to the database.
• 27:44
  Okay. So the database actually has the true answers in it,
• 27:47
  but then it let some differentially private mechanism run over it that then outputs a differentially private output.
• 27:55
  Okay. And so here the difference is the server has actually got all data,
• 27:59
  which is here where the server did not have the true data, only the uh, and uh the private data.
• 28:06
  Okay. That's a difference between the two. In this talk I will talk about the central model.
• 28:10
  Just because it's easy apart from randomised response, just because it's easy and most more work in the central model.
• 28:15
  But of course now there's also a lot of work done in the local model because, um, that's very often what,
• 28:21
  what happens when, you know, uh, internet companies are collecting data about their users.
• 28:26
  It's there usually it's in the local model that the users algorithm,
• 28:31
  the user's machine or iPhone is sending this differentially private data to the server.
• 28:38
  Now this is all great, but are there disadvantages? And yes, there are two main disadvantages.
• 28:44
  The first one is differential. Private algorithms are usually slower.
• 28:48
  Like before you would have had just to say yes I have a or not.
• 28:53
  And now you have to flip this two coins.
• 28:55
  And you know I just did this with volunteers and some talk and they had to think about, you know, when to do what.
• 29:00
  And so, you know, it's not so easy anymore. It's a bit more work.
• 29:04
  And in general differentially private algorithms are slower than non differentially private algorithms.
• 29:10
  And the question is just by how much. And the second even larger problem is the loss on accuracy.
• 29:17
  Okay. So for example which we also call error for example for randomised response.
• 29:23
  So what we are interested in is P would have been the two answer.
• 29:27
  Yeah. And now what we the way we measure the error is as follows.
• 29:31
  We say um what is the parameter alpha such that with probability at least two thirds q falls into this range between p plus alpha and p minus alpha.
• 29:44
  Okay. So with probability, at least two thirds Q must fall into this range.
• 29:48
  And then we say if I say accuracy. There's also a variant where, you know, this is some arbitrary parameter beta.
• 29:55
  But for this talk I just plugged in two thirds. Okay.
• 29:58
  So the accuracy is the alpha such that with probability at least two thirds, the answer that you get will fall into this range.
• 30:05
  And of course you want the alpha to be as small as possible because you want to be as close as possible.
• 30:11
  Yeah.
• 30:11
  And so whenever you write a paper about differential privacy, it's you should of course prove that your mechanism is epsilon differentially private.
• 30:19
  Well whatever notion you of privacy use. But then please always improve accuracy.
• 30:24
  But it's very important that you also show a bound on accuracy.
• 30:27
  I can give you an algorithm for any problem that's always epsilon differentially private.
• 30:32
  I always say zero. You know, it's definitely private.
• 30:36
  It doesn't leak any information, but it has miserable accuracy.
• 30:39
  So just writing a paper where you say, oh yeah, have a epsilon differential, private algorithm is not impressing me at all.
• 30:46
  You better show, you know, that it has always a small accuracy, even in theory.
• 30:50
  Well, with experiments. Yeah. So it's a very important part.
• 30:53
  And I'm emphasising this because I'm seeing papers where this is not done right.
• 30:57
  And I'm kind of wondering why people would not do that. Okay.
• 31:00
  So now for randomised response. What do we get. Well you can show actually using some kind of bounds that although maybe at most uh,
• 31:10
  some constant times square root of another constant divided by n okay.
• 31:15
  Which makes sense. So the more volunteers you have to participate, the smaller the alphabet get okay, the better the accuracy will get.
• 31:24
  If I have only three of you, you know I might be very noisy. If I have, uh, 10 million, it's much better.
• 31:31
  But so what have we seen?
• 31:33
  Um, so we have seen so far randomised response is LN3 differentially private and it's o of square root of one over n accurate.
• 31:42
  And in general the definition of accuracy is as follows.
• 31:45
  We say a mechanism is if accurate if for all inputs d the probability again over the randomness of the algorithm
• 31:53
  that the two output minus the noisy output is at most all for that probability is at least two thirds.
• 31:59
  So there is a good chance that the answer the error is at most alpha.
• 32:05
  And so the goal in differentially private algorithms research is always you have some computational problem.
• 32:12
  Yeah. Nothing as simple as computing an average. Know something more complicated.
• 32:17
  If you wanted to find a max cut in a graph or you know your favourite problem and, um,
• 32:22
  you want an algorithm that is differentially private, it should have small additive error.
• 32:27
  So small accuracy and the running time should be almost the running time.
• 32:32
  And also the space usage should be almost as good as the best Non-private algorithm.
• 32:37
  So these are the three things you're trying to optimise. And it's usually in that order.
• 32:43
  Which means people. People in papers usually stop after the first two, but sometimes already after the first.
• 32:50
  Okay, now there has been a lot of research.
• 32:54
  Let me stop complaining. There has been a lot of research in differential privacy on bunch of problems.
• 33:00
  I only talk about the simplest, which is a binary count in this talk here.
• 33:04
  Um, but there's also, you know, lots of other graph properties clustering.
• 33:09
  Machine learning is of course a very hot topic, differentially private machine learning and also mechanism design.
• 33:15
  So this is in auctions for example. Okay.
• 33:20
  Before getting into more definitions, let me give you some deployment examples so that you are motivated to keep on listening to me.
• 33:26
  Apart from having to sit here anyway, so um, there have been a few large scale deployments actually,
• 33:32
  and the first one was by Google, the wrap system, which was in Google Chrome.
• 33:37
  Uh, these are the authors here. And, um, they built this system in Google Chrome.
• 33:44
  And what it did was it detected the most frequently chosen homepages and also the most frequently chosen, uh, running process names in Google Chrome.
• 33:55
  And that's the information it sent back in a differentially private manner such that
• 33:59
  nobody could come to you afterwards and say that you always visit this homepage.
• 34:02
  So in a differentially private manner. Um, then more a little bit more recently.
• 34:08
  Uh, it's in Gboard. That's the Google, uh, keyboard on Android.
• 34:13
  So if you're typing on Android, um. In Google Chrome.
• 34:18
  What do you mean? You might use the cheap word. And they are. They did also learning for word prediction.
• 34:22
  So this is when you type in high and then it says the next word.
• 34:26
  Yeah or whatever. Thank. And then comes you. Yeah that's what they do in here.
• 34:33
  This example high. How off. Then they suggest you.
• 34:37
  And this is also done um based on differential privacy.
• 34:40
  And um this is the URL of the paper. Um, yeah.
• 34:44
  They evaluated the whole system. And they did more things and they evaluated it given evaluation of the whole system.
• 34:52
  Then. As I mentioned before, it's been used by the US 2020 U.S. census.
• 34:57
  There was a lot of battle about whether they should use differential privacy or not in the census.
• 35:03
  For the 2010 census, there were some privacy leaks, some awkward privacy leaks.
• 35:08
  And that's why they said, you know, the people who were running the census said, we need to use some protection, so let's use differential privacy.
• 35:15
  And the statisticians always said no. And the, you know, algorithms, people said yes and argument back and forth and back and forth.
• 35:22
  And so the decision was then made. Yeah a compromise.
• 35:25
  Yeah. Privacy is used. But Epsilon is 19. That was the time.
• 35:31
  That's now the statisticians are still very unhappy. Just recently I read an article that for some native people.
• 35:37
  Right. If you have a small group, uh, then the noise that you add makes a lot of difference.
• 35:42
  And so some native people are now complaining that, you know, based on that data, they compare the 2010 data with the 2020 data.
• 35:50
  They cannot, uh, you know, say how much their population has really grown or where there are needs and blah, blah, blah.
• 35:57
  And the census data is usually used to determine funding for native people.
• 36:01
  So it's of course important for them to be able to say, you know, we on so much.
• 36:05
  And so there are there are complaints about this for small populations, especially, uh,
• 36:10
  the statisticians are also complaining because some people, they complained, live in Manhattan in the Hudson River.
• 36:15
  And that should not have either. But, uh, then the, you know, algorithm, people say that's just noise, right?
• 36:21
  It's not many. But anyway, so there are some complaints and there are some discussion.
• 36:24
  And it would be interesting to see what happens in the 2030, uh, census.
• 36:30
  See. And then there was also some, uh, deployment in Apple.
• 36:34
  And this is also one of the strange papers because it has no authors except for like Apple Privacy Research group.
• 36:41
  Uh, very private, I guess.
• 36:46
  Okay. Until they showed that, uh, uh, for example, how you can use it to determine frequently used emojis.
• 36:53
  So, for example, for English speaking, if you have an English keyboard, uh,
• 36:58
  then it seems like the smiley face here where you have, you know, tears where you smile a lot.
• 37:03
  It's very popular, but the laugh is very, you know, only the second most popular, much lower level for the French, less my less.
• 37:10
  But I have much more love, for example. And so they figure that out with differential privacy.
• 37:16
  Also, they looked at, you know, uh, memory usage, which webpages train their battery a lot in Safari and things like that,
• 37:24
  and in which health topics people are interested in because,
• 37:27
  you know, they also sell you the Apple Watch and they want to know, are you someone you know who might be interested in health?
• 37:32
  So they also, uh, collect which health topics might be interesting.
• 37:36
  And finally, there was also work at Microsoft published by these people.
• 37:40
  And, uh, this is in Windows 10. Uh, they use this, uh, for estimating application usage statistics.
• 37:48
  And they also do the very. So this is a picture of their paper. Very careful evaluation.
• 37:54
  Okay, so you can see all become many big companies are using differential privacy already when they collect data about their users.
• 38:01
  And so now let me switch back and uh, um, tell you a little bit more about the theory behind it.
• 38:08
  So I said, in a static setting, the most simple problem that we are going to look at is binary count.
• 38:13
  So here what you have, you see, you have a, uh, string, a binary string D of length n.
• 38:19
  So think of n users and you want to just figure out the sum so the number of ones in the string.
• 38:25
  This is basically the same as before for randomised response.
• 38:29
  Right. That was finding the population. The percentage is the same as you know finding how many have it.
• 38:34
  And then divide by the size by n. Okay, but I will give you now a different mechanism that's more efficient.
• 38:41
  Meaning having lower accuracy. Um, so better accuracy.
• 38:47
  Um, so esp for the prime isn't neighbouring if it differs from D by one bit.
• 38:52
  And so now it turns out there is this very nice distribution called Laplace distribution.
• 38:57
  It existed before, but it looks like it's perfect.
• 39:00
  It was specifically designed for differential privacy which of was not.
• 39:03
  But it has only become really popular uh, through differential privacy.
• 39:07
  So it's this function here. So, uh, this distribution.
• 39:12
  So the Laplacian distribution has a parameter here I call it one where epsilon.
• 39:17
  And then you get this function. So at some value x you get this density function here.
• 39:23
  And so what you have is you have then uh the variance of sigma.
• 39:28
  And so if the sigma is very large like here in the light blue, what you get is you get a distribution that's very spread out.
• 39:35
  Yeah. So the probability that you pick minus ten is still, you know, not constant or that you pick plus ten.
• 39:43
  Um, the smaller the sigma the variance, the more picky the distribution is.
• 39:48
  Yeah. Uh, I should say it's symmetric around zero a very important symmetric around zero.
• 39:53
  And the more peaky it is. So it's a red one here for example. It's very picky okay.
• 39:58
  So if you sample from it you're very likely probability almost a half that you pick zero.
• 40:04
  Okay. So now what is a Laplace mechanism?
• 40:07
  The Laplace mechanism is very simple.
• 40:09
  Uh, you take the two, answer the sum of the ones, and you add a random variable that you chose according to this Laplace distribution.
• 40:19
  Okay. And it turns out you can show that this is epsilon differentially private.
• 40:24
  And that is Ellen three over Epsilon accurate.
• 40:29
  So. So why is this? What is the intuition? Well, you see, if you want good privacy.
• 40:34
  Yeah. So you have small epsilon. Then one over epsilon will be large, which means the variance of your distribution will be large.
• 40:41
  So you're more like the light blue here. Okay, so you're not too unlikely to actually add a number like ten to your numbers.
• 40:49
  But you remember, the input differed only by one, right?
• 40:52
  So you had two input strings that differed by one bit.
• 40:55
  And now you add a noise of, let's say ten to the one to the first string, the one that had this one bit not set.
• 41:02
  Let's say, let's say the first bit. They define the first bit. The first string has zero.
• 41:06
  In the first bit the other string has one in the first bit. And now the probability that for the first one you pick the ten.
• 41:14
  And so you would output. Then whatever the two ends are plus ten.
• 41:18
  And the probability that you take the first.
• 41:21
  The second one. And you pick the nine. Yeah.
• 41:25
  Which in this case you would then output in both cases the same thing,
• 41:27
  namely the two ends out of the first one plus ten because the second string had the first bit set.
• 41:32
  Yeah. So the probability that they are almost the same are very close right.
• 41:37
  Just a difference here between picking a ten or a nine.
• 41:41
  Okay.
• 41:42
  And so you can show that by taking this parameter one way epsilon for the Laplace definition you get exactly epsilon differentially private privacy.
• 41:51
  It seems like it's perfectly made for that. And for the accuracy if well, you need to do a little bit of work, but not too bad.
• 41:57
  Some properties of the Laplacian distribution. Okay.
• 42:00
  But this is very nice. It's independent of n okay.
• 42:04
  So accuracy is independent of the size of the input. Okay.
• 42:08
  That's an icing here. So that's good. But what if data is dynamic.
• 42:13
  And this is now finally where my book comes in. Because I like to always look at the dynamic setting where the input changes.
• 42:21
  Okay. And now the people cannot agree in the field what they should call the dynamic setting.
• 42:26
  They don't call it dynamic, that's for sure. They call it either differential privacy under continual observation or under continual release.
• 42:34
  Well, on streaming data. Well, sometimes on data streams.
• 42:38
  Okay. They are very creative, but it's all the same. It's where you get the data, one after the other.
• 42:45
  Okay. So for the general model, what you have, you have a stream of input data from the universe, you of some length let's say t.
• 42:53
  And now the privacy definition needs to be adapted. Um, and I'll talk about this in in a second.
• 43:00
  But what you need to do is every time you get some input, you need to give some output again.
• 43:05
  Okay. So before in the static setting you had one input and you gave one output.
• 43:10
  So you had just one chance of leaking information right.
• 43:14
  By now you have t chances of leaking information because you need to give two outputs after each input.
• 43:20
  And after the next bit of input arrives, you need to give some output again.
• 43:24
  So let's say for binary counting you need to keep on outputting the sum.
• 43:28
  So far the sum so far. And so you have t times the chance to leak information.
• 43:33
  So intuitively already the accuracy should go up.
• 43:36
  You need to add more noise. Okay, so one thing the open problem actually is continual binary counting.
• 43:43
  And I'll tell you what to open about it. Um, so where you have just a stream of input data zero one of length t,
• 43:50
  and after the t split is given for any t between one and capital T, you need to output the sum of all the bits so far.
• 44:01
  And, um, now, in differential privacy and the continual observation, there was a two definitions of privacy.
• 44:08
  I'll just show you one. Um, and I'll just mention that there's a second one.
• 44:13
  And this is the event level differential privacy. And that's very similar to what we've seen before.
• 44:18
  So we say Sigma and Sigma Prime are neighbouring.
• 44:21
  If they differ in one input value in which means in one time step, in one time step you can give something out, get something else.
• 44:29
  And then in the definition of differential privacy now you need to say over all time steps.
• 44:34
  So before we said over all neighbouring databases. And so now we need to say over all the time steps.
• 44:41
  Uh, before we also had over all possible outputs, the outputs on our two dimensional vector.
• 44:46
  And then for any neighbouring inputs you have this definition again.
• 44:51
  And is. It's as it's late in the talk and I don't want to bore you too much.
• 44:54
  I skip this definition of user level privacy, but there is a more, uh, you know,
• 44:59
  advanced or more stringent the harder version, which is called user level privacy.
• 45:04
  So everything that I'm going to say now is about event level privacy.
• 45:09
  And so now you care again about the accuracy. So what is the proper definition of accuracy for the continuous setting.
• 45:16
  So now you are outputting a two dimensional vector right. Because you are outputting T numbers.
• 45:21
  And so the error definition that is most popular is that you take the maximum over all time steps.
• 45:28
  So if you think of this as being a vector. So this is f of sigma is a two answers a two dimensional vector with the two answers.
• 45:35
  And um, alpha is the one that the algorithm gives you.
• 45:40
  Okay. And we will see this in a second. Then we will take the max, the infinite in one, which is the maximum of all the entries in this two vectors.
• 45:49
  Okay. So we say the mechanism is also accurate.
• 45:53
  If for all input streams of length t, the error of the two answer versus the output of the mechanism.
• 46:00
  Here, for every plug in the output of the mechanism,
• 46:03
  the probability that most is the difference is at most, although with at least probability two thirds.
• 46:11
  But. And now what's known about continual binary counting.
• 46:15
  Well, you could do it in a very naive way. The naive way would be to trust every time.
• 46:21
  At every time step you just add Laplacian noise. This is like a static algorithm.
• 46:26
  Run the static algorithm every time. But now you're outputting tee times.
• 46:31
  So and if you do composition right. Then the differential privacy of these tee outputs is the sum of the epsilon values.
• 46:40
  Okay. Since you are outputting t of them, you have to make sure that each of them is epsilon over t differentially private.
• 46:47
  Okay.
• 46:47
  So you have to require each at each output you have epsilon over t differentially private which means you need to use Laplacian noise t over epsilon.
• 46:56
  Okay. And then you can just use the composition that I showed you before,
• 47:00
  and you get the sum of all these key outputs every time epsilon uh of this t epsilon numbers every time epsilon over t.
• 47:07
  So you get that your epsilon differential product. So that's good.
• 47:11
  But what is your accuracy. If you have Laplacian noise t over epsilon your accuracy is t over epsilon which is really not good.
• 47:19
  It's the number of times steps over epsilon. Okay.
• 47:23
  And the question is can you do better. And the answer is yes, but not as good as you would like to.
• 47:29
  So what? What can you do? You can do an accuracy of loks squared t over epsilon.
• 47:39
  That's good. Much better than t. But there's also a lower bound of log t.
• 47:45
  So this was shown by to work Noah Petersen Ross Blum and this by these authors and Chauncey and so on.
• 47:51
  They actually showed slightly worse bounds. But you can, you know, basically get these bound said, okay, so there is actually a gap.
• 47:59
  Yeah, between the lower bound.
• 48:00
  So you cannot show anything better than log T as this lower bound, no matter which mechanism, there cannot be a mechanism better than log t.
• 48:08
  Um, but there's also this upper bound of log square T.
• 48:12
  Now, this lower bound of locked is actually really a disaster, right?
• 48:16
  Because if t goes to infinity, think of you use your phone every day, you know, and probably hundreds of times per day.
• 48:23
  Yeah. So your t they if every time they sending some information back whether you know you looked at health related data or not for example.
• 48:31
  Yeah. Then your T is very quickly very big. And this says here that then the accuracy has to go down by a factor of log t,
• 48:40
  where the companies who are collecting data about you don't like this, right.
• 48:44
  They don't want to have such a bad accuracy.
• 48:46
  So what they do is supposedly that's what they say is every time period, let's say every month, they give every user a certain privacy budget.
• 48:55
  And then when they whenever they use your data in some computation, they subtract something from your privacy budget.
• 49:02
  And if your privacy budget uses reaches zero, they don't use your data anymore for whatever training or whatever algorithms they use.
• 49:10
  They don't use your data anymore. Until the next month, when they reset your privacy budget to be the initial value again.
• 49:19
  Which means basically that they just delaying.
• 49:22
  Right. The privacy loss right there. Just no, uh, they're just delaying it a little bit because for a while they're not using your data.
• 49:30
  But that's how they deal with it. But on the other side, you know, if they don't want to have an accuracy error of to you,
• 49:35
  that's really the only thing they can do because otherwise, you know, it's too bad.
• 49:40
  Now it turns out there's a slightly relaxed version of differential privacy called epsilon delta differential privacy, which I don't want to define.
• 49:47
  And there you can do it even more complicated.
• 49:50
  There you can also actually log t to the 1.5 and was shown by Tung XI and so on.
• 49:56
  Um, and so here we did some work together with Baga and Apache.
• 50:01
  Uh, then what we did is we actually fixed figured out the constant.
• 50:04
  They had a really bad constant. We did an algorithm, a different algorithm where we show the exact constant.
• 50:11
  And, um, the other advantage of our approach is that our accuracy loss.
• 50:15
  So our noise is very smooth. While for the other algorithm, the noise was very, um, smooth, as you can see.
• 50:21
  So for each point in t this put a dot okay. And so you see that it was very smooth.
• 50:27
  And the reason being that the amount of noise, the number of Laplacian noises that you would add up depended on the time step.
• 50:34
  And it might even be just one Laplacian noise, or it might be locked in Laplacian noises.
• 50:38
  And so you got very non smooth noise in the setting.
• 50:41
  And in practice it's a disaster. So you want to count how many Covid cases there are right.
• 50:46
  And you don't want something where you say I don't know where they went up or not.
• 50:49
  Maybe might have been the noise that made it go up. Or maybe the data really goes up.
• 50:53
  So you want the noise that goes up in a smooth way and not such a jumpy way.
• 50:58
  Now let me just because I promised very, very high level sketch how this algorithm works.
• 51:03
  Okay. It's actually simple.
• 51:05
  Uh, even though you might not believe it, it's very our algorithm is very simple because, you see, what do you want to output?
• 51:11
  You want to output the sum of ones.
• 51:14
  Now, I can write this down as a linear algebra problem where you have a matrix A that is lower diagonal with all ones down here,
• 51:21
  and also rows up here. And then the output that you have is simply a times sigma where sigma your input vector.
• 51:29
  Yeah, that's exactly the output that you want. And even better if you are at timestep t.
• 51:35
  So this is the output for all. If you do this product you get all the answers for all time steps.
• 51:40
  If I'm just an time step lower T, I can just take the t by t principal submatrix.
• 51:46
  So the small version of a yeah is up t, but I just take the first t rows and columns and take just the first t entries of my input into this product.
• 51:57
  And the t coordinate of this product is, uh, the answer I want.
• 52:01
  So this is the correct answer. And so now how do we do make this differentially private.
• 52:06
  What we do is we show that there is a composition of A into two matrices L and R.
• 52:11
  And they are both lower triangular as well okay.
• 52:14
  That's the crucial thing. They need to both be lower triangular to work in this continual setting.
• 52:20
  And so they also have this nice property. If you restrict them to the top t by t u k the l's up t and R's up t and that product is still R is up T.
• 52:29
  So everything is beautifully well-behaved. And so now what our mechanism does is a time step t.
• 52:36
  It takes r t and multiplies this with the input sigma t.
• 52:40
  And then it adds a noise vector to it. Okay.
• 52:44
  So it adds noise vector to it here. And then it does post-processing by multiplying with l t.
• 52:50
  So our mechanism is this very simple thing here. Okay.
• 52:55
  Where you can prove that, you know, this is an unbiased estimator and you can show that this is differentially private.
• 53:00
  So what we get is we get a maximum epsilon delta differentially private.
• 53:05
  Um, we get this epsilon delta differentially private mechanism that has this accuracy.
• 53:09
  So then the whole proof is linear algebra. Okay.
• 53:13
  Good. So this is, uh, this is what we did here.
• 53:16
  Now, there has been work for in the continuous setting in, uh, these five cases.
• 53:21
  So we have data streams, which are sequences of numbers.
• 53:24
  We have databases which are sequences of rows that have been analysed, data structures where you have sequences of operations,
• 53:31
  for example, heaps, um, graph algorithms where you have again sequences of operations, insertions and deletions of edges.
• 53:39
  Uh, clustering algorithms where you have insertions and deletions of points and you want to maintain some clustering of them.
• 53:45
  Uh, all this has been studied, but of course, it's still in the beginning, meaning we don't necessarily have the best, uh, answers for them.
• 53:53
  So what are future directions? So one is this look at user level differential privacy, which I just mentioned before.
• 54:00
  Uh, the other one is local differential privacy that I defined.
• 54:05
  And there has been very little work of local differential privacy under continual observation.
• 54:10
  And then also look at the running time and actually implement this algorithms and see how fast they are and how they actually perform.
• 54:16
  Yeah. So actually do algorithms engineering.
• 54:19
  And then the specific problems that I'm still interested in come up with better algorithms for clustering or graph properties and also, uh,
• 54:26
  close the gap of this upper bound, which is located to the 1.5 for log square,
• 54:32
  T for continuous binary counting, and this log T for the lower bound close the gap.
• 54:37
  These are the two specific problems I want to look at. And then I want to just thank my co-authors.