1
00:00:00,000 --> 00:00:03,700
Hello, I am Miguel Guevara.

2
00:00:03,800 --> 00:00:05,500
And I'm Brian Gibson.

3
00:00:05,500 --> 00:00:09,920
I work in privacy infrastructure at Google, in particular on differential privacy.

4
00:00:10,080 --> 00:00:15,060
And we will talk to you about today our differential privacy.

5
00:00:15,420 --> 00:00:19,260
Before we start, let me play this video for you.

6
00:00:21,140 --> 00:00:25,260
At Google, we use data to make our services work better for you.

7
00:00:25,260 --> 00:00:29,880
And it's our responsibility to keep your data private, safe, and secure.

8
00:00:30,000 --> 00:00:34,880
That's why we continually invest in tools that protect individual privacy.

9
00:00:35,020 --> 00:00:38,320
Differentially private analysis is one of those tools.

10
00:00:39,100 --> 00:00:46,980
Many of our features, like popular times and maps, are only possible because we can learn from the activity patterns of millions of users.

11
00:00:46,980 --> 00:00:54,680
With differential privacy, we can protect an individual's data while still preserving the usefulness of the data at scale.

12
00:00:54,680 --> 00:00:57,340
Let's take a closer look at how it works.

13
00:00:57,340 --> 00:01:03,180
Imagine you're trying to plan a trip to the grocery store and want to know how busy it is at the moment.

14
00:01:03,880 --> 00:01:12,320
We use differentially private analysis on the historical and real-time data of other shoppers to show you how busy a place is.

15
00:01:12,720 --> 00:01:19,460
The analysis adds noise to results so you can look at how crowded a place is without identifying who was there.

16
00:01:19,460 --> 00:01:31,240
Differentially private analysis is what enables us to show millions of our users every day how busy a place is while protecting people's privacy with confidence.

17
00:01:31,380 --> 00:01:37,820
Many important research, business, and social questions can be answered by analyzing large data sets.

18
00:01:37,820 --> 00:01:44,240
Which is why, after years of development, Google has made its differential privacy library open source.

19
00:01:44,240 --> 00:01:58,660
Whether you are a researcher working on new medical treatments or a developer building an exciting app, this open source library can help you easily and affordably gain insights from data in a private, secure way.

20
00:01:58,920 --> 00:02:05,200
Differential privacy is just one of many ways we build privacy protections into our products.

21
00:02:05,200 --> 00:02:11,520
And we will continue to innovate to new technologies that keep your data private, safe, and secure.

22
00:02:12,680 --> 00:02:14,240
Great.

23
00:02:14,960 --> 00:02:24,320
Now that we've watched the video, I'll get into trying to talk a little bit more from a high level about differential privacy.

24
00:02:24,860 --> 00:02:32,760
The naive question that we always get is, why don't we just remove identifiers to anonymize data?

25
00:02:33,360 --> 00:02:41,500
Unfortunately, removing identifiers might not be good enough, as well as removing PII.

26
00:02:41,520 --> 00:02:48,600
There are multiple well-known data breaches resulting from publishing the quote-unquote de-identified data.

27
00:02:48,600 --> 00:02:55,240
One classical example involves the publication of de-identified medical records in the state of Washington.

28
00:02:55,240 --> 00:03:01,360
Those records could be partially joined with the voting registry using birthday and postcode.

29
00:03:01,360 --> 00:03:06,680
This was sufficient to identify a majority of individuals in the data set.

30
00:03:06,680 --> 00:03:19,540
In another classical example, as a part of a competition in 2006 that intended to improve the movie recommendation system, Netflix published movie ratings from its users.

31
00:03:19,620 --> 00:03:29,180
The records had the user identifiers removed, but researchers could partially join these records with IMDB databases, which were tied to identity.

32
00:03:29,540 --> 00:03:35,480
Such a join made possible to partially tie the full history of movie ranking to the user identifiers.

33
00:03:35,480 --> 00:03:42,540
This is a classical example of joining de-identified data sets and re-identifying some of the users.

34
00:03:42,680 --> 00:03:49,560
Finally, de-identified search history can also, in certain cases, reveal the identity of a user.

35
00:03:49,660 --> 00:03:52,140
So, there is a pattern here.

36
00:03:52,140 --> 00:04:05,460
Even if the records are published without direct identifying information, the content of those records together with some auxiliary information may make re-identification possible in certain cases.

37
00:04:05,480 --> 00:04:09,840
Thus, we need something better than de-identification in general.

38
00:04:10,340 --> 00:04:16,300
The second question that is very common to have is, well, why don't we just aggregate data?

39
00:04:16,560 --> 00:04:24,680
In fact, it is a very well-known technique to publish aggregated statistics with buckets of users.

40
00:04:24,740 --> 00:04:27,920
Usually, this involves grouping by a set of features.

41
00:04:27,920 --> 00:04:33,240
For example, grouping by restaurant visits, by location, and hour.

42
00:04:33,240 --> 00:04:42,260
This is commonly referred to as k-anonymity, since each user in the anonymized dataset is indistinguishable from at least k other users.

43
00:04:45,580 --> 00:04:52,060
Now, let me explain to you why we need differential privacy and how it works.

44
00:04:52,060 --> 00:04:58,240
Let's imagine you are attending a two-day conference and the moderator shares some insights about the audience.

45
00:04:58,340 --> 00:05:02,580
Here, you can see the country of origin of the participants on day one.

46
00:05:02,580 --> 00:05:08,480
It's aggregated, so it does not reveal anything about any of the individuals in the room, right?

