[00:00.000 --> 00:03.700]  Hello, I am Miguel Guevara.
[00:03.800 --> 00:09.920]  And I'm Brian Gibson. I work in privacy infrastructure at Google, in particular on differential privacy.
[00:10.080 --> 00:15.060]  And we will talk to you about today our differential privacy.
[00:15.420 --> 00:19.260]  Before we start, let me play this video for you.
[00:21.140 --> 00:25.260]  At Google, we use data to make our services work better for you.
[00:25.260 --> 00:29.880]  And it's our responsibility to keep your data private, safe, and secure.
[00:30.000 --> 00:34.880]  That's why we continually invest in tools that protect individual privacy.
[00:35.020 --> 00:38.320]  Differentially private analysis is one of those tools.
[00:39.100 --> 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.
[00:46.980 --> 00:54.680]  With differential privacy, we can protect an individual's data while still preserving the usefulness of the data at scale.
[00:54.680 --> 00:57.340]  Let's take a closer look at how it works.
[00:57.340 --> 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.
[01:03.880 --> 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.
[01:12.720 --> 01:19.460]  The analysis adds noise to results so you can look at how crowded a place is without identifying who was there.
[01:19.460 --> 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.
[01:31.380 --> 01:37.820]  Many important research, business, and social questions can be answered by analyzing large data sets.
[01:37.820 --> 01:44.240]  Which is why, after years of development, Google has made its differential privacy library open source.
[01:44.240 --> 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.
[01:58.920 --> 02:05.200]  Differential privacy is just one of many ways we build privacy protections into our products.
[02:05.200 --> 02:11.520]  And we will continue to innovate to new technologies that keep your data private, safe, and secure.
[02:12.680 --> 02:24.320]  Great. 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.
[02:24.860 --> 02:32.760]  The naive question that we always get is, why don't we just remove identifiers to anonymize data?
[02:33.360 --> 02:41.500]  Unfortunately, removing identifiers might not be good enough, as well as removing PII.
[02:41.520 --> 02:48.600]  There are multiple well-known data breaches resulting from publishing the quote-unquote de-identified data.
[02:48.600 --> 02:55.240]  One classical example involves the publication of de-identified medical records in the state of Washington.
[02:55.240 --> 03:01.360]  Those records could be partially joined with the voting registry using birthday and postcode.
[03:01.360 --> 03:06.680]  This was sufficient to identify a majority of individuals in the data set.
[03:06.680 --> 03:16.260]  In another classical example, as a part of a competition in 2006 that intended to improve the movie recommendation system,
[03:16.260 --> 03:22.240]  Netflix published movie ratings from its users. The records had the user identifiers removed,
[03:22.240 --> 03:29.180]  but researchers could partially join these records with IMDB databases, which were tied to identity.
[03:29.540 --> 03:35.480]  Such a join made possible to partially tie the full history of movie ranking to the user identifiers.
[03:35.480 --> 03:42.540]  This is a classical example of joining de-identified data sets and re-identifying some of the users.
[03:42.680 --> 03:49.560]  Finally, de-identified search history can also, in certain cases, reveal the identity of a user.
[03:49.660 --> 03:56.600]  So, there is a pattern here. Even if the records are published without direct identifying information,
[03:56.600 --> 04:05.460]  the content of those records together with some auxiliary information may make re-identification possible in certain cases.
[04:05.480 --> 04:09.840]  Thus, we need something better than de-identification in general.
[04:10.340 --> 04:16.300]  The second question that is very common to have is, well, why don't we just aggregate data?
[04:16.560 --> 04:24.680]  In fact, it is a very well-known technique to publish aggregated statistics with buckets of users.
[04:24.740 --> 04:33.240]  Usually, this involves grouping by a set of features. For example, grouping by restaurant visits, by location, and hour.
[04:33.240 --> 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.
[04:45.580 --> 04:52.060]  Now, let me explain to you why we need differential privacy and how it works.
[04:52.060 --> 04:58.240]  Let's imagine you are attending a two-day conference and the moderator shares some insights about the audience.
[04:58.340 --> 05:02.580]  Here, you can see the country of origin of the participants on day one.
[05:02.580 --> 05:08.480]  It's aggregated, so it does not reveal anything about any of the individuals in the room, right?
[05:08.700 --> 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.
[05:17.760 --> 05:25.080]  On day two, the moderator shows the stats for the day. They look pretty similar, right?
[05:25.080 --> 05:33.380]  Except, someone has been paying attention and noticed that there was only one new person on day two.
[05:33.700 --> 05:37.960]  And when they look at the data from both days together, look at that.
[05:38.940 --> 05:43.160]  Can you tell where the specific individual is coming from? Yes.
[05:43.420 --> 05:53.780]  Germany. This is how, with two aggregated datasets, the moderator has managed to leak information about a particular participant.
[05:54.620 --> 06:02.760]  K-anonymity provides stronger guarantees than simple de-identification, but it is not perfect either.
[06:02.760 --> 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.
[06:12.860 --> 06:18.680]  It's not helpful that I'm indistinguishable from K other users having the same condition.
[06:18.680 --> 06:28.120]  While I cannot be associated with any particular record in the database, my sensitive attribute in that example is revealed.
[06:28.120 --> 06:38.220]  Here is another example. Imagine two aggregate buckets, 99 users plus me and 99 users without me.
[06:38.220 --> 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.
[06:50.600 --> 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.
[07:03.440 --> 07:10.480]  Those type of attacks aren't always feasible or relevant, but they cannot be excluded in general.
[07:10.620 --> 07:19.650]  Is there a better way to define anonymity? I think so. Let's use differential privacy.
[07:20.650 --> 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.
[07:34.070 --> 07:49.630]  Look at the day one stats, how these stats look compared to the real numbers. They're slightly different. So yes, it is less precise, but you still get the same insights about the statistical trends.
[07:52.170 --> 08:07.510]  Similarly, let's look at day two. Same thing. 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.
[08:07.510 --> 08:15.410]  And you know it's not worth trying since you know the numbers were changed a little. This is the principle behind differential privacy.
[08:15.570 --> 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.
[08:35.810 --> 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.
[08:48.010 --> 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.
[09:01.990 --> 09:08.450]  This threshold is what defines how much the output is allowed to change, and it's called epsilon.
[09:09.050 --> 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.
[09:17.010 --> 09:22.750]  We publish our code in an open source library so that others can reuse our work.
[09:22.750 --> 09:29.890]  As I mentioned before, differential privacy has a lot of implementation subtopics, and it is hard to get it right.
[09:29.890 --> 09:36.150]  As all of you in the crypto community probably know, people should enroll their own crypto.
[09:36.570 --> 09:42.230]  And this is also a really good advice for differential privacy and their implementations.
[09:42.430 --> 09:46.510]  Reusing a hardened implementation is generally a good idea.
[09:46.890 --> 09:54.150]  We open source the technology, and you can read more of the articles that were written back then.
[09:55.210 --> 09:59.510]  I'll now give you some insights as to how we've used the technology.
[10:01.350 --> 10:05.130]  You're probably aware of the Google Mobility Reports.
[10:05.130 --> 10:12.430]  These Mobility Reports were a response to the emerging crisis back in March around COVID-19.
[10:12.430 --> 10:20.890]  They provide policymakers with an idea of mobility trends at a city and state level for different categories.
[10:21.030 --> 10:27.610]  Before I continue going into the Mobility Reports, let me talk to you a little bit about location data at Google.
[10:29.430 --> 10:35.270]  Location data is an optional account feature that says where you go in your private timeline.
[10:35.270 --> 10:39.390]  It's off by default and can be paused or unpaused anytime.
[10:39.990 --> 10:44.390]  From a product perspective, it's available on Android and iOS.
[10:44.990 --> 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.
[10:56.690 --> 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.
[11:07.090 --> 11:12.270]  More recently, we announced that auto deletion is now automatic for new accounts.
[11:12.590 --> 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.
[11:22.690 --> 11:25.230]  Now, let me talk to you about the reports.
[11:25.230 --> 11:29.270]  The reports are the Mobility Reports.
[11:29.270 --> 11:35.630]  These reports were the first product that Google launched that was built with differential privacy from the ground up.
[11:36.130 --> 11:44.570]  The reports do not share data about any individual's locations, movements, or conflicts.
[11:44.950 --> 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.
[11:55.230 --> 11:59.590]  People can turn off that setting at any time and delete their history.
[12:00.130 --> 12:07.310]  We took the additional step of utilizing differential privacy to ensure that no individual can be identified.
[12:07.870 --> 12:10.990]  So how exactly are we using differential privacy?
[12:11.030 --> 12:17.310]  First, we produce a count of people at certain locations within a geographical area.
[12:17.310 --> 12:21.930]  Let's say that we count the visitors to parks in Vegas on a given day.
[12:21.930 --> 12:26.590]  That might give us a number of 8,238 people.
[12:27.030 --> 12:31.170]  Secondly, we add what we call some random noise to that number.
[12:31.310 --> 12:37.550]  Let's assume, for example, that we added an artificial number of 79.
[12:37.870 --> 12:42.950]  We add these two and get a new count of 8,317.
[12:43.310 --> 12:50.270]  This count is differentially private, and we can now use it to calculate the metrics that we publish.
[12:51.150 --> 12:59.170]  This is an example of a differentially private query that we do to produce reports like the mobility report.
[12:59.310 --> 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.
[13:10.210 --> 13:13.650]  In this case, an anonymization count.
[13:14.910 --> 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.
[13:26.310 --> 13:30.330]  Second, we compute those same metrics for a given day.
[13:30.330 --> 13:36.910]  Let's say for Friday, March 27, 5,000 people visited parks in the same region.
[13:36.910 --> 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.
[13:45.530 --> 13:49.210]  And then we repeat this process for all the metrics that we are producing.
[13:49.210 --> 13:53.910]  And therefore, all the metrics that we're reporting are produced with differential privacy.
[13:54.730 --> 14:00.410]  There are some interesting practical aspects on how we use these reports.
[14:00.410 --> 14:05.070]  We limit the number of times that a person is counted on each metric.
[14:05.070 --> 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.
[14:12.390 --> 14:18.330]  This prevents specific patterns like delivery worker people from being too revealing.
[14:19.490 --> 14:23.310]  Second, we remove metrics that are too noisy.
[14:23.450 --> 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%.
[14:33.570 --> 14:40.630]  And finally, if you're curious, we published a technical blog detailing the anonymization process.
[14:42.570 --> 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.
[14:51.950 --> 14:56.050]  The US Census is using it for its 2020 census.
[14:56.050 --> 14:59.450]  Facebook recently released an URL data set.
[14:59.690 --> 15:02.530]  Apple has been using it.
[15:02.530 --> 15:04.550]  We released it on Chrome a while ago.
[15:04.630 --> 15:09.950]  And it's also open source for machine learning purposes on TensorFlow privacy.
[15:10.250 --> 15:15.650]  Now, Brian will talk to you a little bit more about building the infrastructure.
[15:15.830 --> 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.
[15:22.290 --> 15:28.150]  But I want to take you through three really critically important pieces of that journey, which is building strong foundations,
[15:28.150 --> 15:31.190]  building frameworks that are familiar to potential users,
[15:31.190 --> 15:35.190]  and helping users to assess the privacy utility frontier.
[15:35.490 --> 15:41.270]  So the infrastructure that we build starts with the differentially private foundational libraries.
[15:41.290 --> 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.
[15:50.290 --> 15:57.490]  A lot of times users are trying to do experiments or prototypes before actually building a project,
[15:57.490 --> 16:01.170]  and this ideation stage is perfect for differential privacy,
[16:01.170 --> 16:05.870]  because it can provide a very good way of getting trends or overall statistics,
[16:05.870 --> 16:12.510]  and allows people to assess whether it's even worth continuing development on a particular project.
[16:13.470 --> 16:20.970]  So the foundational library that we use here at Google is actually the same as the one that we open sourced and published,
[16:20.970 --> 16:23.150]  so that others could reuse our work.
[16:23.150 --> 16:27.310]  For us, it's always been important to provide transparency around our implementation.
[16:28.070 --> 16:31.710]  Hopefully folks have had a chance to poke around the library.
[16:32.690 --> 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.
[16:39.730 --> 16:49.410]  I think the analogy we oftentimes use with differential privacy is best compared to cryptography, right?
[16:49.450 --> 16:54.570]  There you say, don't roll your own crypto, same thing goes for differential privacy.
[16:54.570 --> 16:59.230]  There are a lot of gotchas, there's a lot of difficulty involved in rolling it out correctly,
[16:59.230 --> 17:05.050]  and an incorrect or partial implementation of DP is in some cases worse than none at all,
[17:05.050 --> 17:08.830]  because you might have a gaping hole in your system that you're not aware of.
[17:08.830 --> 17:11.990]  So reusing a hardened implementation is just a good idea.
[17:13.370 --> 17:17.290]  So the second step we did was to build a SQL engine,
[17:17.290 --> 17:21.810]  and there were lots of languages we could have used, lots of ways we could have gotten about this,
[17:21.810 --> 17:24.750]  but SQL really made the most sense, right?
[17:24.750 --> 17:29.030]  It's the language that most developers are familiar with,
[17:29.030 --> 17:34.390]  you don't have to be an expert to get in and start doing an analysis on data sets,
[17:34.930 --> 17:37.670]  and so it just felt like the right choice.
[17:37.670 --> 17:43.470]  So I'm just going to give a little bit of an overview of some of the challenges involved in this.
[17:43.810 --> 17:48.170]  So one of the big ones is that SQL allows pretty much anything.
[17:48.170 --> 17:50.710]  A lot of implementations are actually Turing-complete,
[17:50.710 --> 17:52.950]  so enforcing differential privacy,
[17:53.250 --> 17:59.590]  while at the same time allowing non-experts to write SQL that they're basically familiar with is a big challenge.
[17:59.710 --> 18:04.650]  A lot of challenges come up around things like joins between different data sets,
[18:04.650 --> 18:08.570]  or cardinality changes, if you're allowed to just multiply rows endlessly,
[18:08.570 --> 18:12.350]  lots of privacy implications come out of that.
[18:13.130 --> 18:20.210]  So the basis of differential privacy is really about quantifying the effect that a single user can have on output.
[18:20.710 --> 18:24.590]  And part of a differentially private SQL engine really has to have the same property.
[18:24.590 --> 18:31.070]  So what we do is we actually split SQL statements into per-user transforms and cross-user aggregations.
[18:31.070 --> 18:36.750]  The per-user transforms are very generous, you can do essentially arbitrary, even Turing-complete SQL.
[18:36.750 --> 18:45.530]  The cross-user transforms are a restricted set of aggregation functions that are much more protected from a privacy standpoint.
[18:52.100 --> 19:05.240]  Finally, you really want to ensure correctness when you're talking about any type of privacy-sensitive infrastructure.
[19:05.540 --> 19:11.400]  And unfortunately, proving that something you've built is differentially private is really hard.
[19:11.400 --> 19:14.100]  It's so hard, it's actually provably undecidable.
[19:14.820 --> 19:22.840]  That said, as part of the foundational libraries, we employ stochastic model checking as part of regression testing.
[19:22.840 --> 19:27.460]  Now obviously this isn't a sufficient guarantee for differential privacy by itself,
[19:27.460 --> 19:37.900]  but it really quickly catches violations, both obvious and subtle, and provides a stable backdrop to more traditional privacy verification work and expert analysis.
[19:38.160 --> 19:44.080]  So this is just an example of a differentially private query, we'll get into this a little bit more later.
[19:44.100 --> 19:51.280]  It's meant to be user-centric, it highlights the fact that you're doing an anonymous query right up front.
[19:51.300 --> 20:02.320]  And in general, it basically looks like a normal SQL query with just a few more keywords and syntactic sugar.
[20:02.620 --> 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.
[20:15.280 --> 20:20.020]  So that was a really cursory overview of this particular implementation.
[20:20.200 --> 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.
[20:28.280 --> 20:32.600]  And we'll be getting into some of the more detailed math later in the talk.
[20:32.880 --> 20:37.620]  So we're going to spend some time to return to the math behind differential privacy a little bit.
[20:37.620 --> 20:43.520]  We talked kind of about how our SQL engine was structured and a little bit about differential privacy.
[20:43.560 --> 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.
[20:53.320 --> 20:59.100]  Of course, what we're actually saying when we say some sort of probabilistic statement about any differentially private system
[20:59.440 --> 21:04.980]  is that adding or removing a user from a data set doesn't change the results that much.
[21:04.980 --> 21:09.220]  That much actually has a really rigorous technical definition.
[21:10.040 --> 21:12.800]  There's two parameters, there's epsilon and delta.
[21:12.880 --> 21:18.380]  Epsilon, we generally think about in a sort of a Bayesian context,
[21:18.380 --> 21:26.020]  which is to say that supposing I have some notion of a detail of a user that you're trying to target, right?
[21:26.020 --> 21:29.900]  Supposing you're about 60% sure that they live in Wisconsin,
[21:29.900 --> 21:36.380]  and the attacker is attempting to improve that confidence from their perspective, ideally to 100%.
[21:36.880 --> 21:44.220]  Well, it turns out that there's a really nice translation between how much an attacker can improve their confidence
[21:44.220 --> 21:50.080]  in knowing something and the epsilon that you choose.
[21:50.080 --> 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%.
[21:58.200 --> 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.
[22:05.920 --> 22:10.740]  And so you have this nice principled trade-off between risk and accuracy,
[22:10.740 --> 22:19.160]  since the epsilon has the strongest influence on sort of the quality, the accuracy, the utility of the output results.
[22:20.480 --> 22:24.280]  Delta is a much easier concept to understand and explain.
[22:24.280 --> 22:31.580]  It's basically our out to say that we basically made a differentially private engine,
[22:31.580 --> 22:36.020]  but occasionally, very occasionally, it's not differentially private.
[22:36.020 --> 22:38.940]  So delta is the probability of catastrophic failure.
[22:39.160 --> 22:45.320]  There are lots of ways to think about it, but the way we generally talk about it is perhaps the number of output rows
[22:45.320 --> 22:48.740]  that are not strictly differentially private.
[22:48.740 --> 22:52.740]  Now, of course, you don't know which rows those are, so there's always sort of a reasonable doubt.
[22:52.740 --> 23:01.540]  But this allows you to really quantify a baseline of failure modes that your output data set can have.
[23:01.820 --> 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.
[23:10.880 --> 23:18.340]  And because the nature of the noise that we use is a decaying exponential,
[23:18.340 --> 23:22.340]  the delta that is sort of induced by some of the math,
[23:23.420 --> 23:31.120]  actually can be sort of smaller than is machine representable in many cases, as we'll get into in a few minutes.
[23:31.220 --> 23:34.020]  So oftentimes, you don't actually have to worry about a delta,
[23:34.020 --> 23:37.820]  but it's sort of important enough that you should be able to reason about it.
[23:38.420 --> 23:42.780]  So just returning earlier, we talked about the privacy model,
[23:42.780 --> 23:47.580]  per-user transformation that's very generous, more restricted cross-user aggregation.
[23:48.340 --> 23:49.540]  And that's why we apply to SQL.
[23:49.960 --> 23:57.720]  Let's take kind of an example of a typical privacy-sensitive query that seems pretty innocuous.
[23:57.720 --> 24:03.580]  We're counting up the number of visits to a website based on browser agent.
[24:03.800 --> 24:09.620]  So a quick look through the logs reveals that a single user used a particular agent.
[24:09.900 --> 24:15.120]  And already, we've kind of re-identified an individual without doing anything more than counting statistics.
[24:15.120 --> 24:20.000]  So we can see the problem with kind of a non-differentially private environment already.
[24:20.440 --> 24:26.780]  So classically, sort of naively, one thing that one does in differential privacy
[24:26.780 --> 24:32.000]  is they add some kind of noise that satisfies differential privacy to counts.
[24:32.000 --> 24:35.020]  And so in this case, we go through all the browser agents,
[24:35.020 --> 24:40.820]  we adjust the counts, plus or minus, a small amount of noise dependent on epsilon.
[24:41.540 --> 24:43.880]  And in general, you might think, oh, we're good.
[24:43.880 --> 24:49.500]  Except that a browser agent can be an arbitrary string, right?
[24:49.500 --> 24:52.000]  So this could be a made-up thing.
[24:52.000 --> 24:55.120]  Essentially, from the position of an attacker,
[24:55.120 --> 25:01.560]  you have to assume that browser agent is an unbounded space of potentially arbitrarily linked strings.
[25:01.560 --> 25:06.980]  Which means that if you see a value there in your logs,
[25:07.580 --> 25:11.200]  then at least one user must have registered that.
[25:11.200 --> 25:13.060]  There are lots of ways of dealing with this.
[25:13.060 --> 25:15.260]  You could generate a bunch of random strings,
[25:15.260 --> 25:20.240]  and sort of give essentially zero noise to each of those.
[25:20.420 --> 25:25.600]  But you, for an unbounded space, would have to generate unboundedly many browser agents.
[25:25.600 --> 25:28.920]  So the way that we do it is we basically just filter
[25:28.920 --> 25:35.320]  and say that at least tau users need to contribute to any particular partition.
[25:35.500 --> 25:39.160]  It turns out that there's a direct line between tau and delta.
[25:39.160 --> 25:43.600]  So it's really easy to reason about what sort of the correct tau or the correct delta
[25:44.160 --> 25:46.860]  needs to be in terms of the existing parameters.
[25:47.940 --> 25:52.340]  As I said earlier, the nature of the noise is a decaying exponential.
[25:52.340 --> 25:55.180]  So even for 50 users or 100 users,
[25:55.180 --> 25:59.340]  you might be at a vanishingly small, perhaps unmeasurably small,
[25:59.340 --> 26:04.760]  probability that a particular partition is surfaced incorrectly.
[26:05.780 --> 26:07.780]  So you think, we're done, right?
[26:07.780 --> 26:11.360]  Well, almost. There's a little bit more nuance to this.
[26:11.360 --> 26:16.580]  And this is kind of one of the big strengths of this type of a privacy model in SQL
[26:16.580 --> 26:18.180]  is that you can enforce it.
[26:18.900 --> 26:23.800]  So an individual user in any particular session might be using a single browser.
[26:23.800 --> 26:26.600]  But across all their sessions, they may have used many browsers,
[26:26.600 --> 26:28.300]  unboundedly many, in fact.
[26:28.360 --> 26:30.480]  And from the perspective of differential privacy,
[26:30.480 --> 26:33.760]  we're trying to protect a user, not a browser.
[26:33.760 --> 26:41.260]  So if a user has used 10 different browsers and everybody else has just used one,
[26:41.260 --> 26:47.040]  potentially you violated kind of the epsilon guarantees of your system,
[26:47.040 --> 26:48.280]  if you allow that.
[26:48.280 --> 26:54.620]  So the way that we deal with that is with reservoir sampling of a user's contributions
[26:54.620 --> 26:58.160]  and then limiting those contributions.
[26:58.160 --> 27:01.720]  So a user might be able to contribute to 10 separate partitions
[27:01.720 --> 27:04.380]  or three or one or whatever seems appropriate.
[27:04.380 --> 27:09.360]  And again, it's another parameter that can be chosen by the user.
[27:09.480 --> 27:14.520]  But you can also sort of choose one based on an appropriate epsilon and delta.
[27:15.020 --> 27:20.160]  So again, it's just about giving an engine the flexibility to represent
[27:20.160 --> 27:23.580]  sort of both utility and privacy needs at the same time.
[27:24.040 --> 27:26.780]  And this is basically the model in a nutshell.
[27:26.780 --> 27:30.960]  Now, of course, if you were requiring users to write exactly the syntax every time,
[27:31.720 --> 27:32.120]  that's not possible.
[27:32.120 --> 27:38.240]  And so the new syntax is introduced with anonymization is basically just a clever rewriter
[27:38.240 --> 27:42.700]  that is doing all of that in the background to the AST of the SQL
[27:43.280 --> 27:48.540]  and allowing people to write basically SQL that they're familiar with.
[27:48.540 --> 27:52.580]  You see a few more keywords in here, obviously, the privacy parameters,
[27:52.580 --> 27:58.300]  the anonymization keyword in the aggregation calls.
[27:59.540 --> 28:04.500]  And of course, sort of importantly, it's really critical to differential privacy
[28:04.500 --> 28:07.960]  to be able to bound what a single user is able to contribute.
[28:08.420 --> 28:14.720]  So, you know, from the perspective of a particular partition,
[28:14.720 --> 28:21.240]  perhaps, you know, you only want a user to be able to contribute a single visit to a website.
[28:21.500 --> 28:28.180]  But perhaps for a salary, you'd want to allow them to contribute up to,
[28:28.180 --> 28:31.020]  you know, $1 million, $1 million, whatever seems reasonable there.
[28:31.280 --> 28:34.920]  Perhaps if you were contributing an average age or something,
[28:34.920 --> 28:37.700]  you'd want to bound people between 0 and 120.
[28:38.320 --> 28:42.740]  The more that you can definitely say about aggregation bounds,
[28:42.740 --> 28:44.560]  the more accuracy you can do.
[28:44.560 --> 28:47.620]  But of course, a lot of times when you're dealing with arbitrary data,
[28:47.620 --> 28:53.080]  machine learning, that sort of thing, you have no idea what bounds that are in the data.
[28:53.080 --> 28:55.900]  In fact, that's maybe the reason you're doing the analysis in the first place
[28:55.900 --> 28:57.660]  is to learn a bit more about the data.
[28:58.480 --> 29:04.430]  And so one of the other contributions of this work is automatic bounds determination.
[29:05.840 --> 29:10.800]  You want to be able to sort of get the best possible bounding on your data
[29:10.800 --> 29:13.580]  without paying for it very much.
[29:13.580 --> 29:17.120]  Once again, finding out global bounds that are differentially private
[29:17.120 --> 29:20.660]  on arbitrary functions is undecidable.
[29:21.220 --> 29:23.980]  So, you know, you can just sort of give up out of the gate
[29:23.980 --> 29:26.380]  and just sort of go to the next best thing,
[29:26.380 --> 29:28.200]  which is a good approximation.
[29:28.240 --> 29:33.440]  And so what we use when bounds are not provided is logarithmic histograms.
[29:33.440 --> 29:36.940]  Basically, you have partitions of increasing size.
[29:37.260 --> 29:42.620]  Doubling, for instance, allows you to get a reasonably good upper bound
[29:42.620 --> 29:44.920]  that might be off by a factor of two,
[29:44.920 --> 29:47.840]  which in terms of differential privacy actually doesn't cost you very much
[29:47.840 --> 29:52.300]  in terms of utility, but still gives you a really solid understanding
[29:52.300 --> 29:56.760]  of, you know, sort of the worst case upper bound.
[29:56.760 --> 30:01.380]  And what's really amazing about this is that, you know,
[30:01.380 --> 30:05.240]  even with our epsilon having to be split between the exploration bounds
[30:05.240 --> 30:09.060]  of the histogram and the actual computation,
[30:09.060 --> 30:12.900]  the accuracy is often still better than manually determined bounds.
[30:13.720 --> 30:18.460]  Again, just because you're oftentimes talking about worst case scenarios
[30:18.460 --> 30:21.340]  when you're determining bounds in a computation.
[30:22.300 --> 30:26.180]  And this is finding them sort of data dependent bounds.
[30:26.520 --> 30:30.160]  And typically, you know, you might require maybe 100 elements
[30:30.160 --> 30:34.580]  or fewer, depending on the nature of the calculation.
[30:36.000 --> 30:39.860]  Now, let me go back to our open sourcing availability
[30:39.860 --> 30:43.280]  and some action items for you.
[30:45.020 --> 30:49.120]  First, we would like to take part of our differentially private training
[30:49.120 --> 30:51.360]  that we're piloting with this audience.
[30:51.360 --> 30:53.840]  As a first step, please take our survey.
[30:53.840 --> 30:55.760]  And it only takes five minutes.
[30:55.760 --> 30:58.780]  It tries to figure out how much have you understood
[30:58.780 --> 31:02.620]  about differential privacy before you jump into the next topics.
[31:03.120 --> 31:05.460]  Then you can check another introductory video
[31:05.460 --> 31:08.760]  on differential privacy in that link.
[31:10.700 --> 31:13.860]  Third, you can try out some of our code labs.
[31:13.860 --> 31:19.200]  The link that's pointing out there points to a Go pipeline
[31:19.200 --> 31:23.140]  that you can build to produce differentially private metrics
[31:23.140 --> 31:27.140]  for a restaurant and its busy times.
[31:27.640 --> 31:30.380]  Fourth, if you're curious about differential privacy
[31:30.380 --> 31:34.020]  and learning more, you can check out the blog that we're linking.
[31:35.340 --> 31:40.900]  Finally, provide us some feedback on the overall training course
[31:40.900 --> 31:43.160]  and the materials that we've created for you.
[31:43.160 --> 31:47.500]  We're really looking forward to hearing more from your end.
[31:47.500 --> 31:51.920]  And with that, we'll open it up for questions.
[31:58.990 --> 32:02.670]  All right. Thank you for this terrific talk.
[32:02.670 --> 32:05.030]  This was differential privacy, more important than ever
[32:05.030 --> 32:07.290]  in the world of COVID-19.
[32:07.670 --> 32:11.230]  We have Aditi Joshi, Miguel Guevara, and Royce Wilson here
[32:11.230 --> 32:15.170]  to chat with us and answer some questions.
[32:15.170 --> 32:18.390]  First, I think, Aditi, you wanted to introduce the team.
[32:52.290 --> 32:55.750]  Hold on one moment. I think we're having an audio problem.
[32:58.670 --> 33:01.030]  We'll wait for a cue.
[33:01.070 --> 33:04.030]  In the meantime, thanks, everybody, for your patience.
[33:04.030 --> 33:06.210]  This is our glitched episode.
[33:21.640 --> 33:24.260]  And just as a reminder, you can submit any questions you have
[33:24.260 --> 33:27.280]  for the team into the Q&A channel on the Discord.
[33:27.480 --> 33:32.180]  You can find the link there at the link from the Twitch stream.
[33:32.180 --> 33:35.160]  You can also go to our website. It contains links to Twitch.
[33:35.800 --> 33:37.460]  Excuse me, to our Discord.
[33:37.460 --> 34:05.490]  I have her try speaking.
[34:45.730 --> 34:49.790]  So that it was as useful and practical to the audience as possible.
[34:49.870 --> 34:52.210]  And with that, I'm going to turn it over to Miguel and Royce
[34:52.210 --> 34:53.510]  to introduce themselves.
[34:53.990 --> 34:57.430]  All right. One moment. Let me check with our team behind the scenes.
[34:57.430 --> 34:59.470]  Do we have audio right now for our speakers?
[35:02.860 --> 35:05.100]  Okay, we do. Great. Fantastic. Wonderful.
[35:05.100 --> 35:07.560]  Thanks for that intro, Aditi. Miguel, take it away.
[35:08.180 --> 35:11.780]  Great. Thank you, everyone, for coming today to our talk.
[35:11.780 --> 35:16.160]  I'm Miguel. I'm a product manager working on Google's privacy team.
[35:16.300 --> 35:19.500]  Basically, I work with Royce and other engineers on the team
[35:19.500 --> 35:23.240]  on developing our internal differential private infrastructure
[35:23.540 --> 35:26.040]  that we recently open sourced.
[35:29.540 --> 35:33.000]  And then I am Royce. I'm a sophomore engineer at Google.
[35:33.000 --> 35:35.640]  I work on privacy infrastructure.
[35:35.960 --> 35:40.360]  I was also the lead author behind the paper that the talk is based on.
[35:45.110 --> 35:48.170]  Terrific. So we have a couple of questions.
[35:48.770 --> 35:50.970]  I'll start off with the question that I have,
[35:50.970 --> 35:53.770]  just taking the liberty and privilege to do so.
[35:54.190 --> 35:56.790]  Have you encountered any misunderstandings in your work
[35:56.790 --> 35:58.810]  about how Google uses differential privacy?
[35:58.810 --> 36:00.270]  And what have you found to be most effective
[36:00.270 --> 36:02.910]  in combating any of those misunderstandings?
[36:04.330 --> 36:05.730]  That's an interesting question.
[36:05.910 --> 36:09.810]  I wouldn't say it's misunderstandings on how Google uses differential privacy.
[36:09.810 --> 36:11.550]  I would say it's just your own misunderstanding
[36:11.550 --> 36:14.730]  about what differential privacy is.
[36:14.730 --> 36:18.630]  A lot of the times when we launch new features
[36:18.630 --> 36:21.110]  and when we open source things, people approach to us
[36:21.110 --> 36:23.430]  trying to use it. They're very excited
[36:23.430 --> 36:26.410]  because they sort of think that differential privacy
[36:26.410 --> 36:30.470]  is this magic wand that when it touches any sort of data,
[36:30.470 --> 36:33.430]  it suddenly transforms it into private data.
[36:33.610 --> 36:35.870]  And I think that the biggest misunderstanding is
[36:35.870 --> 36:38.990]  people confuse differential privacy a lot with synthetic data.
[36:38.990 --> 36:41.610]  So they believe that differential privacy can automatically
[36:41.610 --> 36:43.790]  turn things into synthetic data.
[36:44.110 --> 36:46.790]  And I think that's the biggest misunderstanding.
[36:46.790 --> 36:49.630]  And one thing that's, I think, important to highlight
[36:49.630 --> 36:52.650]  is that our open source offering helps people
[36:52.650 --> 36:55.990]  produce statistics in a differential private manner.
[36:56.010 --> 36:59.750]  So if any of you has one of those use cases,
[36:59.750 --> 37:02.450]  then I think that the open sourcing offering
[37:02.450 --> 37:04.230]  is a good place to start.
[37:04.230 --> 37:06.190]  And that's the way that we use it at Google
[37:06.190 --> 37:09.310]  to produce a lot of these statistical information
[37:09.310 --> 37:11.130]  in a private manner.
[37:13.190 --> 37:17.450]  Great. Any input from Aditi or Royce on that particular issue?
[37:17.450 --> 37:19.410]  No, I think Miguel captured it.
[37:19.410 --> 37:23.530]  Great. And so this is kind of a related question, I guess.
[37:23.530 --> 37:26.010]  Can you comment on what Google services,
[37:26.010 --> 37:28.230]  besides location visit and busy time reporting,
[37:28.230 --> 37:30.810]  are implementing differential privacy today?
[37:30.810 --> 37:32.630]  Can you give us a sense?
[37:33.570 --> 37:38.110]  Yeah. So the mobility reports also use differential privacy
[37:38.110 --> 37:39.810]  for all of their reporting.
[37:40.150 --> 37:43.810]  We have a lot of features on the backend
[37:43.810 --> 37:45.650]  that use differential privacy.
[37:45.650 --> 37:50.050]  So for instance, Maps has this way of trying to cache tiles
[37:50.470 --> 37:54.630]  that you'll probably use when you have no data.
[37:54.630 --> 37:58.430]  And the way that Maps does the ranking on the backend
[37:58.430 --> 38:00.910]  is by using differential privacy.
[38:00.910 --> 38:03.850]  Popular Dishes on Maps also uses differential privacy
[38:03.850 --> 38:06.230]  to do the ranking of the dishes.
[38:06.530 --> 38:09.570]  And those are some of the user-facing features that we have.
[38:09.570 --> 38:14.770]  However, we use differential privacy a lot for internal analysis.
[38:14.770 --> 38:18.390]  And that internal analysis informs new features.
[38:21.190 --> 38:21.950]  Great.
[38:21.950 --> 38:23.910]  I'm going to use the link to the COVID mobility reports
[38:23.910 --> 38:27.410]  in the Discord channel so people can reference it.
[38:29.010 --> 38:32.390]  All the short links from your slide deck into Discord as well.
[38:32.390 --> 38:33.110]  Fantastic.
[38:35.110 --> 38:37.150]  And then just more broadly,
[38:37.150 --> 38:38.750]  and this is sort of a big long-term question,
[38:38.750 --> 38:41.010]  what do you think is next for differential privacy?
[38:41.010 --> 38:43.790]  That could be sort of in terms of the academic work
[38:43.790 --> 38:47.510]  or in terms of the applied work that you see your team going with
[38:47.510 --> 38:48.910]  in the next several years?
[38:49.470 --> 38:51.110]  Royce, do you want to take that question?
[38:51.610 --> 38:55.150]  Yeah.
[38:57.270 --> 38:59.910]  Miguel might be more suited for this one, I think.
[39:02.230 --> 39:03.650]  Do you want to...?
[39:03.650 --> 39:04.430]  Okay.
[39:04.570 --> 39:09.490]  I think that the biggest academic frontier
[39:09.490 --> 39:15.990]  is improving the performance of differential privacy.
[39:15.990 --> 39:17.730]  At the moment, for certain use cases,
[39:17.730 --> 39:20.630]  you get very big hits in terms of utility.
[39:20.630 --> 39:23.770]  And therefore, it's not good for certain use cases.
[39:23.770 --> 39:27.010]  So I really hope that within the academic community,
[39:27.010 --> 39:30.370]  they can come up with new ways of doing differential privacy
[39:30.510 --> 39:33.390]  with less utility trade-offs.
[39:33.390 --> 39:36.190]  I think that's the other thing that I was thinking about
[39:36.190 --> 39:40.570]  is just make it generally more usable.
[39:40.570 --> 39:44.130]  At the moment, it requires a significant level of expertise
[39:44.130 --> 39:46.850]  to understand it and to implement it.
[39:46.850 --> 39:49.410]  And I hope that in 10 years or less,
[39:49.410 --> 39:51.490]  we get to the point where crypto is nowadays,
[39:51.490 --> 39:54.530]  where there are standard libraries
[39:54.530 --> 39:58.150]  and you can do crypto without being an expert.
[39:58.150 --> 40:01.510]  And you can rely on some other experts to do the right work
[40:01.510 --> 40:03.830]  so that you can be safe.
[40:03.830 --> 40:06.050]  So I hope that differential privacy reaches that point
[40:06.050 --> 40:08.290]  where it becomes so commonplace
[40:08.290 --> 40:11.430]  and a new default way of doing data analysis
[40:11.430 --> 40:15.470]  that is backed up by a lot of expert code
[40:15.470 --> 40:17.670]  that has been reviewed and vetted.
[40:18.330 --> 40:19.850]  And just like you don't roll your own crypto,
[40:19.850 --> 40:22.070]  you don't do the same thing with differential privacy.
[40:22.070 --> 40:24.690]  So the goal of our training is to really make it
[40:24.690 --> 40:27.370]  as accessible to everyone as possible.
[40:27.370 --> 40:29.350]  And so when I post the short links,
[40:29.350 --> 40:30.450]  please go through the training.
[40:30.450 --> 40:32.250]  If you feel like there's something missing,
[40:32.250 --> 40:34.870]  something's not cleared, give us that feedback.
[40:34.910 --> 40:36.910]  Our goal is to keep iterating on this training
[40:36.910 --> 40:40.730]  and to make it as easy to implement as possible
[40:40.730 --> 40:42.790]  for everyone across the board.
[40:44.530 --> 40:45.770]  Great. All right.
[40:45.770 --> 40:48.150]  Well, I think that's all the questions that we've got right now
[40:48.150 --> 40:49.670]  for the time being.
[40:49.670 --> 40:51.430]  And I will unleash you on the Discord
[40:51.430 --> 40:53.990]  to answer any further questions anybody may have.
[40:53.990 --> 40:56.590]  Thank you all so much for providing this valuable resource
[40:57.370 --> 40:58.790]  and for having this terrific talk.
[40:59.290 --> 41:01.130]  Have a terrific rest of your DEF CON.
[41:01.210 --> 41:03.210]  And our next talk will start at 1 p.m.
[41:03.450 --> 41:03.970]  Thank you so much.