47
00:05:08,700 --> 00:05:17,160
And it looks like the top country of origin is Italy, whereas Germany has the least participants and France and Spain are in the middle.

48
00:05:17,760 --> 00:05:22,460
On day two, the moderator shows the stats for the day.

49
00:05:22,560 --> 00:05:25,080
They look pretty similar, right?

50
00:05:25,080 --> 00:05:33,380
Except, someone has been paying attention and noticed that there was only one new person on day two.

51
00:05:33,700 --> 00:05:37,960
And when they look at the data from both days together, look at that.

52
00:05:38,940 --> 00:05:42,160
Can you tell where the specific individual is coming from?

53
00:05:42,160 --> 00:05:43,160
Yes.

54
00:05:43,420 --> 00:05:44,540
Germany.

55
00:05:44,680 --> 00:05:53,780
This is how, with two aggregated datasets, the moderator has managed to leak information about a particular participant.

56
00:05:54,620 --> 00:06:02,760
K-anonymity provides stronger guarantees than simple de-identification, but it is not perfect either.

57
00:06:02,760 --> 00:06:12,760
For example, it is problematic if I'm part of a bucket that is associated with a sensitive attribute, say a particular medical condition.

58
00:06:12,860 --> 00:06:18,680
It's not helpful that I'm indistinguishable from K other users having the same condition.

59
00:06:18,680 --> 00:06:28,120
While I cannot be associated with any particular record in the database, my sensitive attribute in that example is revealed.

60
00:06:28,120 --> 00:06:30,080
Here is another example.

61
00:06:30,080 --> 00:06:38,220
Imagine two aggregate buckets, 99 users plus me and 99 users without me.

62
00:06:38,220 --> 00:06:50,600
Publishing aggregate information about those two buckets is K-anonymous, but it's possible to identify me and my sensitive attributes by differencing those two buckets.

63
00:06:50,600 --> 00:07:03,440
At last, if the attacker can modify the database and create fake entries, there's no anonymity for my data if I'm part of a crowd of 99 fake users.

64
00:07:03,440 --> 00:07:10,480
Those type of attacks aren't always feasible or relevant, but they cannot be excluded in general.

65
00:07:10,620 --> 00:07:14,360
Is there a better way to define anonymity?

66
00:07:15,400 --> 00:07:17,340
I think so.

67
00:07:17,340 --> 00:07:19,650
Let's use differential privacy.

68
00:07:20,650 --> 00:07:33,690
The moderator would similarly announce that they're showing insights about the audience, but they would like to announce, I'm going to share insights about the audience, randomly changing the numbers just a little.

69
00:07:34,070 --> 00:07:41,510
Look at the day one stats, how these stats look compared to the real numbers.

70
00:07:41,510 --> 00:07:43,170
They're slightly different.

71
00:07:43,170 --> 00:07:49,630
So yes, it is less precise, but you still get the same insights about the statistical trends.

72
00:07:52,170 --> 00:07:55,170
Similarly, let's look at day two.

73
00:07:55,970 --> 00:07:57,390
Same thing.

74
00:07:58,350 --> 00:08:07,510
But now, if you compare the stats for day one and day two, you can't tell which country the single person is coming from.

75
00:08:07,510 --> 00:08:11,990
And you know it's not worth trying since you know the numbers were changed a little.

76
00:08:12,310 --> 00:08:15,410
This is the principle behind differential privacy.

77
00:08:15,570 --> 00:08:34,510
Differential privacy introduces the right amount of noise to the data, so we're able to provide useful statistically significant insights while ensuring that no one can tell if a particular individual's information was used in the competition in a mathematically proven way.

78
00:08:35,810 --> 00:08:47,950
Just to recap, and Brian will talk a little bit more about it in a bit, an algorithm is differentially private if its output doesn't change much when a single person is added to the database.

79
00:08:48,010 --> 00:09:01,990
This has a rigorous mathematical definition, which basically considers a pair of two neighboring data sets, calculates the output of those data sets, and defines a threshold of the probability density functions.

80
00:09:01,990 --> 00:09:08,450
This threshold is what defines how much the output is allowed to change, and it's called epsilon.

81
00:09:09,050 --> 00:09:17,010
Now, let me talk to you about some open sourcing efforts we've done at Google to share some of this technology with the world.

82
00:09:17,010 --> 00:09:22,750
We publish our code in an open source library so that others can reuse our work.

83
00:09:22,750 --> 00:09:29,890
As I mentioned before, differential privacy has a lot of implementation subtopics, and it is hard to get it right.

84
00:09:29,890 --> 00:09:36,150
As all of you in the crypto community probably know, people should enroll their own crypto.

85
00:09:36,570 --> 00:09:42,230
And this is also a really good advice for differential privacy and their implementations.

86
00:09:42,430 --> 00:09:46,510
Reusing a hardened implementation is generally a good idea.

87
00:09:46,890 --> 00:09:54,150
We open source the technology, and you can read more of the articles that were written back then.

88
00:09:55,210 --> 00:09:59,510
I'll now give you some insights as to how we've used the technology.

89
00:10:01,350 --> 00:10:05,130
You're probably aware of the Google Mobility Reports.

90
00:10:05,130 --> 00:10:12,430
These Mobility Reports were a response to the emerging crisis back in March around COVID-19.

91
00:10:12,430 --> 00:10:20,890
They provide policymakers with an idea of mobility trends at a city and state level for different categories.

92
00:10:21,030 --> 00:10:27,610
Before I continue going into the Mobility Reports, let me talk to you a little bit about location data at Google.

93
00:10:29,430 --> 00:10:35,270
Location data is an optional account feature that says where you go in your private timeline.

94
00:10:35,270 --> 00:10:39,390
It's off by default and can be paused or unpaused anytime.

95
00:10:39,990 --> 00:10:44,390
From a product perspective, it's available on Android and iOS.

96
00:10:44,990 --> 00:10:56,690
It helps users remember where they have been and gives users personalized information such as better restaurant recommendations, suggestions for a faster commute, etc.

97
00:10:56,690 --> 00:11:07,090
Users can view, edit, and delete some or all of their timeline at any time, as well as set up auto deletion after three or 18 months.

98
00:11:07,090 --> 00:11:12,270
More recently, we announced that auto deletion is now automatic for new accounts.

99
00:11:12,590 --> 00:11:21,110
And if you're curious as to how it looks like, you can access it as it's been shown on this GIF.

100
00:11:22,690 --> 00:11:25,230
Now, let me talk to you about the reports.

101
00:11:25,230 --> 00:11:29,270
The reports are the Mobility Reports.

102
00:11:29,270 --> 00:11:35,630
These reports were the first product that Google launched that was built with differential privacy from the ground up.

103
00:11:36,130 --> 00:11:44,570
The reports do not share data about any individual's locations, movements, or conflicts.

104
00:11:44,950 --> 00:11:54,930
The insights are created with aggregated, anonymized datasets from users who have turned on the location history setting, which is off by default.

105
00:11:55,230 --> 00:11:59,590
People can turn off that setting at any time and delete their history.

106
00:12:00,130 --> 00:12:07,310
We took the additional step of utilizing differential privacy to ensure that no individual can be identified.

107
00:12:07,870 --> 00:12:10,990
So how exactly are we using differential privacy?

108
00:12:11,030 --> 00:12:17,310
First, we produce a count of people at certain locations within a geographical area.

109
00:12:17,310 --> 00:12:21,930
Let's say that we count the visitors to parks in Vegas on a given day.

110
00:12:21,930 --> 00:12:26,590
That might give us a number of 8,238 people.

111
00:12:27,030 --> 00:12:31,170
Secondly, we add what we call some random noise to that number.

112
00:12:31,310 --> 00:12:37,550
Let's assume, for example, that we added an artificial number of 79.

113
00:12:37,870 --> 00:12:42,950
We add these two and get a new count of 8,317.

114
00:12:43,310 --> 00:12:50,270
This count is differentially private, and we can now use it to calculate the metrics that we publish.

115
00:12:51,150 --> 00:12:59,170
This is an example of a differentially private query that we do to produce reports like the mobility report.

116
00:12:59,310 --> 00:13:10,210
It's helpful for people who are familiar with the SQL environment because it uses the general syntax by only introducing new anonymization functions.

117
00:13:10,210 --> 00:13:13,650
In this case, an anonymization count.

118
00:13:14,910 --> 00:13:26,110
Generally, to produce the metrics, in the reports, we compute a baseline using differential privacy for a given weekday in the past.

119
00:13:26,310 --> 00:13:30,330
Second, we compute those same metrics for a given day.

120
00:13:30,330 --> 00:13:36,910
Let's say for Friday, March 27, 5,000 people visited parks in the same region.

121
00:13:36,910 --> 00:13:45,530
Then we divide that result by the first result, showing that there was a 50% reduction in visits to parks in that region.

122
00:13:45,530 --> 00:13:49,210
And then we repeat this process for all the metrics that we are producing.

123
00:13:49,210 --> 00:13:53,910
And therefore, all the metrics that we're reporting are produced with differential privacy.

124
00:13:54,730 --> 00:14:00,410
There are some interesting practical aspects on how we use these reports.

125
00:14:00,410 --> 00:14:05,070
We limit the number of times that a person is counted on each metric.

126
00:14:05,070 --> 00:14:12,290
For example, if for some reason I go to the grocery store 100 times in a day, I will only be counted once.

127
00:14:12,390 --> 00:14:18,330
This prevents specific patterns like delivery worker people from being too revealing.

128
00:14:19,490 --> 00:14:23,310
Second, we remove metrics that are too noisy.

129
00:14:23,450 --> 00:14:33,570
By using confidence intervals, we can figure out when a number has a less than 5% chance of being wrong by more than 10%.

130
00:14:33,570 --> 00:14:40,630
And finally, if you're curious, we published a technical blog detailing the anonymization process.

131
00:14:42,570 --> 00:14:51,950
Differential privacy has been around for a while, and mobility reports are not the only example out there that's using it.

132
00:14:51,950 --> 00:14:56,050
The US Census is using it for its 2020 census.

133
00:14:56,050 --> 00:14:59,450
Facebook recently released an URL data set.

134
00:14:59,690 --> 00:15:02,530
Apple has been using it.

135
00:15:02,530 --> 00:15:04,550
We released it on Chrome a while ago.

136
00:15:04,630 --> 00:15:09,950
And it's also open source for machine learning purposes on TensorFlow privacy.

137
00:15:10,250 --> 00:15:15,650
Now, Brian will talk to you a little bit more about building the infrastructure.

138
00:15:15,830 --> 00:15:22,290
So getting to the point where we could build a new product from the ground up with differential privacy was a long journey.

139
00:15:22,290 --> 00:15:35,190
But I want to take you through three really critically important pieces of that journey, which is building strong foundations, building frameworks that are familiar to potential users, and helping users to assess the privacy utility frontier.

140
00:15:35,490 --> 00:15:41,270
So the infrastructure that we build starts with the differentially private foundational libraries.

141
00:15:41,290 --> 00:15:50,290
We started these about three years ago, and our vision was to power differentially private use cases that could primarily accelerate developer velocity.

142
00:15:50,290 --> 00:16:12,510
A lot of times users are trying to do experiments or prototypes before actually building a project, and this ideation stage is perfect for differential privacy, because it can provide a very good way of getting trends or overall statistics, and allows people to assess whether it's even worth continuing development on a particular project.

143
00:16:13,470 --> 00:16:23,150
So the foundational library that we use here at Google is actually the same as the one that we open sourced and published, so that others could reuse our work.

144
00:16:23,150 --> 00:16:27,310
For us, it's always been important to provide transparency around our implementation.

145
00:16:28,070 --> 00:16:31,710
Hopefully folks have had a chance to poke around the library.

146
00:16:32,690 --> 00:16:39,710
It was launched in C++ several months ago, and a couple of weeks ago we also launched a Java version of this.

147
00:16:39,730 --> 00:16:49,410
I think the analogy we oftentimes use with differential privacy is best compared to cryptography, right?

148
00:16:49,450 --> 00:16:54,570
There you say, don't roll your own crypto, same thing goes for differential privacy.

149
00:16:54,570 --> 00:17:08,830
There are a lot of gotchas, there's a lot of difficulty involved in rolling it out correctly, and an incorrect or partial implementation of DP is in some cases worse than none at all, because you might have a gaping hole in your system that you're not aware of.

150
00:17:08,830 --> 00:17:11,990
So reusing a hardened implementation is just a good idea.

151
00:17:13,370 --> 00:17:24,750
So the second step we did was to build a SQL engine, and there were lots of languages we could have used, lots of ways we could have gotten about this, but SQL really made the most sense, right?

152
00:17:24,750 --> 00:17:37,670
It's the language that most developers are familiar with, you don't have to be an expert to get in and start doing an analysis on data sets, and so it just felt like the right choice.

153
00:17:37,670 --> 00:17:43,470
So I'm just going to give a little bit of an overview of some of the challenges involved in this.

154
00:17:43,810 --> 00:17:48,170
So one of the big ones is that SQL allows pretty much anything.

155
00:17:48,170 --> 00:17:59,590
A lot of implementations are actually Turing-complete, so enforcing differential privacy, while at the same time allowing non-experts to write SQL that they're basically familiar with is a big challenge.

156
00:17:59,710 --> 00:18:12,350
A lot of challenges come up around things like joins between different data sets, or cardinality changes, if you're allowed to just multiply rows endlessly, lots of privacy implications come out of that.

157
00:18:13,130 --> 00:18:20,210
So the basis of differential privacy is really about quantifying the effect that a single user can have on output.

158
00:18:20,710 --> 00:18:24,590
And part of a differentially private SQL engine really has to have the same property.

159
00:18:24,590 --> 00:18:31,070
So what we do is we actually split SQL statements into per-user transforms and cross-user aggregations.

160
00:18:31,070 --> 00:18:36,750
The per-user transforms are very generous, you can do essentially arbitrary, even Turing-complete SQL.

161
00:18:36,750 --> 00:18:45,530
The cross-user transforms are a restricted set of aggregation functions that are much more protected from a privacy standpoint.

162
00:18:52,100 --> 00:19:05,240
Finally, you really want to ensure correctness when you're talking about any type of privacy-sensitive infrastructure.

163
00:19:05,540 --> 00:19:11,400
And unfortunately, proving that something you've built is differentially private is really hard.

164
00:19:11,400 --> 00:19:14,100
It's so hard, it's actually provably undecidable.

165
00:19:14,820 --> 00:19:22,840
That said, as part of the foundational libraries, we employ stochastic model checking as part of regression testing.

166
00:19:22,840 --> 00:19:37,900
Now obviously this isn't a sufficient guarantee for differential privacy by itself, but it really quickly catches violations, both obvious and subtle, and provides a stable backdrop to more traditional privacy verification work and expert analysis.

167
00:19:38,160 --> 00:19:44,080
So this is just an example of a differentially private query, we'll get into this a little bit more later.

168
00:19:44,100 --> 00:19:51,280
It's meant to be user-centric, it highlights the fact that you're doing an anonymous query right up front.

169
00:19:51,300 --> 00:20:02,320
And in general, it basically looks like a normal SQL query with just a few more keywords and syntactic sugar.

170
00:20:02,620 --> 00:20:13,000
You see that this query includes things like count and average, and is selecting from some table in exactly the same way that you would perform normal SQL.

171
00:20:15,280 --> 00:20:20,020
So that was a really cursory overview of this particular implementation.

172
00:20:20,200 --> 00:20:26,400
You can check out the details of our SQL implementation in full in the paper that we published at PETS this year.

173
00:20:28,280 --> 00:20:32,600
And we'll be getting into some of the more detailed math later in the talk.

174
00:20:32,880 --> 00:20:37,620
So we're going to spend some time to return to the math behind differential privacy a little bit.

175
00:20:37,620 --> 00:20:43,520
We talked kind of about how our SQL engine was structured and a little bit about differential privacy.

176
00:20:43,560 --> 00:20:52,720
But going into a bit more of the details, you know, usually when a DP is introduced, it looks something like this.

177
00:20:53,320 --> 00:21:04,980
Of course, what we're actually saying when we say some sort of probabilistic statement about any differentially private system is that adding or removing a user from a data set doesn't change the results that much.

178
00:21:04,980 --> 00:21:09,220
That much actually has a really rigorous technical definition.

179
00:21:10,040 --> 00:21:12,800
There's two parameters, there's epsilon and delta.

180
00:21:12,880 --> 00:21:26,020
Epsilon, we generally think about in a sort of a Bayesian context, which is to say that supposing I have some notion of a detail of a user that you're trying to target, right?

181
00:21:26,020 --> 00:21:36,380
Supposing you're about 60% sure that they live in Wisconsin, and the attacker is attempting to improve that confidence from their perspective, ideally to 100%.

182
00:21:36,880 --> 00:21:50,080
Well, it turns out that there's a really nice translation between how much an attacker can improve their confidence in knowing something and the epsilon that you choose.

183
00:21:50,080 --> 00:21:58,200
So for a particular choice of epsilon, perhaps they might be able to improve only 5% their confidence if they're starting at 60%.

184
00:21:58,200 --> 00:22:05,920
If you really, really want to be rigorous, perhaps they're not able to really improve it, you know, in any sort of measurable way at all.

185
00:22:05,920 --> 00:22:19,160
And so you have this nice principled trade-off between risk and accuracy, since the epsilon has the strongest influence on sort of the quality, the accuracy, the utility of the output results.

186
00:22:20,480 --> 00:22:24,280
Delta is a much easier concept to understand and explain.

187
00:22:24,280 --> 00:22:36,020
It's basically our out to say that we basically made a differentially private engine, but occasionally, very occasionally, it's not differentially private.

188
00:22:36,020 --> 00:22:38,940
So delta is the probability of catastrophic failure.

189
00:22:39,160 --> 00:22:48,740
There are lots of ways to think about it, but the way we generally talk about it is perhaps the number of output rows that are not strictly differentially private.

190
00:22:48,740 --> 00:22:52,740
Now, of course, you don't know which rows those are, so there's always sort of a reasonable doubt.

191
00:22:52,740 --> 00:23:01,540
But this allows you to really quantify a baseline of failure modes that your output data set can have.

192
00:23:01,820 --> 00:23:08,880
Delta tends to be very, very small, typically on the order of 1 over n, where n is the number of users, or rows, rather.

193
00:23:10,880 --> 00:23:31,120
And because the nature of the noise that we use is a decaying exponential, the delta that is sort of induced by some of the math, actually can be sort of smaller than is machine representable in many cases, as we'll get into in a few minutes.

194
00:23:31,220 --> 00:23:37,820
So oftentimes, you don't actually have to worry about a delta, but it's sort of important enough that you should be able to reason about it.

195
00:23:38,420 --> 00:23:47,580
So just returning earlier, we talked about the privacy model, per-user transformation that's very generous, more restricted cross-user aggregation.

196
00:23:48,340 --> 00:23:49,540
And that's why we apply to SQL.

197
00:23:49,960 --> 00:23:57,720
Let's take kind of an example of a typical privacy-sensitive query that seems pretty innocuous.

198
00:23:57,720 --> 00:24:03,580
We're counting up the number of visits to a website based on browser agent.

199
00:24:03,800 --> 00:24:09,620
So a quick look through the logs reveals that a single user used a particular agent.

200
00:24:09,900 --> 00:24:15,120
And already, we've kind of re-identified an individual without doing anything more than counting statistics.

201
00:24:15,120 --> 00:24:20,000
So we can see the problem with kind of a non-differentially private environment already.

202
00:24:20,440 --> 00:24:32,000
So classically, sort of naively, one thing that one does in differential privacy is they add some kind of noise that satisfies differential privacy to counts.

203
00:24:32,000 --> 00:24:40,820
And so in this case, we go through all the browser agents, we adjust the counts, plus or minus, a small amount of noise dependent on epsilon.

204
00:24:41,540 --> 00:24:43,880
And in general, you might think, oh, we're good.

205
00:24:43,880 --> 00:24:49,500
Except that a browser agent can be an arbitrary string, right?

206
00:24:49,500 --> 00:24:52,000
So this could be a made-up thing.

207
00:24:52,000 --> 00:25:01,560
Essentially, from the position of an attacker, you have to assume that browser agent is an unbounded space of potentially arbitrarily linked strings.

208
00:25:01,560 --> 00:25:11,200
Which means that if you see a value there in your logs, then at least one user must have registered that.

209
00:25:11,200 --> 00:25:13,060
There are lots of ways of dealing with this.

210
00:25:13,060 --> 00:25:20,240
You could generate a bunch of random strings, and sort of give essentially zero noise to each of those.

211
00:25:20,420 --> 00:25:25,600
But you, for an unbounded space, would have to generate unboundedly many browser agents.

212
00:25:25,600 --> 00:25:35,320
So the way that we do it is we basically just filter and say that at least tau users need to contribute to any particular partition.

213
00:25:35,500 --> 00:25:39,160
It turns out that there's a direct line between tau and delta.

214
00:25:39,160 --> 00:25:46,860
So it's really easy to reason about what sort of the correct tau or the correct delta needs to be in terms of the existing parameters.

215
00:25:47,940 --> 00:25:52,340
As I said earlier, the nature of the noise is a decaying exponential.

216
00:25:52,340 --> 00:26:04,760
So even for 50 users or 100 users, you might be at a vanishingly small, perhaps unmeasurably small, probability that a particular partition is surfaced incorrectly.

217
00:26:05,780 --> 00:26:07,780
So you think, we're done, right?

218
00:26:07,780 --> 00:26:08,840
Well, almost.

219
00:26:08,840 --> 00:26:11,360
There's a little bit more nuance to this.

220
00:26:11,360 --> 00:26:18,180
And this is kind of one of the big strengths of this type of a privacy model in SQL is that you can enforce it.

221
00:26:18,900 --> 00:26:23,800
So an individual user in any particular session might be using a single browser.

222
00:26:23,800 --> 00:26:28,300
But across all their sessions, they may have used many browsers, unboundedly many, in fact.

223
00:26:28,360 --> 00:26:33,760
And from the perspective of differential privacy, we're trying to protect a user, not a browser.

224
00:26:33,760 --> 00:26:48,280
So if a user has used 10 different browsers and everybody else has just used one, potentially you violated kind of the epsilon guarantees of your system, if you allow that.

225
00:26:48,280 --> 00:26:58,160
So the way that we deal with that is with reservoir sampling of a user's contributions and then limiting those contributions.

226
00:26:58,160 --> 00:27:04,380
So a user might be able to contribute to 10 separate partitions or three or one or whatever seems appropriate.

227
00:27:04,380 --> 00:27:09,360
And again, it's another parameter that can be chosen by the user.

228
00:27:09,480 --> 00:27:14,520
But you can also sort of choose one based on an appropriate epsilon and delta.

229
00:27:15,020 --> 00:27:23,580
So again, it's just about giving an engine the flexibility to represent sort of both utility and privacy needs at the same time.

230
00:27:24,040 --> 00:27:26,780
And this is basically the model in a nutshell.

231
00:27:26,780 --> 00:27:32,120
Now, of course, if you were requiring users to write exactly the syntax every time, that's not possible .

232
00:27:32,120 --> 00:27:48,540
And so the new syntax is introduced with anonymization is basically just a clever rewriter that is doing all of that in the background to the AST of the SQL and allowing people to write basically SQL that they're familiar with.

233
00:27:48,540 --> 00:27:58,300
You see a few more keywords in here, obviously, the privacy parameters, the anonymization keyword in the aggregation calls.

234
00:27:59,540 --> 00:28:07,960
And of course, sort of importantly, it's really critical to differential privacy to be able to bound what a single user is able to contribute.

235
00:28:08,420 --> 00:28:21,240
So, you know, from the perspective of a particular partition, perhaps, you know, you only want a user to be able to contribute a single visit to a website.

236
00:28:21,500 --> 00:28:31,020
But perhaps for a salary, you'd want to allow them to contribute up to, you know, $1 million, $1 million, whatever seems reasonable there.

237
00:28:31,280 --> 00:28:37,700
Perhaps if you were contributing an average age or something, you'd want to bound people between 0 and 120.

238
00:28:38,320 --> 00:28:44,560
The more that you can definitely say about aggregation bounds, the more accuracy you can do.

239
00:28:44,560 --> 00:28:53,080
But of course, a lot of times when you're dealing with arbitrary data, machine learning, that sort of thing, you have no idea what bounds that are in the data.

240
00:28:53,080 --> 00:28:57,660
In fact, that's maybe the reason you're doing the analysis in the first place is to learn a bit more about the data.

241
00:28:58,480 --> 00:29:04,430
And so one of the other contributions of this work is automatic bounds determination.

242
00:29:05,840 --> 00:29:13,580
You want to be able to sort of get the best possible bounding on your data without paying for it very much.

243
00:29:13,580 --> 00:29:20,660
Once again, finding out global bounds that are differentially private on arbitrary functions is undecidable.

244
00:29:21,220 --> 00:29:28,200
So, you know, you can just sort of give up out of the gate and just sort of go to the next best thing, which is a good approximation.

245
00:29:28,240 --> 00:29:33,440
And so what we use when bounds are not provided is logarithmic histograms.

246
00:29:33,440 --> 00:29:36,940
Basically, you have partitions of increasing size.

247
00:29:37,260 --> 00:29:53,480
Doubling, for instance, allows you to get a reasonably good upper bound that might be off by a factor of two, which in terms of differential privacy actually doesn't cost you very much in terms of utility, but still gives you a really solid understanding of,

248
00:29:53,480 --> 00:29:56,760
you know, sort of the worst case upper bound.

249
00:29:56,760 --> 00:30:12,900
And what's really amazing about this is that, you know, even with our epsilon having to be split between the exploration bounds of the histogram and the actual computation, the accuracy is often still better than manually determined bounds.

250
00:30:13,720 --> 00:30:21,340
Again, just because you're oftentimes talking about worst case scenarios when you're determining bounds in a computation.

251
00:30:22,300 --> 00:30:26,180
And this is finding them sort of data dependent bounds.

252
00:30:26,520 --> 00:30:34,580
And typically, you know, you might require maybe 100 elements or fewer, depending on the nature of the calculation.

253
00:30:36,000 --> 00:30:43,280
Now, let me go back to our open sourcing availability and some action items for you.

254
00:30:45,020 --> 00:30:51,360
First, we would like to take part of our differentially private training that we're piloting with this audience.

255
00:30:51,360 --> 00:30:53,840
As a first step, please take our survey.

256
00:30:53,840 --> 00:30:55,760
And it only takes five minutes.

257
00:30:55,760 --> 00:31:02,620
It tries to figure out how much have you understood about differential privacy before you jump into the next topics.

258
00:31:03,120 --> 00:31:08,760
Then you can check another introductory video on differential privacy in that link.

259
00:31:10,700 --> 00:31:13,860
Third, you can try out some of our code labs.

260
00:31:13,860 --> 00:31:27,140
The link that's pointing out there points to a Go pipeline that you can build to produce differentially private metrics for a restaurant and its busy times.

261
00:31:27,640 --> 00:31:34,020
Fourth, if you're curious about differential privacy and learning more, you can check out the blog that we're linking.

262
00:31:35,340 --> 00:31:43,160
Finally, provide us some feedback on the overall training course and the materials that we've created for you.

263
00:31:43,160 --> 00:31:47,500
We're really looking forward to hearing more from your end.

264
00:31:47,500 --> 00:31:51,920
And with that, we'll open it up for questions.

265
00:31:58,990 --> 00:31:59,910
All right.

266
00:31:59,910 --> 00:32:02,670
Thank you for this terrific talk.

267
00:32:02,670 --> 00:32:07,290
This was differential privacy, more important than ever in the world of COVID-19.

268
00:32:07,670 --> 00:32:15,170
We have Aditi Joshi, Miguel Guevara, and Royce Wilson here to chat with us and answer some questions.

269
00:32:15,170 --> 00:32:18,390
First, I think, Aditi, you wanted to introduce the team.

270
00:32:52,290 --> 00:32:53,470
Hold on one moment.

271
00:32:53,470 --> 00:32:55,750
I think we're having an audio problem.

272
00:32:58,670 --> 00:33:01,030
We'll wait for a cue.

273
00:33:01,070 --> 00:33:04,030
In the meantime, thanks, everybody, for your patience.

274
00:33:04,030 --> 00:33:06,210
This is our glitched episode.

275
00:33:21,640 --> 00:33:27,280
And just as a reminder, you can submit any questions you have for the team into the Q&A channel on the Discord.

276
00:33:27,480 --> 00:33:32,180
You can find the link there at the link from the Twitch stream.

277
00:33:32,180 --> 00:33:33,600
You can also go to our website.

278
00:33:33,600 --> 00:33:35,160
It contains links to Twitch.

279
00:33:35,800 --> 00:33:37,460
Excuse me, to our Discord.

280
00:33:37,460 --> 00:33:37,820
I

281
00:34:02,990 --> 00:34:05,490
have her try speaking.

282
00:34:45,730 --> 00:34:49,790
So that it was as useful and practical to the audience as possible.

283
00:34:49,870 --> 00:34:53,510
And with that, I'm going to turn it over to Miguel and Royce to introduce themselves.

284
00:34:53,990 --> 00:34:54,550
All right.

285
00:34:54,550 --> 00:34:55,470
One moment.

286
00:34:55,470 --> 00:34:57,430
Let me check with our team behind the scenes.

287
00:34:57,430 --> 00:34:59,470
Do we have audio right now for our speakers?

288
00:35:02,860 --> 00:35:03,700
Okay, we do.

289
00:35:03,700 --> 00:35:03,940
Great.

290
00:35:03,960 --> 00:35:04,580
Fantastic.

291
00:35:04,580 --> 00:35:05,100
Wonderful.

292
00:35:05,100 --> 00:35:06,280
Thanks for that intro, Aditi.

293
00:35:06,280 --> 00:35:07,560
Miguel, take it away.

294
00:35:08,180 --> 00:35:08,980
Great.

295
00:35:09,340 --> 00:35:11,780
Thank you, everyone, for coming today to our talk.

296
00:35:11,780 --> 00:35:12,660
I'm Miguel.

297
00:35:12,660 --> 00:35:16,160
I'm a product manager working on Google's privacy team.

298
00:35:16,300 --> 00:35:26,040
Basically, I work with Royce and other engineers on the team on developing our internal differential private infrastructure that we recently open sourced.

299
00:35:29,540 --> 00:35:31,220
And then I am Royce.

300
00:35:31,220 --> 00:35:33,000
I'm a sophomore engineer at Google.

301
00:35:33,000 --> 00:35:35,640
I work on privacy infrastructure.

302
00:35:35,960 --> 00:35:40,360
I was also the lead author behind the paper that the talk is based on.

303
00:35:45,110 --> 00:35:45,990
Terrific.

304
00:35:45,990 --> 00:35:48,170
So we have a couple of questions.

305
00:35:48,770 --> 00:35:53,770
I'll start off with the question that I have, just taking the liberty and privilege to do so.

306
00:35:54,190 --> 00:35:58,810
Have you encountered any misunderstandings in your work about how Google uses differential privacy?

307
00:35:58,810 --> 00:36:02,910
And what have you found to be most effective in combating any of those misunderstandings?

308
00:36:04,330 --> 00:36:05,730
That's an interesting question.

309
00:36:05,910 --> 00:36:09,810
I wouldn't say it's misunderstandings on how Google uses differential privacy.

310
00:36:09,810 --> 00:36:14,730
I would say it's just your own misunderstanding about what differential privacy is.

311
00:36:14,730 --> 00:36:22,570
A lot of the times when we launch new features and when we open source things, people approach to us trying to use it.

312
00:36:22,570 --> 00:36:33,430
They're very excited because they sort of think that differential privacy is this magic wand that when it touches any sort of data, it suddenly transforms it into private data.

313
00:36:33,610 --> 00:36:38,990
And I think that the biggest misunderstanding is people confuse differential privacy a lot with synthetic data.

314
00:36:38,990 --> 00:36:43,790
So they believe that differential privacy can automatically turn things into synthetic data.

315
00:36:44,110 --> 00:36:46,790
And I think that's the biggest misunderstanding.

316
00:36:46,790 --> 00:36:55,990
And one thing that's, I think, important to highlight is that our open source offering helps people produce statistics in a differential private manner.

317
00:36:56,010 --> 00:37:04,230
So if any of you has one of those use cases, then I think that the open sourcing offering is a good place to start.

318
00:37:04,230 --> 00:37:11,130
And that's the way that we use it at Google to produce a lot of these statistical information in a private manner.

319
00:37:13,190 --> 00:37:13,870
Great.

320
00:37:13,870 --> 00:37:17,450
Any input from Aditi or Royce on that particular issue?

321
00:37:17,450 --> 00:37:19,410
No, I think Miguel captured it.

322
00:37:19,410 --> 00:37:20,270
Great.

323
00:37:21,270 --> 00:37:23,530
And so this is kind of a related question, I guess.

324
00:37:23,530 --> 00:37:30,810
Can you comment on what Google services, besides location visit and busy time reporting, are implementing differential privacy today?

325
00:37:30,810 --> 00:37:32,630
Can you give us a sense?

326
00:37:33,570 --> 00:37:34,170
Yeah.

327
00:37:34,170 --> 00:37:39,810
So the mobility reports also use differential privacy for all of their reporting.

328
00:37:40,150 --> 00:37:45,650
We have a lot of features on the backend that use differential privacy.

329
00:37:45,650 --> 00:37:54,630
So for instance, Maps has this way of trying to cache tiles that you'll probably use when you have no data.

330
00:37:54,630 --> 00:38:00,910
And the way that Maps does the ranking on the backend is by using differential privacy.

331
00:38:00,910 --> 00:38:06,230
Popular Dishes on Maps also uses differential privacy to do the ranking of the dishes.

332
00:38:06,530 --> 00:38:09,570
And those are some of the user-facing features that we have.

333
00:38:09,570 --> 00:38:14,770
However, we use differential privacy a lot for internal analysis.

334
00:38:14,770 --> 00:38:18,390
And that internal analysis informs new features.

335
00:38:21,190 --> 00:38:21,950
Great.

336
00:38:21,950 --> 00:38:27,410
I'm going to use the link to the COVID mobility reports in the Discord channel so people can reference it.

337
00:38:29,010 --> 00:38:32,390
All the short links from your slide deck into Discord as well.

338
00:38:32,390 --> 00:38:33,110
Fantastic.

339
00:38:35,110 --> 00:38:41,010
And then just more broadly, and this is sort of a big long-term question, what do you think is next for differential privacy?

340
00:38:41,010 --> 00:38:48,910
That could be sort of in terms of the academic work or in terms of the applied work that you see your team going with in the next several years?

341
00:38:49,470 --> 00:38:51,110
Royce, do you want to take that question?

342
00:38:51,610 --> 00:38:51,610
Yeah

343
00:38:54,710 --> 00:38:55,150
.

344
00:38:57,270 --> 00:38:59,910
Miguel might be more suited for this one, I think.

345
00:39:02,230 --> 00:39:03,650
Do you want to...?

346
00:39:03,650 --> 00:39:04,430
Okay.

347
00:39:04,570 --> 00:39:15,990
I think that the biggest academic frontier is improving the performance of differential privacy.

348
00:39:15,990 --> 00:39:20,630
At the moment, for certain use cases, you get very big hits in terms of utility.

349
00:39:20,630 --> 00:39:23,770
And therefore, it's not good for certain use cases.

350
00:39:23,770 --> 00:39:33,390
So I really hope that within the academic community, they can come up with new ways of doing differential privacy with less utility trade-offs.

351
00:39:33,390 --> 00:39:40,570
I think that's the other thing that I was thinking about is just make it generally more usable.

352
00:39:40,570 --> 00:39:46,850
At the moment, it requires a significant level of expertise to understand it and to implement it.

353
00:39:46,850 --> 00:39:58,150
And I hope that in 10 years or less, we get to the point where crypto is nowadays, where there are standard libraries and you can do crypto without being an expert.

354
00:39:58,150 --> 00:40:03,830
And you can rely on some other experts to do the right work so that you can be safe.

355
00:40:03,830 --> 00:40:17,670
So I hope that differential privacy reaches that point where it becomes so commonplace and a new default way of doing data analysis that is backed up by a lot of expert code that has been reviewed and vetted.

356
00:40:18,330 --> 00:40:22,070
And just like you don't roll your own crypto, you don't do the same thing with differential privacy.

357
00:40:22,070 --> 00:40:27,370
So the goal of our training is to really make it as accessible to everyone as possible.

358
00:40:27,370 --> 00:40:30,450
And so when I post the short links, please go through the training.

359
00:40:30,450 --> 00:40:34,870
If you feel like there's something missing, something's not cleared, give us that feedback.

360
00:40:34,910 --> 00:40:42,790
Our goal is to keep iterating on this training and to make it as easy to implement as possible for everyone across the board.

361
00:40:44,530 --> 00:40:45,350
Great.

362
00:40:45,350 --> 00:40:45,770
All right.

363
00:40:45,770 --> 00:40:49,670
Well, I think that's all the questions that we've got right now for the time being.

364
00:40:49,670 --> 00:40:53,990
And I will unleash you on the Discord to answer any further questions anybody may have.

365
00:40:53,990 --> 00:40:58,790
Thank you all so much for providing this valuable resource and for having this terrific talk.

366
00:40:59,290 --> 00:41:01,130
Have a terrific rest of your DEF CON.

367
00:41:01,210 --> 00:41:03,210
And our next talk will start at 1 p.m.

368
00:41:03,450 --> 00:41:03,970
Thank you so much.