Differential Privacy and the US Census
Dwork, Cynthia
Differential privacy is a mathematically rigorous definition of privacy tailored to statistical analysis of large datasets. Differentially private systems simultaneously provide useful statistics to the well-intentioned data analyst and strong protection against arbitrarily powerful adversarial system users - without needing to distinguish between the two. Differentially private systems 'don't care' what the adversary knows, now or in the future. Finally, differentially private systems can rigorously bound and control the cumulative privacy loss that accrues over many interactions with the confidential data. These unique properties, together with the abundance of auxiliary data sources and the ease with which they can be deployed by a privacy adversary, led the US Census Bureau to adopt differential privacy as the disclosure avoidance methodology of the 2020 decennial census. This talk will motivate the definition of differential privacy, reflect on the theory-meets-practice experiences of the decennial census, and highlight a few pressing challenges in the field.
 Today's topic is going to be differential privacy and the US census. And it's an extremely timely topic, and I'm not very ambitious in terms of the talk, but differential privacy will be the confidentiality protection mechanism for the 2020 US decennial census. So for the first time, privacy will be protected by a formal method. And pods and sigmod have played a very interesting role, an important role in the history of this field, so I wanted to highlight that. And at the very least, what I hope is that when you leave this talk, you are able to explain to other people what differential privacy is. And later in the talk, you'll see why I think that's so important. Okay, so in a nutshell, there are really two kinds of data analysis, a statistical data analysis. So one kind is to try to statistically understand the population as a whole. So for example, this is exactly what we do with census data. It's what we do with financial data. This is the brainchild of Elizabeth Warren, the Consumer Financial Protection Bureau. And one of the goals of the Consumer Financial Protection Bureau is to examine loan data, housing loan data in particular, for evidence of discrimination because of historical discrimination in loans in the United States. Another thing that you might be doing is analyzing cell information, images, learning to, you know, training a classifier to distinguish cancerous from non-cancerous cells, working on the data of individuals. And so the idea in all of this is to somehow extract some general or statistical knowledge while protecting the privacy of the individuals who are in the data set. The other kind of data analysis is when you're looking for a needle in a haystack. So this would have been the case, for example, with the so-called Total Information Awareness System, which was processing huge troves of data looking for terrorists. So if you want to do privacy-preserving data analysis, differential privacy is something that's appropriate to this first task, where you're trying to learn statistical trends of the population as a whole, and it's not relevant to the needle in the haystack task. And in fact, if what you're trying to do is find the needle in the haystack and you want to somehow preserve privacy for the non-needles, so to speak, you need a different solution. Differential privacy won't do it for you. So it's the wrong tool for that. Now, statistics in general feel private. That is, so a statistic is a quantity that's computed from a sample, and it's supposed to tell us about the population as a whole. So everybody's intuition is that the statistic somehow is not talking about the individuals within the sample, but is about a bigger thing. And for example, two data sets that are collected independently, but using the correct sampling technology from the same population should tell us essentially the same things about the population. And our sense of the privacy of a statistic is, I think, derived from this fact, that there's a kind of intuition of, gee, nobody knows that I was in the sample. I could claim that I opted out, or I could claim that nobody asked me to be in the sample. And it's not about me, it's about the population as a whole, and the proof of it somehow is that, well, if someone had collected a different data set that didn't happen to contain me, the same things would have been learned. So this intuition is good, and it's on the right track, but it's not quite enough to give us privacy. And the role of differential privacy is to kind of help this intuition along and make an honest intuition out of it. So statistics, differential privacy is supposed to give us this kind of statistical out opt-in intuition for all computations, including total population counts. And that's what a census is. So here's how we're going to abstract the problem. We're going to have here, I have an analyst, data analyst on the right, and I have a database on the left, or a data set. And the data set contains a lot of very, very useful but potentially sensitive information. In our abstraction, our analyst will interact with the data set by posing queries and getting responses. So a query could be something very simple, like how many people in the data set are over six feet tall, or a query could be something much more complex. Give me the following set of marginals, or carry out at least squares regression, or do the following study of the data. And then we get an answer. And based on that answer, so adaptively based on that answer, the analyst can ask a new question. And our privacy is going to be against the analyst. So we want to keep the analyst from somehow violating the privacy of the members of the database. But we have to give some information to the analyst, because that's the whole point. The abstraction is general enough to capture the fact that you might have different people asking questions of the same data set, and they might or might not be conferring, first of all, in their choice of questions, and secondly, in their desires to compromise the privacy of the individuals in the data set. And it's also general enough to capture the fact that researchers carry out studies. They look at some data, they publish some results, and then new studies are created based on the findings of the old studies, follow-up questions, or the first study might suggest some other new areas of inquiry. And people may go back, possibly, to the same data set or an overlapping data set and ask questions. So it's a very, very general formulation. Now the problem of privacy-preserving data analysis dates back at least to 1965 randomized response of Warner. And so it is an old problem, and when I began this work, I was working with my then intern, Adam Smith, and our driving scenario was that of the US Census Bureau. Our idea was that, first of all, the motivation should be fairly clean here. It's an analysis of the people's data to allocate the resources of the people, hopefully for the benefit of the people, and there is a legal mandate for privacy. So there's a law about privacy of the responses in the Census. So there was real motivation, we felt, on the part of the curators of the data to ensure privacy. We'll talk more about the Census, of course, later. So here's an example, flossing. Flossing will be our favorite. Going back to the intuition about statistics being private, I said that this intuition needs some help, and here's the problem. Suppose we have exact answers to the following two questions. How many living physics Nobel laureates floss regularly, and how many male living physics Nobel laureates floss regularly? If we had exact answers to both of those questions, then we would know whether or not Donna Strickland flosses regularly, and this would be a compromise of her privacy. So even though both of these could be very large sets, it's their intersection or their set difference being so small that is causing us a problem. This differencing attack is just one example of how seemingly innocuous questions, possibly posed over very large sets of data, can be combined to compromise privacy. And more generally, we have the fundamental law of information recovery, which says that intuitively if you have overly accurate estimates of too many statistics, then this is completely non-private. You can totally break privacy. So this was a seminal result of D'Norah Nisim, and many variants of this basic theorem have been proven. The definition of overly accurate will change according to the number of queries. So if you're going to have a very large number of queries, then to prevent total loss of privacy, you need to have a lot of noise in the answers. But if you have fewer queries, you can get by with smaller noise. And this result applies equally to interactive and non-interactive systems. So I gave you a picture before where I was clearly indicating interaction, question one answer, one question, two answer, two. But I said that those questions could be pretty broad, like give me the following collection of marginals. So the same is true here. The question might be, give me a table that lets me reconstruct the answers to the following very large set of queries. So early on when we were doing this work, I got a call from a medical researcher who said exactly, can't you just give me a noisy table that will let me get answers to all of the questions I want to ask as I figure out what they are? And the answer is no. If I gave you something that would in fact let you accurately answer or relatively overly accurately answer too many of those questions that you're choosing on the fly, then it would be a violation of the fundamental law of information recovery. So even if I hand you a blob that you can compute on and get relatively accurate answers from, the same problem would show up. So what's the definition of differential privacy and how did we get there? This is a picture of Cecilia Helena Payne Gapushchin, 1900 to 1979. She was among the first women to obtain a PhD in astronomy and she ascertained the temperatures of different classes of stars and estimated the great abundance of hydrogen in them, much more than there is in Earth. And so her dissertation work disputed the incorrect belief at the time that the Earth and the stars had the same composition. So here she is, Payne is in this database. What kind of privacy should we guarantee for her? What does it mean to say that we are protecting her privacy against a data analyst? So the first thing that we would try is a definition that says that the analyst can't learn anything about Payne that she didn't already know about Payne. Nothing new. And this is a definition that's very evocative of semantic security for a crypto system and it is also the disideratum that the statistician, Tordelinius, articulated for what he called the statistical database in 1977. So the problem with this definition is if that's your goal, then what's the point? So for example, suppose that I'm from Mars and I believe that all humans have two left feet. And in particular, I think that Payne has two left feet. I carry out a statistical analysis of the dataset and I learned that the vast majority of humans have one left foot and one right foot. So now my beliefs about Payne have changed and I think that she has one left foot and one right foot. I have learned something new about her, something I didn't know before. Have I violated her privacy? So that's a definitional question. You get to make a decision about that and your definition, your intuition may say, yes, this is a privacy violation, but it was not our intuition. We said this is not a privacy violation and the reason it's not a violation is that the same things would have been learned about Payne even if she had it opted out or even if she had been replaced in the dataset with another random member of the population. So this is Henrietta Swan Leavitt, another physicist who was the first to know the relation between certain variable stars' brightnesses and the period over which that brightness varied. And that, her observations gave rise to a law which proved a valuable means for estimating distances in space. Okay. So we're going to be learning, if we would be learning the same things, independent of whether any individual opts in or opts out of the dataset, our intuition is that it's not a privacy violation for these people. So that's led to the English language definition of differential privacy, that the outcome of any analysis should be essentially equally likely independent of whether any individual opts in or opts out of the dataset. So even an analyst who knows the whole rest of the database and who thinks there are two possible worlds, it's this database all by itself, that's the bottom picture, or it's this database plus the data of Payne, that's the other database. Even such an analyst shouldn't be able to determine which of the two databases is actually the case. Okay. So an adversary, again, knowing both datasets in their entirety should never be able to distinguish which of the two cases is the reality. And so you have to ask, what's the source of uncertainty when I say that the outcome of an analysis is essentially equally likely? What is that likelihood over? So our algorithms are going to flip coins. Our guarantee is going to be worst case for all pairs of databases that differ in the data of just one person. And the probability spaces will always be coin flips of the algorithm. And that's good because we are the algorithm designers, we're the good guys, we can make sure that the algorithm flips its coins. So if you're not used to thinking about similar probability distributions, or if you're ever going to be explaining this definition to somebody else, the following metaphor might be useful. Think about a fair coin versus a very slightly biased coin. So your fair coin has probability a half, or specifically, let's say, 500 out of 1,000 of coming up heads. And our slightly biased coin will have probability, say, 501 over 1,000 of coming up heads. So think about the coin now as playing the role of the database. And we have an algorithm which is going to flip a coin and tell you whether it's heads or tails. So given one of these coins, the flipping algorithm will now produce either heads or tails. And the probability distribution on the outcomes is, as you can see plainly, nearly the same for the two coins. The probability of heads in one is 500 over 1,000 and in the other is 501 over 1,000. So they're nearly the same. And given one or even several coin flips of the same coin. An adversary can never actually determine which of the coins is the true one with any degree of certainty. Now, it's a very strong definition of privacy, almost the same output distributions independent of the participation of any individual. Why does it allow us to do any kind of data analysis at all? So some of you know something about machine learning and you know that stability, that is the stability of the output of the algorithm to small changes in the data set is actually essential for the ability to generalize from your data set to the population from which the data set is drawn. So stability preserves privacy, but it also prevents overfitting. And so that's just a little bit of an intuition as to why, even though we think of sort of adding noise or randomness as interfering with utility and putting privacy into conflict with utility, it actually is helping learning. Privacy and generalization turn out to be aligned. So here's the formal definition now of differential privacy. Our algorithms are called M for mechanism. And we need the concept of adjacent data sets. And those are pairs of data sets exactly as we've been discussing. These are data sets that are almost identical, but one data set contains the data of just one more person. Oops, I want to go back to this definition. One more person. Now you have an algorithm, the algorithm maps databases to some output space, and so we can look at output events called, say, S. And the definition of differential privacy, and this is due to joint work with McSherry, Nisseman Smith, says that the probability that we observe this event, any event, S, when the algorithm is running on database X, is at most e to the epsilon times the probability that we see S when we're running on database Y. So what is this epsilon? In differential privacy, privacy is not binary, but rather there is a measure of privacy loss, which is called typically epsilon. And this is controlling the ratio of the probabilities of observing S on adjacent data sets X and Y. Those are data sets that differ in the data of just one person. And the probability spaces here are over the coins of the algorithm, our mechanism M. So if you're not so comfortable with e to the epsilon, when epsilon is small, this is approximately one plus epsilon. So this is a statement, differential privacy is a statement about the behavior of the algorithm M. It has absolutely nothing to do with who knows what. I don't know why this is advancing. It has nothing to do with who knows what now or in the future. So if you see an output, it's like seeing a head or tail from that coin flipping algorithm. No matter what other information you get, other than telling you which of the two databases it is, which of the two coins it is, you won't be able to determine which of the databases it is. And the intuition, of course, is that if you can't even tell whether or not I'm in the data set, you certainly can't be learning details about me that are specific to me and aren't just general statements about the population as a whole. So this says you can learn about pain, but you can only learn things that you could have learned without her participation. And as I said, we call this a bounded ratio condition. I've just rewritten the inequality. And notice that the roles of X and Y are completely symmetric in this definition. We said that X and Y are adjacent, meaning one of them is larger than the other and the larger one contains the data of just one more person. But the inequality holds whether the larger one is X or the larger one is Y. So going back to the needle in the haystack, I said that differential privacy is the wrong tool for privately finding the needle in the haystack. And the reason is that differential privacy protects the outliers. It protects every individual. And indeed, this was intentional. Our feeling was that the outliers needed protection perhaps more than everybody else. So if you think of X as the haystack and Y as the haystack without the needle, what you're going to observe in outputs from a differentially private algorithm will be essentially the same, independent even of the presence of the needle. So it certainly isn't going to help you to find the needle. So here are some key properties of differential privacy that follow immediately from the definition. First it's resilient to present and future information from other sources. It also composes gracefully and automatically. That is, we understand the cumulative privacy loss over multiple computations on the same or on intersecting data sets. In the very worst case, the losses add up. More advanced analyses involve understanding that the privacy loss is in fact a random variable. And nicely, sometimes it's positive, but sometimes it's negative. So that we do get cancellation effects and there are concentration results. That's beyond the scope of today's talk. As we understand how privacy loss accumulates over multiple computations, differential privacy becomes programmable. That is, you can define small, differentially private primitives and then combine them to carry out in a differentially private way more complex statistical analyses. And you can control by setting the epsilon parameters accordingly, you can control the cumulative loss. And this is what makes it so strong. There is, to my knowledge, no other method that permits this. So composition is the sine qua non of differential privacy. So here's one technique just to give you a flavor. There are many techniques for achieving differential privacy and many little computational primitives that you might have. Here is one extremely useful computational primitive. So suppose what you are interested in is computing some function F on your data set. A key quantity for us is going to be how much the value of any single individual can swing, how much the data of any single individual can swing the value of the function F. So we look at the maximum over all adjacent data sets. Those are data sets differing in the data of just one person of F of X minus F of Y. And we take that absolute value, that's our sensitivity or delta one. And the theorem is the following. So this is the Laplace noise distribution. And it takes a parameter and you can see a bunch of different values of the parameter. Probably you can't read the font. But the idea is when the parameter is larger, the data, the spread is fatter, the curve is fatter. And I've centered it at zero. So what does the theorem say? It says that if you want to release the value of F on your data set in a differentially private way, it suffices to first compute F on your data set, that's F of X, and then add Laplace noise that's drawn with parameter, the sensitivity divided by epsilon. So let's just talk about that parameter for a moment. Intuitively, if the data of one person can really swing the value of the function F, then you want a fat curve. And indeed delta one is sitting up there in the numerator, so a bigger sensitivity gives you a fatter curve. If you want very good privacy, then again, you want a fat curve. You don't want a curve that's really peaked right over F of X. And so really good privacy corresponds to really small epsilon. And here is epsilon in the denominator, so small epsilon again blows up our parameter B. So things are in their right place. And in fact, we'll see in a moment why this works. But here's the first observation. We tended to think about epsilon as a constant. So for thinking about epsilon as a constant, a draw from this distribution is, sorry, so think about a counting query. How many people in the data space are over six feet tall? The sensitivity of this counting query is one, because the addition or deletion of any one person can change the count of the number of people who are over six feet tall by just one. And for any counting query, the sensitivity is one. And so if epsilon is a constant, what we're adding here is noise that we expect will have magnitude one over epsilon or a constant. So the noise is roughly one for a single counting query. Now, I promised a quick proof of this. So the proof is simple, and it relies on the fact that the probability density function for the Laplace noise distribution, when the parameter is some value B, will drop off exponentially, so P of t will drop off exponentially in the magnitude of t divided by B. So for any t, the ratio of the probabilities that we will see the outcome t when, or the density at t, when the database is x and when the database is y, is given by this expression on the left. And just using the triangle inequality, that gives us e to the magnitude f of x minus f of y divided by the parameter B. That magnitude is by definition bounded by the sensitivity delta one, and the parameter B is delta one over epsilon, and so we get this bound of e to the epsilon. Now suppose we want to look at a number of different queries or some k-ary function. You can think of k different queries as a k-ary function, but it could also just be something else in high dimensional space. Then the same theorem and the same proof works, but for a slightly different definition of sensitivity. Instead of the absolute value of f of x minus f of y, it's the L1 norm now, which is the sum of the absolute values of the individual coefficients. But the same theorem holds, and what we're doing now is we're drawing fresh random noise scaled to this new sensitivity for each of the k different components of the output. So in particular, what that would say would be that for k counting queries, you would need noise that scales to k. I mentioned work that involves looking at privacy loss as a random variable and using cancellation, and with that you can get a relaxed notion of differential privacy where this value turns into something it's closer to square root of k. So now though something really interesting happened. In particular, think about a histogram query. So in a histogram query, you have your space of individuals and you carve it up into some arbitrary number of cells of arbitrary shape, and you want to know how many individuals are in each of the different cells. But a histogram query has sensitivity 1. That is, adding or deleting a single person can change the count in only one cell and can change that count by only one. And so the sensitivity of a histogram query is actually, again, just one. Even though it might be a large, large number of cells, you only now have to add noise scale to 1 over epsilon rather than k over epsilon to each of these cells. All right. So three notes from the history of pods in SIGMOD. So this fundamental law of information reconstruction, the seminal work in this area, was published here in 2003 at pods. And then it won the test of time award. And section three of that paper says that it's not a heavily looked at section. It says that you can get meaningful privacy analysis for almost n squared queries. And so the power of the reconstruction theorem is it says, look, we don't know what you mean by privacy. But we're going to show you something bad that can happen. And you're going to agree that whatever you thought of privacy as, this bad thing violates that. So that was really powerful. But there wasn't yet a real definition of privacy. And in fact, when Colby came to visit me at Microsoft, and I had been thinking about privacy for the hotmail user database, which at the time had like 500 million users. And he was showing me some attack. And the attack took n squared queries. And I was thinking, you know, n is 500 million n squared, not so likely. And I said, well, what happens if we cut off the questions after a little while? I mean, you don't like sneak off and secretly ask 500 million queries, let alone that number squared. And we worked on this, and we were able to repurpose an argument that Colby and Erit had for some other thing, and show that we got some kind of meaningful notion of privacy. So but as I said, we didn't yet have the definition of differential privacy. And two years later, also here at PODS, there was another paper, this was with Blum, McSherry, and Niseem. And there what we said was, okay, we understand how to, with this sort of clumsy definition of privacy, how to ask privacy preserving counting queries, let's look at that as a computational primitive and see what we can do with it. And then we showed that you could carry out a lot of common data mining tasks, like a version of the perceptron algorithm and singular value decomposition and K-means computations, and in fact, anything learnable in the statistical queries learning model in a differentially private way. And this sort of algorithmic beginning, I think, was key. So PODS played a really key role in this history. And it's, there were other publications about differential privacy and other interesting work on privacy in general here, but I'm just mentioning three. In 2009, Frank McSherry in SIGMOD published a paper on what he called pink or privacy integrated queries. And this is a general programming platform to facilitate programming with differential privacy, including monitoring of the privacy loss budget, how much privacy loss has been happening. And I wanted to particularly mention that because it's winning the SIGMOD Test of Time award this year, so congratulations to Frank. Now, there are lots of algorithms for many different tasks, and there are also relaxed studies of lots of different things that are related to differential privacy, and in fact, the fields has kind of come to encompass all of these. Relaxations for privacy loss that I mentioned before. Things like studies of lower bounds on sample complexity, lower bounds on computational complexity, economics perspectives. This is all like from the outside, right, this is all work done in DP. There are applications of differential privacy also to other fields. So there are results that came in geometry from insights derived from differential privacy, also in economics, in online learning, and most recently in a paper by Scott Aronson and Guy Rothblum in gentle measurements in quantum. So there's something I think very fundamental to computing with a little bit of noise that seems to be helping in lots of different directions. Just want to mention before getting onto the discussion of the census, one surprising application of differential privacy, and that is that it neutralizes the risks to validity that are caused by adaptivity. So choosing your next question based on the answer to the previous questions. So this is a very, this is a risk always in data exploration where you sort of trawl around in the data looking for stuff, and so it's going to eliminate the sources of p-hacking and overfitting that come from adaptivity. And I only have time to give a little bit of an intuition, but here's the intuition. So fix a query queue, any query that you want to know something about for your population. And then go off and recruit a database X, and you're going to now evaluate this query on your database and try to learn something about your population as a result. So of course, with high probability, the database that you go out and recruit will be somehow representative of the population with respect to Q. This is why statistics works. This just, that's how it works. You have this thing you want to study, you go and you get a sample of the population and you study it on the population, and you expect that it's telling you about the population as a whole. That's why it works. So if I think now of p-hacking and overfitting as kind of an adversarial attempt to find a query for which the dataset is not representative, differential privacy is going to protect. So we have this initial intuition, or this initial fact. Now you could reverse the order of the steps if you're careful. So first recruit a database using proper sampling technology. Now without looking at the database, choose your query. Well of course the query is still independent of the database, so you're in the same situation that you were in before and you're really unlikely to choose a query for which your database is not representative of the population as a whole. Just as, because you've done something completely equivalent to what happened in the previous case. So now suppose during the course of interacting with your dataset, the analyst can find a query for which the dataset is not representative. Then intuitively she must have learned a lot about the database because we just saw that when she didn't know anything about the database, she was really unlikely to come up with such a query. And so differential privacy prevents the analyst from learning enough about the dataset to find a query on which the dataset is not representative. So differential privacy today, it's being used a lot in industry. In Apple, Google, Microsoft and Uber, for example, a lot of this work is done in what's called the local model. Meaning that in the pictures I've been showing you, there's a dataset that's been collected or curated and the analyst interacts with the dataset. In many of the industrial applications, raw data aren't being gathered from the clients, but rather privacy is being rolled in at the client level and this privacy preserving version of the data is being sent up to the server. And in industry parlance, this is called moving the trust boundary out to the client. So certainly Apple and Google and Microsoft are doing things in that model. Now Facebook has recently announced a secure and private artificial intelligence scholarship aimed to equip students with privacy preserving technologies such as federated learning, differential privacy and encrypted computation. And a high up person at LinkedIn tells me that LinkedIn is investing heavily in differential privacy and is, by the way, almost all of these companies are recruiting in this area, so center students for jobs could be very, very exciting time. The oldest deployment of differential privacy, large scale deployment is within a Census Bureau product called On the Map, which is a website that allows the public to learn where people work and where workers live. And recently there's been new work based on census data in the Opportunity Atlas, mapping the childhood roots of social mobility. So this is work by the economist Raj Chetty and colleagues that have deployed something very close to differential privacy in constructing this Opportunity Atlas. And I will say more about this later on in the talk. Now every decade the U.S. government carries out a complete enumeration of people living in the United States. The enumerated population in each state serves as the basis for apportionment of the 435 representatives in the House of Representatives. And in addition, this enumeration is, decides where hundreds of billions of dollars in federal financing is allocated. It also is, this information is also used for enforcing the Voting Rights Act and in redistricting. Okay, in the 2010 census, completely typically, 7.7 billion statistics were released from the data that were collected by census. And there are about some 300,000 individuals. And in light of these reconstruction attacks that I've been talking about, John Aboud, who is the Chief Scientist and Associate Director of Research and Methodology at the Bureau, decided that census should check to see what was the nature of the privacy protection, which is mandated by law, what was the nature of the privacy protection against these sorts of reconstruction attacks. And he looked at the 2010 data. So he knows what was released to the public, and he also knows what was collected because he's at the census. And his conclusion was, as you can see, that technical advances revealed a new vulnerability, allowing people to reconstruct data from tables that were previously assumed to be privacy preserving. And this is a slide from a talk that John Aboud gave in February of this year. He talked a little bit about his attack. And so these are his slides. And essentially, what they did was, first of all, they took all of the released information, and from that, they sort of reconstructed a whole bunch of putative individuals, of everybody in the data set. So that means that they wrote down a collection of attributes. This is without names, but a collection of attributes for each of the individuals, supposedly, in the census. And then they linked these putative people to commercially available data sets that contained names. So what do I mean by linking? I mean, you have basically the, you have a bunch of attributes in your putative reconstructions, and in the public data set, you have some of these attributes and the names, and you match them up, and now you have names for the people in your data set. So they did a lot of linking. And they weren't able to link everybody, but they were able to link many. And when they did this, they got hold of now the names for these putative people where they thought they had success. And then they were able to look at the census data to see did they get the names correct, and moreover, did they reconstruct the attributes correctly for those people? And what they found was that they had perfectly reconstructed 17% of the population. That's 52 million people. And the specific things that they were able to reconstruct for these people, the harms that they envisioned, is that an attacker carrying out the same reconstruction would be able to learn people's self-response for race and ethnicity. Now, yeah, okay. You'll see in a little bit, I'll show you the census form. It doesn't have much more than that. But there's another census form which is not part of the decennial census, which is much more rich, and the privacy harms could be more dramatic. For example, you could learn if somebody was adopted or not. Okay. So Abeld says, we fixed this for the 2020 census by implementing differential privacy. So what do you think the response was on the part of people who work with census data? Were they thrilled that they were now sort of going to be morally in the clear because there was no privacy compromise? Well, no. And in fact, this is greeted with a lot of concern and anxiety. So first of all, there were simply people who say, well, the old protections worked well and the law doesn't care what you learn about people. It only cares whether or not you can match a record to a name. If the law doesn't care what you can learn about people, then I don't understand the point of the law. And in fact, this is a very interesting question, but okay. And then there was a lot of concern about utility in general. So what happens when you ask questions and require a certain amount of accuracy and you sort of use up the privacy budget? You can't go any further because the fundamental law is about to kick in. Huge amounts of money have been spent gathering data for the census. It's the largest peacetime mobilization. And also for other surveys by federal statistical agencies, just billions of dollars are spent gathering these information. What happens when we can't use them anymore? All right. So these are real concerns, and I don't, as a computer scientist, I don't have answers to these questions, but it's important to sort of think again about the context. People share their data because they are assured of confidentiality. That really is drawn into stark relief when you think about what's been happening in the United States and the push, for example, to include a citizenship question, which at least temporarily has been pushed back, but we don't know whether that's going to stay. The Supreme Court said we don't like your justification, but you can try to come up with a justification that we do like. Okay. So assuming, though, that we're going forward with differential privacy, let's talk about some of the specific challenges. So one of them I have already alluded to. It's the allocation of the privacy resource. So in some sense, we have a privacy budget, which is a cap on the cumulative privacy loss that we think we ought to be tolerating. So first of all, how do you choose this privacy cap? How do you choose this budget? And who should choose this budget? The question makes sense for census, but it also makes sense for the various industrial uses. And once you have chosen a budget, there's a finiteness to everything. And census has to figure out among the questions that it is going to answer or among the statistics and tables that it's going to release, which ones should be given priority? Which ones should be given the best accuracy and get to use up more of the privacy budget? And which ones have to have less good accuracy and use up less of the budget? And this is not the kind of question that census has had to confront in the past. So they're trying very hard to find out from their users, what do you need? What are the queries that you need to be able to answer? Now this question about how and when to allocate, I mean, how to allocate the budget, this is one where perhaps economists have something to say. And in fact, John A. Bowden and Ian Schmouta have a paper about exactly this question. And they say that, and I'm quoting now, economists recognize this is a problem of resource allocation. We propose an economic framework for solving it. Statistical agencies must allocate information in their collected data between two competing uses, production of statistics that are sufficiently accurate, balanced against the protection of privacy for those in the data. We combine the economic theory of public goods with cryptographic methods from computer science to show that social welfare maximization can and should guide how statistical agencies manage this tradeoff. And the paper is very, very interesting. Okay. What's another problem? Another problem is that the people who work from the census data and the released statistics, so historians, sociologists, demographers, economists, are simply not trained to interact with the data in a differentially private way. They're not trained to ask queries and get responses. If you take a class in statistics, the first thing that you're told is, look at the data. Well, you can't look at the data in our methodology. You can't see raw data. You have to ask queries and get differentially private responses. Now, you might say, if you have a database of 300 million people, what does it mean to look at the data anyway? Aren't you, in fact, always looking at some statistic of the data or some illustration of the data of some sort and can't these things be done in a differentially private way? Maybe often the answer is yes, but still, the people who work with the data are not accustomed to this. And in no way do I want to minimize the difficulties here. This is a sea change in the way people have to operate. Another thing is that they have to be trained to deal with noise. Social privacy intentionally adds noise at various points in the computations. People are used to thinking of things that the Census Bureau releases as actually being noise free. It's not true. They've always been adding noise in one way or another. They've always been doing something in order to protect privacy. It just hasn't been enough, and that was what the results of the 2010 attack showed us. But everybody is used to thinking of everything that's released as being ground truth. Here you have to learn to adjust for the noise. The nice thing about differential privacy is the methods are completely public, and a trained analyst can, in fact, adjust for the noise. And this is different from how things were in the past, but you have to learn to do it. Now the Census Bureau goes to a lot of effort in their work to kind of make some of the artifacts of differential privacy invisible to the user. So for example, in differential privacy we add noise, and we might be looking at a count, and the count that's released might be negative, or it might not be an integer. And these are fine. We understand how to interpret a negative count. It means that the true count is very small, and the noise pushed it negative. Okay, fine, not a problem. We know that there aren't really a negative number of people, and similarly with nonintegrality. But when I say they go through a lot of noise, I mean they're solving integer programming problems in order to produce nice, integral things. Some day, perhaps, people can learn to deal with non-integer negative things or inconsistent counts because you've added noise differently in different places. And again, if you understand what's going on, you can cope with this, but that requires a high degree of sophistication. And we're definitely not there yet. And finally, a lot of research remains on a purely technical level. So we know how to do a lot of things very well using differential privacy, and there are a lot of things we might want to do that we don't yet know how to do well. The field is still relatively young. There's essentially no work on differentially private data cleaning, or we need to do more work in order to investigate things like tales of a distribution. Social scientists will often tell you that all the interesting stuff happens in the outliers. I have no answer there. That's my needle in a haystack. And I'm also not enough of a data analyst to know how I should interpret the statement. But maybe some of you do. Now, I've been talking about the decennial census. So this is actually a picture of the entire 2010 decennial census form. As the website said, 10 questions, 10 minutes. So what are the things that are being asked? Because I'm sure you can't see the font. There's a householder who is supposed to fill out the form. And in fact, information has to be given for every member of the household. But so for each person, first of all, how many people are living in the home as of this certain date? How many other people often stay in the home? Is the home in a house, is it an apartment, is it a mobile home? Phone number, name, sex, and age of each person in the house. And then questions about ethnicity and race. So Hispanic or Latino origin, and there are a number of categories there, and race. And there are several categories there. And people can check all of the boxes that apply to them. And then finally, there's a question about whether this person ever stays anywhere else. So for example, in college or in a military barracks or in jail, for that matter. So this is the easy case. And why do I say this is the easy case? Well, it turns out that there's 44 bits of information collected per person. Not that much in these fields, not including the name, of course. Every year, a random subsample of the US population also fills out another form. So this is, I think, a 5% I'm not sure sample of the population. Fills out another form called the American Community Survey. And this is what used to be called the long form, but now this is done every year on a rolling basis. So here are the things that are covered in the community survey. Building ancestry, journey to work, computer and internet use, disability, employment, family and relationship to the householder, fertility, food stamps, grandparents as caregivers, health insurance coverage, Hispanic origin, home heating fuel, housing costs for owners, industry occupation and class of worker, marital status and history, ownership, home value and rent, place of birth and citizenship and year of entry, plumbing, kitchen and telephone service, residence one year ago and migration, school enrollment, sex, vehicles available, veteran status, the year built and the year moved in. So you can see that this is an extremely rich collection of information about each person. If things are difficult now with this form, what's going to happen with the ACS? Okay. So one thing that people talk about is a different mode of interaction with the database. So an example is restricted access data centers. This is a picture of Steve Feinberg pictured with his wife Joyce. Steve was a renowned statistician and an expert in disclosure limitation among other fields. And early conversations with Steve starting in 2004 or 2005 led to close ties between members of several communities. For example, this is how the differential privacy people were brought into contact with the labor economist John Aboud who is now the chief scientist at the census. And the field of differential privacy has benefited enormously from this cross-disciplinary early contact. And it's through Feinberg that I first learned a little bit about how statisticians approach data and the sea change that would be needed to make this new approach accessible to even very trained statisticians. So Steve died in December of 2016 and Joyce was one of 11 people murdered in October of 2018 at the Tree of Life synagogue massacre in Pittsburgh. And I miss them both very much. Now there's this discussion of increased use of restricted access data centers for viewing census data. And this question starting a couple of years ago led to what in formulae is called the Feinberg problem. So the Feinberg problem is basically, Steve would say, I need to look at the data. And I trusted Steve. We all trusted Steve. And he knew what he was doing. And he was smart and he was well-intentioned. And so the question is, could we allow him to look at raw data and then think, you know, do whatever he normally does, but when he decides that he has found a statistic that he wants to make public, we would publish that statistic, but we would redo the computation in a differentially private way for that statistic. So we'd like to be able to do this. And it turns out to be difficult. And the reason immediately is that the choice of which statistic you're going to publish may itself be disclosive. I may, you know, Steve may only choose to publish a particular statistic because he happened to see Bill Gates' data in the data set and that made him think of something or other and he decided that would be an interesting statistic. So the choice of which statistic to publish is, could be sensitive. And the way to think about it is sort of, you have to get the right level of abstraction. Estimates are just functions that we don't understand that interact with data and make choices about what to publish. So we need a way of making this differentially private. And astonishingly, there are some, like, toy ways of going about it, but there's a lot of work to be done on that problem. Now in addition to publishing estimates and tables, the Census Bureau also publishes something called public use micro data. And you can think of these as little synthetic data records, except, sorry, they're not synthetic there. They've taken real data records and they've pulled out some identifying information and they've carried out something called swapping, which means that occasionally they take a family in this geographic region and one over here and they literally swap their data. And the point of swapping is to introduce uncertainty about whether what you're seeing is really a person who lives down the street from you or is in fact the data of someone swapped in from Michigan. So can we do privacy preserving micro data? And the answer is, well, maybe, but again, the fundamental law applies and in fact there are hardness results. So in the interest of time, I'm going to skip this slide, which gives you some intuition about hardness results, because I would like to end on a positive note, which is an interesting, wonderful recent piece of work. So I mentioned the opportunity at last before. And I'm going to describe now as a result from a paper by Raj Chetty and John Friedman, a practical method to reduce privacy loss when disclosing statistics based on small samples. Quoting from their paper, actually I won't. So what they do is building on techniques from differential privacy. They suggest a method to reduce privacy loss for certain kinds of statistics, such as ordinary least squares, regression elements, estimates based on small samples. And there is a technicality that makes their technique not differentially private, but first of all, our intuition says that this shouldn't be very risky, and as I'll tell you in a moment, it also led to improvements or strengthenings that are in fact differentially private. So this is a graph of low income black women. On the x-axis is in their census tract what percentage of the homes are single parent homes. And on the y-axis is the teen birth rate. So it's the teen birth rate for low income black women. And this is a picture of what was obtained with noise infused data, and the conclusions that they reach are the same as they would have reached. I mean, they were able to check without the noise. So what they're showing here is in this image, you can see there's a clear positive relationship between the two variables in ordinary least squares regression. So in other words, the context matters, and if there are very few single family homes, then these poor black women do not have teenage mothers. But if there is a large percentage of single family homes, then they are more likely. And you get this nice, or nice, I don't know, you get this clear linear relationship. Now this involves looking at census tracts. And a commonly used technique previously before differential privacy is called cell suppression. When you have counts that are very small, say less than five, you simply don't report the results for this cell. Although often the results, if the count is zero, they will report because that's not viewed as being disclosive. So this is what happens when you have cell suppression. So what's going on here is that it's completely obscuring the linear relationship. And this actually happens for two reasons. By omitting the cells that have few teenage births, you're omitting tracts with low but nonzero teenage births. These are the tracts that happen to have few single parents. And so those data are simply being written out of the story, and the results are biased accordingly. The second effect that's going on is that black women who grew up in tracts with smaller black populations have fewer teenage births, and these in turn are more likely to be suppressed. So not only are you not getting the story, but you're getting a really biased story. It didn't say, hey, we fail. It said, here's what's going on, and it's actually the wrong story. And this kind of distortion contributes to the myth of hypersexualization among African-American women. So finally, I mentioned that spurred by this work, and in conversations with Chetty and Friedman, a lobby McMillan, Serati, Smith, and Vodan have been looking at new algorithms that are differentially private for ordinary least squares for this particular setting with very small samples. And roughly speaking, the green in the picture is what Chetty and Friedman were getting, and the orange in the picture is the better algorithm, and the blue in the picture is the not so good differentially private algorithm. But we can see that the orange is approaching the green, which is all I have time to say. Thank you very much for your attention.
 Today's topic is going to be differential privacy and the US census.  And it's an extremely timely topic, and I'm not very ambitious in terms of the talk, but  differential privacy will be the confidentiality protection mechanism for the 2020 US decennial  census.  So for the first time, privacy will be protected by a formal method.  And pods and sigmod have played a very interesting role, an important role in the history of  this field, so I wanted to highlight that.  And at the very least, what I hope is that when you leave this talk, you are able to  explain to other people what differential privacy is.  And later in the talk, you'll see why I think that's so important.  Okay, so in a nutshell, there are really two kinds of data analysis, a statistical data  analysis.  So one kind is to try to statistically understand the population as a whole.  So for example, this is exactly what we do with census data.  It's what we do with financial data.  This is the brainchild of Elizabeth Warren, the Consumer Financial Protection Bureau.  And one of the goals of the Consumer Financial Protection Bureau is to examine loan data,  housing loan data in particular, for evidence of discrimination because of historical discrimination  in loans in the United States.  Another thing that you might be doing is analyzing cell information, images, learning to, you  know, training a classifier to distinguish cancerous from non-cancerous cells, working  on the data of individuals.  And so the idea in all of this is to somehow extract some general or statistical knowledge  while protecting the privacy of the individuals who are in the data set.  The other kind of data analysis is when you're looking for a needle in a haystack.  So this would have been the case, for example, with the so-called Total Information Awareness  System, which was processing huge troves of data looking for terrorists.  So if you want to do privacy-preserving data analysis, differential privacy is something  that's appropriate to this first task, where you're trying to learn statistical trends  of the population as a whole, and it's not relevant to the needle in the haystack task.  And in fact, if what you're trying to do is find the needle in the haystack and you want  to somehow preserve privacy for the non-needles, so to speak, you need a different solution.  Differential privacy won't do it for you.  So it's the wrong tool for that.  Now, statistics in general feel private.  That is, so a statistic is a quantity that's computed from a sample, and it's supposed  to tell us about the population as a whole.  So everybody's intuition is that the statistic somehow is not talking about the individuals  within the sample, but is about a bigger thing.  And for example, two data sets that are collected independently, but using the correct sampling  technology from the same population should tell us essentially the same things about  the population.  And our sense of the privacy of a statistic is, I think, derived from this fact, that  there's a kind of intuition of, gee, nobody knows that I was in the sample.  I could claim that I opted out, or I could claim that nobody asked me to be in the sample.  And it's not about me, it's about the population as a whole, and the proof of it somehow is  that, well, if someone had collected a different data set that didn't happen to contain me,  the same things would have been learned.  So this intuition is good, and it's on the right track, but it's not quite enough to  give us privacy.  And the role of differential privacy is to kind of help this intuition along and make  an honest intuition out of it.  So statistics, differential privacy is supposed to give us this kind of statistical out opt-in  intuition for all computations, including total population counts.  And that's what a census is.  So here's how we're going to abstract the problem.  We're going to have here, I have an analyst, data analyst on the right, and I have a database  on the left, or a data set.  And the data set contains a lot of very, very useful but potentially sensitive information.  In our abstraction, our analyst will interact with the data set by posing queries and getting  responses.  So a query could be something very simple, like how many people in the data set are over  six feet tall, or a query could be something much more complex.  Give me the following set of marginals, or carry out at least squares regression, or  do the following study of the data.  And then we get an answer.  And based on that answer, so adaptively based on that answer, the analyst can ask a new  question.  And our privacy is going to be against the analyst.  So we want to keep the analyst from somehow violating the privacy of the members of the  database.  But we have to give some information to the analyst, because that's the whole point.  The abstraction is general enough to capture the fact that you might have different people  asking questions of the same data set, and they might or might not be conferring, first  of all, in their choice of questions, and secondly, in their desires to compromise the  privacy of the individuals in the data set.  And it's also general enough to capture the fact that researchers carry out studies.  They look at some data, they publish some results, and then new studies are created  based on the findings of the old studies, follow-up questions, or the first study might  suggest some other new areas of inquiry.  And people may go back, possibly, to the same data set or an overlapping data set and ask  questions.  So it's a very, very general formulation.  Now the problem of privacy-preserving data analysis dates back at least to 1965 randomized  response of Warner.  And so it is an old problem, and when I began this work, I was working with my then intern,  Adam Smith, and our driving scenario was that of the US Census Bureau.  Our idea was that, first of all, the motivation should be fairly clean here.  It's an analysis of the people's data to allocate the resources of the people, hopefully for  the benefit of the people, and there is a legal mandate for privacy.  So there's a law about privacy of the responses in the Census.  So there was real motivation, we felt, on the part of the curators of the data to ensure  privacy.  We'll talk more about the Census, of course, later.  So here's an example, flossing.  Flossing will be our favorite.  Going back to the intuition about statistics being private, I said that this intuition  needs some help, and here's the problem.  Suppose we have exact answers to the following two questions.  How many living physics Nobel laureates floss regularly, and how many male living physics  Nobel laureates floss regularly?  If we had exact answers to both of those questions, then we would know whether or not Donna Strickland  flosses regularly, and this would be a compromise of her privacy.  So even though both of these could be very large sets, it's their intersection or their  set difference being so small that is causing us a problem.  This differencing attack is just one example of how seemingly innocuous questions, possibly  posed over very large sets of data, can be combined to compromise privacy.  And more generally, we have the fundamental law of information recovery, which says that  intuitively if you have overly accurate estimates of too many statistics, then this is completely  non-private.  You can totally break privacy.  So this was a seminal result of D'Norah Nisim, and many variants of this basic theorem have  been proven.  The definition of overly accurate will change according to the number of queries.  So if you're going to have a very large number of queries, then to prevent total loss of  privacy, you need to have a lot of noise in the answers.  But if you have fewer queries, you can get by with smaller noise.  And this result applies equally to interactive and non-interactive systems.  So I gave you a picture before where I was clearly indicating interaction, question one  answer, one question, two answer, two.  But I said that those questions could be pretty broad, like give me the following collection  of marginals.  So the same is true here.  The question might be, give me a table that lets me reconstruct the answers to the following  very large set of queries.  So early on when we were doing this work, I got a call from a medical researcher who  said exactly, can't you just give me a noisy table that will let me get answers to all  of the questions I want to ask as I figure out what they are?  And the answer is no.  If I gave you something that would in fact let you accurately answer or relatively overly  accurately answer too many of those questions that you're choosing on the fly, then it would  be a violation of the fundamental law of information recovery.  So even if I hand you a blob that you can compute on and get relatively accurate answers  from, the same problem would show up.  So what's the definition of differential privacy and how did we get there?  This is a picture of Cecilia Helena Payne Gapushchin, 1900 to 1979.  She was among the first women to obtain a PhD in astronomy and she ascertained the temperatures  of different classes of stars and estimated the great abundance of hydrogen in them, much  more than there is in Earth.  And so her dissertation work disputed the incorrect belief at the time that the Earth  and the stars had the same composition.  So here she is, Payne is in this database.  What kind of privacy should we guarantee for her?  What does it mean to say that we are protecting her privacy against a data analyst?  So the first thing that we would try is a definition that says that the analyst can't  learn anything about Payne that she didn't already know about Payne.  Nothing new.  And this is a definition that's very evocative of semantic security for a crypto system and  it is also the disideratum that the statistician, Tordelinius, articulated for what he called  the statistical database in 1977.  So the problem with this definition is if that's your goal, then what's the point?  So for example, suppose that I'm from Mars and I believe that all humans have two left  feet.  And in particular, I think that Payne has two left feet.  I carry out a statistical analysis of the dataset and I learned that the vast majority  of humans have one left foot and one right foot.  So now my beliefs about Payne have changed and I think that she has one left foot and  one right foot.  I have learned something new about her, something I didn't know before.  Have I violated her privacy?  So that's a definitional question.  You get to make a decision about that and your definition, your intuition may say, yes,  this is a privacy violation, but it was not our intuition.  We said this is not a privacy violation and the reason it's not a violation is that the  same things would have been learned about Payne even if she had it opted out or even  if she had been replaced in the dataset with another random member of the population.  So this is Henrietta Swan Leavitt, another physicist who was the first to know the relation  between certain variable stars' brightnesses and the period over which that brightness  varied.  And that, her observations gave rise to a law which proved a valuable means for estimating  distances in space.  Okay.  So we're going to be learning, if we would be learning the same things, independent of  whether any individual opts in or opts out of the dataset, our intuition is that it's  not a privacy violation for these people.  So that's led to the English language definition of differential privacy, that the outcome  of any analysis should be essentially equally likely independent of whether any individual  opts in or opts out of the dataset.  So even an analyst who knows the whole rest of the database and who thinks there are two  possible worlds, it's this database all by itself, that's the bottom picture, or it's  this database plus the data of Payne, that's the other database.  Even such an analyst shouldn't be able to determine which of the two databases is actually  the case.  Okay.  So an adversary, again, knowing both datasets in their entirety should never be able to  distinguish which of the two cases is the reality.  And so you have to ask, what's the source of uncertainty when I say that the outcome  of an analysis is essentially equally likely?  What is that likelihood over?  So our algorithms are going to flip coins.  Our guarantee is going to be worst case for all pairs of databases that differ in the  data of just one person.  And the probability spaces will always be coin flips of the algorithm.  And that's good because we are the algorithm designers, we're the good guys, we can make  sure that the algorithm flips its coins.  So if you're not used to thinking about similar probability distributions, or if you're ever  going to be explaining this definition to somebody else, the following metaphor might  be useful.  Think about a fair coin versus a very slightly biased coin.  So your fair coin has probability a half, or specifically, let's say, 500 out of 1,000  of coming up heads.  And our slightly biased coin will have probability, say, 501 over 1,000 of coming up heads.  So think about the coin now as playing the role of the database.  And we have an algorithm which is going to flip a coin and tell you whether it's heads  or tails.  So given one of these coins, the flipping algorithm will now produce either heads or tails.  And the probability distribution on the outcomes is, as you can see plainly, nearly the same  for the two coins.  The probability of heads in one is 500 over 1,000 and in the other is 501 over 1,000.  So they're nearly the same.  And given one or even several coin flips of the same coin.  An adversary can never actually determine which of the coins is the true one with any  degree of certainty.  Now, it's a very strong definition of privacy, almost the same output distributions independent  of the participation of any individual.  Why does it allow us to do any kind of data analysis at all?  So some of you know something about machine learning and you know that stability, that  is the stability of the output of the algorithm to small changes in the data set is actually  essential for the ability to generalize from your data set to the population from which  the data set is drawn.  So stability preserves privacy, but it also prevents overfitting.  And so that's just a little bit of an intuition as to why, even though we think of sort of  adding noise or randomness as interfering with utility and putting privacy into conflict  with utility, it actually is helping learning.  Privacy and generalization turn out to be aligned.  So here's the formal definition now of differential privacy.  Our algorithms are called M for mechanism.  And we need the concept of adjacent data sets.  And those are pairs of data sets exactly as we've been discussing.  These are data sets that are almost identical, but one data set contains the data of just  one more person.  Oops, I want to go back to this definition.  One more person.  Now you have an algorithm, the algorithm maps databases to some output space, and so we  can look at output events called, say, S. And the definition of differential privacy,  and this is due to joint work with McSherry, Nisseman Smith, says that the probability  that we observe this event, any event, S, when the algorithm is running on database X, is  at most e to the epsilon times the probability that we see S when we're running on database  Y. So what is this epsilon?  In differential privacy, privacy is not binary, but rather there is a measure of privacy loss,  which is called typically epsilon.  And this is controlling the ratio of the probabilities of observing S on adjacent data sets X and  Y. Those are data sets that differ in the data of just one person.  And the probability spaces here are over the coins of the algorithm, our mechanism M.  So if you're not so comfortable with e to the epsilon, when epsilon is small, this is  approximately one plus epsilon.  So this is a statement, differential privacy is a statement about the behavior of the algorithm  M. It has absolutely nothing to do with who knows what.  I don't know why this is advancing.  It has nothing to do with who knows what now or in the future.  So if you see an output, it's like seeing a head or tail from that coin flipping algorithm.  No matter what other information you get, other than telling you which of the two databases  it is, which of the two coins it is, you won't be able to determine which of the databases  it is.  And the intuition, of course, is that if you can't even tell whether or not I'm in  the data set, you certainly can't be learning details about me that are specific to me and  aren't just general statements about the population as a whole.  So this says you can learn about pain, but you can only learn things that you could have  learned without her participation.  And as I said, we call this a bounded ratio condition.  I've just rewritten the inequality.  And notice that the roles of X and Y are completely symmetric in this definition.  We said that X and Y are adjacent, meaning one of them is larger than the other and the  larger one contains the data of just one more person.  But the inequality holds whether the larger one is X or the larger one is Y.  So going back to the needle in the haystack, I said that differential privacy is the wrong  tool for privately finding the needle in the haystack.  And the reason is that differential privacy protects the outliers.  It protects every individual.  And indeed, this was intentional.  Our feeling was that the outliers needed protection perhaps more than everybody else.  So if you think of X as the haystack and Y as the haystack without the needle, what  you're going to observe in outputs from a differentially private algorithm will be essentially  the same, independent even of the presence of the needle.  So it certainly isn't going to help you to find the needle.  So here are some key properties of differential privacy that follow immediately from the definition.  First it's resilient to present and future information from other sources.  It also composes gracefully and automatically.  That is, we understand the cumulative privacy loss over multiple computations on the same  or on intersecting data sets.  In the very worst case, the losses add up.  More advanced analyses involve understanding that the privacy loss is in fact a random  variable.  And nicely, sometimes it's positive, but sometimes it's negative.  So that we do get cancellation effects and there are concentration results.  That's beyond the scope of today's talk.  As we understand how privacy loss accumulates over multiple computations, differential privacy  becomes programmable.  That is, you can define small, differentially private primitives and then combine them to  carry out in a differentially private way more complex statistical analyses.  And you can control by setting the epsilon parameters accordingly, you can control the  cumulative loss.  And this is what makes it so strong.  There is, to my knowledge, no other method that permits this.  So composition is the sine qua non of differential privacy.  So here's one technique just to give you a flavor.  There are many techniques for achieving differential privacy and many little computational primitives  that you might have.  Here is one extremely useful computational primitive.  So suppose what you are interested in is computing some function F on your data set.  A key quantity for us is going to be how much the value of any single individual can swing,  how much the data of any single individual can swing the value of the function F. So  we look at the maximum over all adjacent data sets.  Those are data sets differing in the data of just one person of F of X minus F of Y.  And we take that absolute value, that's our sensitivity or delta one.  And the theorem is the following.  So this is the Laplace noise distribution.  And it takes a parameter and you can see a bunch of different values of the parameter.  Probably you can't read the font.  But the idea is when the parameter is larger, the data, the spread is fatter, the curve is  fatter.  And I've centered it at zero.  So what does the theorem say?  It says that if you want to release the value of F on your data set in a differentially  private way, it suffices to first compute F on your data set, that's F of X, and then  add Laplace noise that's drawn with parameter, the sensitivity divided by epsilon.  So let's just talk about that parameter for a moment.  Intuitively, if the data of one person can really swing the value of the function F,  then you want a fat curve.  And indeed delta one is sitting up there in the numerator, so a bigger sensitivity gives  you a fatter curve.  If you want very good privacy, then again, you want a fat curve.  You don't want a curve that's really peaked right over F of X.  And so really good privacy corresponds to really small epsilon.  And here is epsilon in the denominator, so small epsilon again blows up our parameter  B. So things are in their right place.  And in fact, we'll see in a moment why this works.  But here's the first observation.  We tended to think about epsilon as a constant.  So for thinking about epsilon as a constant, a draw from this distribution is, sorry, so  think about a counting query.  How many people in the data space are over six feet tall?  The sensitivity of this counting query is one, because the addition or deletion of any  one person can change the count of the number of people who are over six feet tall by just  one.  And for any counting query, the sensitivity is one.  And so if epsilon is a constant, what we're adding here is noise that we expect will have  magnitude one over epsilon or a constant.  So the noise is roughly one for a single counting query.  Now, I promised a quick proof of this.  So the proof is simple, and it relies on the fact that the probability density function  for the Laplace noise distribution, when the parameter is some value B, will drop off exponentially,  so P of t will drop off exponentially in the magnitude of t divided by B.  So for any t, the ratio of the probabilities that we will see the outcome t when, or the  density at t, when the database is x and when the database is y, is given by this expression  on the left.  And just using the triangle inequality, that gives us e to the magnitude f of x minus f  of y divided by the parameter B.  That magnitude is by definition bounded by the sensitivity delta one, and the parameter  B is delta one over epsilon, and so we get this bound of e to the epsilon.  Now suppose we want to look at a number of different queries or some k-ary function.  You can think of k different queries as a k-ary function, but it could also just be  something else in high dimensional space.  Then the same theorem and the same proof works, but for a slightly different definition  of sensitivity.  Instead of the absolute value of f of x minus f of y, it's the L1 norm now, which is the  sum of the absolute values of the individual coefficients.  But the same theorem holds, and what we're doing now is we're drawing fresh random noise  scaled to this new sensitivity for each of the k different components of the output.  So in particular, what that would say would be that for k counting queries, you would  need noise that scales to k.  I mentioned work that involves looking at privacy loss as a random variable and using  cancellation, and with that you can get a relaxed notion of differential privacy where  this value turns into something it's closer to square root of k.  So now though something really interesting happened.  In particular, think about a histogram query.  So in a histogram query, you have your space of individuals and you carve it up into some  arbitrary number of cells of arbitrary shape, and you want to know how many individuals  are in each of the different cells.  But a histogram query has sensitivity 1.  That is, adding or deleting a single person can change the count in only one cell and  can change that count by only one.  And so the sensitivity of a histogram query is actually, again, just one.  Even though it might be a large, large number of cells, you only now have to add noise scale  to 1 over epsilon rather than k over epsilon to each of these cells.  All right.  So three notes from the history of pods in SIGMOD.  So this fundamental law of information reconstruction, the seminal work in this area, was published  here in 2003 at pods.  And then it won the test of time award.  And section three of that paper says that it's not a heavily looked at section.  It says that you can get meaningful privacy analysis for almost n squared queries.  And so the power of the reconstruction theorem is it says, look, we don't know what you mean  by privacy.  But we're going to show you something bad that can happen.  And you're going to agree that whatever you thought of privacy as, this bad thing violates  that.  So that was really powerful.  But there wasn't yet a real definition of privacy.  And in fact, when Colby came to visit me at Microsoft, and I had been thinking about privacy  for the hotmail user database, which at the time had like 500 million users.  And he was showing me some attack.  And the attack took n squared queries.  And I was thinking, you know, n is 500 million n squared, not so likely.  And I said, well, what happens if we cut off the questions after a little while?  I mean, you don't like sneak off and secretly ask 500 million queries, let alone that number  squared.  And we worked on this, and we were able to repurpose an argument that Colby and Erit had  for some other thing, and show that we got some kind of meaningful notion of privacy.  So but as I said, we didn't yet have the definition of differential privacy.  And two years later, also here at PODS, there was another paper, this was with Blum, McSherry,  and Niseem.  And there what we said was, okay, we understand how to, with this sort of clumsy definition  of privacy, how to ask privacy preserving counting queries, let's look at that as a  computational primitive and see what we can do with it.  And then we showed that you could carry out a lot of common data mining tasks, like a  version of the perceptron algorithm and singular value decomposition and K-means computations,  and in fact, anything learnable in the statistical queries learning model in a differentially  private way.  And this sort of algorithmic beginning, I think, was key.  So PODS played a really key role in this history.  And it's, there were other publications about differential privacy and other interesting  work on privacy in general here, but I'm just mentioning three.  In 2009, Frank McSherry in SIGMOD published a paper on what he called pink or privacy  integrated queries.  And this is a general programming platform to facilitate programming with differential  privacy, including monitoring of the privacy loss budget, how much privacy loss has been  happening.  And I wanted to particularly mention that because it's winning the SIGMOD Test of Time  award this year, so congratulations to Frank.  Now, there are lots of algorithms for many different tasks, and there are also relaxed  studies of lots of different things that are related to differential privacy, and in fact,  the fields has kind of come to encompass all of these.  Relaxations for privacy loss that I mentioned before.  Things like studies of lower bounds on sample complexity, lower bounds on computational  complexity, economics perspectives.  This is all like from the outside, right, this is all work done in DP.  There are applications of differential privacy also to other fields.  So there are results that came in geometry from insights derived from differential privacy,  also in economics, in online learning, and most recently in a paper by Scott Aronson  and Guy Rothblum in gentle measurements in quantum.  So there's something I think very fundamental to computing with a little bit of noise that  seems to be helping in lots of different directions.  Just want to mention before getting onto the discussion of the census, one surprising  application of differential privacy, and that is that it neutralizes the risks to validity  that are caused by adaptivity.  So choosing your next question based on the answer to the previous questions.  So this is a very, this is a risk always in data exploration where you sort of trawl around  in the data looking for stuff, and so it's going to eliminate the sources of p-hacking  and overfitting that come from adaptivity.  And I only have time to give a little bit of an intuition, but here's the intuition.  So fix a query queue, any query that you want to know something about for your population.  And then go off and recruit a database X, and you're going to now evaluate this query  on your database and try to learn something about your population as a result.  So of course, with high probability, the database that you go out and recruit will be somehow  representative of the population with respect to Q.  This is why statistics works.  This just, that's how it works.  You have this thing you want to study, you go and you get a sample of the population  and you study it on the population, and you expect that it's telling you about the population  as a whole.  That's why it works.  So if I think now of p-hacking and overfitting as kind of an adversarial attempt to find  a query for which the dataset is not representative, differential privacy is going to protect.  So we have this initial intuition, or this initial fact.  Now you could reverse the order of the steps if you're careful.  So first recruit a database using proper sampling technology.  Now without looking at the database, choose your query.  Well of course the query is still independent of the database, so you're in the same situation  that you were in before and you're really unlikely to choose a query for which your  database is not representative of the population as a whole.  Just as, because you've done something completely equivalent to what happened in the previous  case.  So now suppose during the course of interacting with your dataset, the analyst can find a  query for which the dataset is not representative.  Then intuitively she must have learned a lot about the database because we just saw that  when she didn't know anything about the database, she was really unlikely to come up with such  a query.  And so differential privacy prevents the analyst from learning enough about the dataset to  find a query on which the dataset is not representative.  So differential privacy today, it's being used a lot in industry.  In Apple, Google, Microsoft and Uber, for example, a lot of this work is done in what's  called the local model.  Meaning that in the pictures I've been showing you, there's a dataset that's been collected  or curated and the analyst interacts with the dataset.  In many of the industrial applications, raw data aren't being gathered from the clients,  but rather privacy is being rolled in at the client level and this privacy preserving version  of the data is being sent up to the server.  And in industry parlance, this is called moving the trust boundary out to the client.  So certainly Apple and Google and Microsoft are doing things in that model.  Now Facebook has recently announced a secure and private artificial intelligence scholarship  aimed to equip students with privacy preserving technologies such as federated learning, differential  privacy and encrypted computation.  And a high up person at LinkedIn tells me that LinkedIn is investing heavily in differential  privacy and is, by the way, almost all of these companies are recruiting in this area,  so center students for jobs could be very, very exciting time.  The oldest deployment of differential privacy, large scale deployment is within a Census  Bureau product called On the Map, which is a website that allows the public to learn  where people work and where workers live.  And recently there's been new work based on census data in the Opportunity Atlas, mapping  the childhood roots of social mobility.  So this is work by the economist Raj Chetty and colleagues that have deployed something  very close to differential privacy in constructing this Opportunity Atlas.  And I will say more about this later on in the talk.  Now every decade the U.S. government carries out a complete enumeration of people living  in the United States.  The enumerated population in each state serves as the basis for apportionment of the 435  representatives in the House of Representatives.  And in addition, this enumeration is, decides where hundreds of billions of dollars in federal  financing is allocated.  It also is, this information is also used for enforcing the Voting Rights Act and in  redistricting.  Okay, in the 2010 census, completely typically, 7.7 billion statistics were released from  the data that were collected by census.  And there are about some 300,000 individuals.  And in light of these reconstruction attacks that I've been talking about, John Aboud,  who is the Chief Scientist and Associate Director of Research and Methodology at the Bureau,  decided that census should check to see what was the nature of the privacy protection,  which is mandated by law, what was the nature of the privacy protection against these sorts  of reconstruction attacks.  And he looked at the 2010 data.  So he knows what was released to the public, and he also knows what was collected because  he's at the census.  And his conclusion was, as you can see, that technical advances revealed a new vulnerability,  allowing people to reconstruct data from tables that were previously assumed to be privacy  preserving.  And this is a slide from a talk that John Aboud gave in February of this year.  He talked a little bit about his attack.  And so these are his slides.  And essentially, what they did was, first of all, they took all of the released information,  and from that, they sort of reconstructed a whole bunch of putative individuals, of everybody  in the data set.  So that means that they wrote down a collection of attributes.  This is without names, but a collection of attributes for each of the individuals, supposedly,  in the census.  And then they linked these putative people to commercially available data sets that contained  names.  So what do I mean by linking?  I mean, you have basically the, you have a bunch of attributes in your putative reconstructions,  and in the public data set, you have some of these attributes and the names, and you  match them up, and now you have names for the people in your data set.  So they did a lot of linking.  And they weren't able to link everybody, but they were able to link many.  And when they did this, they got hold of now the names for these putative people where  they thought they had success.  And then they were able to look at the census data to see did they get the names correct,  and moreover, did they reconstruct the attributes correctly for those people?  And what they found was that they had perfectly reconstructed 17% of the population.  That's 52 million people.  And the specific things that they were able to reconstruct for these people, the harms  that they envisioned, is that an attacker carrying out the same reconstruction would  be able to learn people's self-response for race and ethnicity.  Now, yeah, okay.  You'll see in a little bit, I'll show you the census form.  It doesn't have much more than that.  But there's another census form which is not part of the decennial census, which is much  more rich, and the privacy harms could be more dramatic.  For example, you could learn if somebody was adopted or not.  Okay.  So Abeld says, we fixed this for the 2020 census by implementing differential privacy.  So what do you think the response was on the part of people who work with census data?  Were they thrilled that they were now sort of going to be morally in the clear because  there was no privacy compromise?  Well, no.  And in fact, this is greeted with a lot of concern and anxiety.  So first of all, there were simply people who say, well, the old protections worked  well and the law doesn't care what you learn about people.  It only cares whether or not you can match a record to a name.  If the law doesn't care what you can learn about people, then I don't understand the  point of the law.  And in fact, this is a very interesting question, but okay.  And then there was a lot of concern about utility in general.  So what happens when you ask questions and require a certain amount of accuracy and you  sort of use up the privacy budget?  You can't go any further because the fundamental law is about to kick in.  Huge amounts of money have been spent gathering data for the census.  It's the largest peacetime mobilization.  And also for other surveys by federal statistical agencies, just billions of dollars are spent  gathering these information.  What happens when we can't use them anymore?  All right.  So these are real concerns, and I don't, as a computer scientist, I don't have answers  to these questions, but it's important to sort of think again about the context.  People share their data because they are assured of confidentiality.  That really is drawn into stark relief when you think about what's been happening in the  United States and the push, for example, to include a citizenship question, which at least  temporarily has been pushed back, but we don't know whether that's going to stay.  The Supreme Court said we don't like your justification, but you can try to come up with  a justification that we do like.  Okay.  So assuming, though, that we're going forward with differential privacy, let's talk about  some of the specific challenges.  So one of them I have already alluded to.  It's the allocation of the privacy resource.  So in some sense, we have a privacy budget, which is a cap on the cumulative privacy loss  that we think we ought to be tolerating.  So first of all, how do you choose this privacy cap?  How do you choose this budget?  And who should choose this budget?  The question makes sense for census, but it also makes sense for the various industrial  uses.  And once you have chosen a budget, there's a finiteness to everything.  And census has to figure out among the questions that it is going to answer or among the statistics  and tables that it's going to release, which ones should be given priority?  Which ones should be given the best accuracy and get to use up more of the privacy budget?  And which ones have to have less good accuracy and use up less of the budget?  And this is not the kind of question that census has had to confront in the past.  So they're trying very hard to find out from their users, what do you need?  What are the queries that you need to be able to answer?  Now this question about how and when to allocate, I mean, how to allocate the budget, this is  one where perhaps economists have something to say.  And in fact, John A. Bowden and Ian Schmouta have a paper about exactly this question.  And they say that, and I'm quoting now, economists recognize this is a problem of resource allocation.  We propose an economic framework for solving it.  Statistical agencies must allocate information in their collected data between two competing  uses, production of statistics that are sufficiently accurate, balanced against the protection  of privacy for those in the data.  We combine the economic theory of public goods with cryptographic methods from computer  science to show that social welfare maximization can and should guide how statistical agencies  manage this tradeoff.  And the paper is very, very interesting.  Okay.  What's another problem?  Another problem is that the people who work from the census data and the released statistics,  so historians, sociologists, demographers, economists, are simply not trained to interact  with the data in a differentially private way.  They're not trained to ask queries and get responses.  If you take a class in statistics, the first thing that you're told is, look at the data.  Well, you can't look at the data in our methodology.  You can't see raw data.  You have to ask queries and get differentially private responses.  Now, you might say, if you have a database of 300 million people, what does it mean to  look at the data anyway?  Aren't you, in fact, always looking at some statistic of the data or some illustration  of the data of some sort and can't these things be done in a differentially private  way?  Maybe often the answer is yes, but still, the people who work with the data are not  accustomed to this.  And in no way do I want to minimize the difficulties here.  This is a sea change in the way people have to operate.  Another thing is that they have to be trained to deal with noise.  Social privacy intentionally adds noise at various points in the computations.  People are used to thinking of things that the Census Bureau releases as actually being  noise free.  It's not true.  They've always been adding noise in one way or another.  They've always been doing something in order to protect privacy.  It just hasn't been enough, and that was what the results of the 2010 attack showed us.  But everybody is used to thinking of everything that's released as being ground truth.  Here you have to learn to adjust for the noise.  The nice thing about differential privacy is the methods are completely public, and  a trained analyst can, in fact, adjust for the noise.  And this is different from how things were in the past, but you have to learn to do it.  Now the Census Bureau goes to a lot of effort in their work to kind of make some of the  artifacts of differential privacy invisible to the user.  So for example, in differential privacy we add noise, and we might be looking at a count,  and the count that's released might be negative, or it might not be an integer.  And these are fine.  We understand how to interpret a negative count.  It means that the true count is very small, and the noise pushed it negative.  Okay, fine, not a problem.  We know that there aren't really a negative number of people, and similarly with nonintegrality.  But when I say they go through a lot of noise, I mean they're solving integer programming  problems in order to produce nice, integral things.  Some day, perhaps, people can learn to deal with non-integer negative things or inconsistent  counts because you've added noise differently in different places.  And again, if you understand what's going on, you can cope with this, but that requires  a high degree of sophistication.  And we're definitely not there yet.  And finally, a lot of research remains on a purely technical level.  So we know how to do a lot of things very well using differential privacy, and there  are a lot of things we might want to do that we don't yet know how to do well.  The field is still relatively young.  There's essentially no work on differentially private data cleaning, or we need to do more  work in order to investigate things like tales of a distribution.  Social scientists will often tell you that all the interesting stuff happens in the outliers.  I have no answer there.  That's my needle in a haystack.  And I'm also not enough of a data analyst to know how I should interpret the statement.  But maybe some of you do.  Now, I've been talking about the decennial census.  So this is actually a picture of the entire 2010 decennial census form.  As the website said, 10 questions, 10 minutes.  So what are the things that are being asked?  Because I'm sure you can't see the font.  There's a householder who is supposed to fill out the form.  And in fact, information has to be given for every member of the household.  But so for each person, first of all, how many people are living in the home as of this  certain date?  How many other people often stay in the home?  Is the home in a house, is it an apartment, is it a mobile home?  Phone number, name, sex, and age of each person in the house.  And then questions about ethnicity and race.  So Hispanic or Latino origin, and there are a number of categories there, and race.  And there are several categories there.  And people can check all of the boxes that apply to them.  And then finally, there's a question about whether this person ever stays anywhere else.  So for example, in college or in a military barracks or in jail, for that matter.  So this is the easy case.  And why do I say this is the easy case?  Well, it turns out that there's 44 bits of information collected per person.  Not that much in these fields, not including the name, of course.  Every year, a random subsample of the US population also fills out another form.  So this is, I think, a 5% I'm not sure sample of the population.  Fills out another form called the American Community Survey.  And this is what used to be called the long form, but now this is done every year on a  rolling basis.  So here are the things that are covered in the community survey.  Building ancestry, journey to work, computer and internet use, disability, employment,  family and relationship to the householder, fertility, food stamps, grandparents as caregivers,  health insurance coverage, Hispanic origin, home heating fuel, housing costs for owners,  industry occupation and class of worker, marital status and history, ownership, home value  and rent, place of birth and citizenship and year of entry, plumbing, kitchen and telephone  service, residence one year ago and migration, school enrollment, sex, vehicles available,  veteran status, the year built and the year moved in.  So you can see that this is an extremely rich collection of information about each person.  If things are difficult now with this form, what's going to happen with the ACS?  Okay.  So one thing that people talk about is a different mode of interaction with the database.  So an example is restricted access data centers.  This is a picture of Steve Feinberg pictured with his wife Joyce.  Steve was a renowned statistician and an expert in disclosure limitation among other fields.  And early conversations with Steve starting in 2004 or 2005 led to close ties between  members of several communities.  For example, this is how the differential privacy people were brought into contact with the labor  economist John Aboud who is now the chief scientist at the census.  And the field of differential privacy has benefited enormously from this cross-disciplinary  early contact.  And it's through Feinberg that I first learned a little bit about how statisticians approach  data and the sea change that would be needed to make this new approach accessible to even  very trained statisticians.  So Steve died in December of 2016 and Joyce was one of 11 people murdered in October of  2018 at the Tree of Life synagogue massacre in Pittsburgh.  And I miss them both very much.  Now there's this discussion of increased use of restricted access data centers for viewing  census data.  And this question starting a couple of years ago led to what in formulae is called the  Feinberg problem.  So the Feinberg problem is basically, Steve would say, I need to look at the data.  And I trusted Steve.  We all trusted Steve.  And he knew what he was doing.  And he was smart and he was well-intentioned.  And so the question is, could we allow him to look at raw data and then think, you know,  do whatever he normally does, but when he decides that he has found a statistic that  he wants to make public, we would publish that statistic, but we would redo the computation  in a differentially private way for that statistic.  So we'd like to be able to do this.  And it turns out to be difficult.  And the reason immediately is that the choice of which statistic you're going to publish  may itself be disclosive.  I may, you know, Steve may only choose to publish a particular statistic because he  happened to see Bill Gates' data in the data set and that made him think of something or  other and he decided that would be an interesting statistic.  So the choice of which statistic to publish is, could be sensitive.  And the way to think about it is sort of, you have to get the right level of abstraction.  Estimates are just functions that we don't understand that interact with data and make  choices about what to publish.  So we need a way of making this differentially private.  And astonishingly, there are some, like, toy ways of going about it, but there's a lot  of work to be done on that problem.  Now in addition to publishing estimates and tables, the Census Bureau also publishes something  called public use micro data.  And you can think of these as little synthetic data records, except, sorry, they're not  synthetic there.  They've taken real data records and they've pulled out some identifying information and  they've carried out something called swapping, which means that occasionally they take a  family in this geographic region and one over here and they literally swap their data.  And the point of swapping is to introduce uncertainty about whether what you're seeing  is really a person who lives down the street from you or is in fact the data of someone  swapped in from Michigan.  So can we do privacy preserving micro data?  And the answer is, well, maybe, but again, the fundamental law applies and in fact there  are hardness results.  So in the interest of time, I'm going to skip this slide, which gives you some intuition  about hardness results, because I would like to end on a positive note, which is an interesting,  wonderful recent piece of work.  So I mentioned the opportunity at last before.  And I'm going to describe now as a result from a paper by Raj Chetty and John Friedman,  a practical method to reduce privacy loss when disclosing statistics based on small  samples.  Quoting from their paper, actually I won't.  So what they do is building on techniques from differential privacy.  They suggest a method to reduce privacy loss for certain kinds of statistics, such as ordinary  least squares, regression elements, estimates based on small samples.  And there is a technicality that makes their technique not differentially private, but  first of all, our intuition says that this shouldn't be very risky, and as I'll tell  you in a moment, it also led to improvements or strengthenings that are in fact differentially  private.  So this is a graph of low income black women.  On the x-axis is in their census tract what percentage of the homes are single parent  homes.  And on the y-axis is the teen birth rate.  So it's the teen birth rate for low income black women.  And this is a picture of what was obtained with noise infused data, and the conclusions  that they reach are the same as they would have reached.  I mean, they were able to check without the noise.  So what they're showing here is in this image, you can see there's a clear positive relationship  between the two variables in ordinary least squares regression.  So in other words, the context matters, and if there are very few single family homes,  then these poor black women do not have teenage mothers.  But if there is a large percentage of single family homes, then they are more likely.  And you get this nice, or nice, I don't know, you get this clear linear relationship.  Now this involves looking at census tracts.  And a commonly used technique previously before differential privacy is called cell suppression.  When you have counts that are very small, say less than five, you simply don't report  the results for this cell.  Although often the results, if the count is zero, they will report because that's not  viewed as being disclosive.  So this is what happens when you have cell suppression.  So what's going on here is that it's completely obscuring the linear relationship.  And this actually happens for two reasons.  By omitting the cells that have few teenage births, you're omitting tracts with low but  nonzero teenage births.  These are the tracts that happen to have few single parents.  And so those data are simply being written out of the story, and the results are biased  accordingly.  The second effect that's going on is that black women who grew up in tracts with smaller  black populations have fewer teenage births, and these in turn are more likely to be suppressed.  So not only are you not getting the story, but you're getting a really biased story.  It didn't say, hey, we fail.  It said, here's what's going on, and it's actually the wrong story.  And this kind of distortion contributes to the myth of hypersexualization among African-American  women.  So finally, I mentioned that spurred by this work, and in conversations with Chetty and  Friedman, a lobby McMillan, Serati, Smith, and Vodan have been looking at new algorithms  that are differentially private for ordinary least squares for this particular setting  with very small samples.  And roughly speaking, the green in the picture is what Chetty and Friedman were getting, and  the orange in the picture is the better algorithm, and the blue in the picture is the not so good  differentially private algorithm.  But we can see that the orange is approaching the green, which is all I have time to say.  Thank you very much for your attention.
Cynthia_Dwork_0_143.png Cynthia_Dwork_144_2315.png Cynthia_Dwork_2316_5435.png Cynthia_Dwork_5436_6815.png Cynthia_Dwork_6816_7031.png Cynthia_Dwork_7032_11015.png Cynthia_Dwork_11016_11363.png Cynthia_Dwork_11364_15527.png Cynthia_Dwork_15528_15791.png Cynthia_Dwork_15792_16271.png Cynthia_Dwork_16272_16403.png Cynthia_Dwork_16404_18791.png Cynthia_Dwork_18792_19235.png Cynthia_Dwork_19236_20927.png Cynthia_Dwork_20928_21131.png Cynthia_Dwork_21132_21383.png Cynthia_Dwork_21384_21671.png Cynthia_Dwork_21672_21767.png Cynthia_Dwork_21768_24419.png Cynthia_Dwork_24420_24599.png Cynthia_Dwork_24600_24695.png Cynthia_Dwork_24696_25295.png Cynthia_Dwork_25296_27083.png Cynthia_Dwork_27084_27407.png Cynthia_Dwork_27408_32963.png Cynthia_Dwork_32964_33335.png Cynthia_Dwork_33336_52019.png Cynthia_Dwork_52020_52223.png Cynthia_Dwork_52224_52619.png Cynthia_Dwork_52620_52691.png Cynthia_Dwork_52692_53051.png Cynthia_Dwork_53052_55103.png Cynthia_Dwork_55104_55163.png Cynthia_Dwork_55164_55631.png Cynthia_Dwork_55632_58919.png Cynthia_Dwork_58920_59075.png Cynthia_Dwork_59076_59315.png Cynthia_Dwork_59316_59723.png Cynthia_Dwork_59724_61451.png Cynthia_Dwork_61452_61715.png Cynthia_Dwork_61716_61871.png Cynthia_Dwork_61872_62039.png Cynthia_Dwork_62040_62099.png Cynthia_Dwork_62100_62627.png Cynthia_Dwork_62628_62951.png Cynthia_Dwork_62952_63179.png Cynthia_Dwork_63180_63335.png Cynthia_Dwork_63336_65387.png Cynthia_Dwork_65388_65591.png Cynthia_Dwork_65592_65783.png Cynthia_Dwork_65784_66119.png Cynthia_Dwork_66120_66299.png Cynthia_Dwork_66300_66467.png Cynthia_Dwork_66468_66875.png Cynthia_Dwork_66876_70127.png Cynthia_Dwork_70128_70259.png Cynthia_Dwork_70260_72767.png Cynthia_Dwork_72768_73823.png Cynthia_Dwork_73824_73907.png Cynthia_Dwork_73908_74411.png Cynthia_Dwork_74412_74987.png Cynthia_Dwork_74988_75239.png Cynthia_Dwork_75240_75443.png Cynthia_Dwork_75444_75503.png Cynthia_Dwork_75504_75623.png Cynthia_Dwork_75624_79523.png Cynthia_Dwork_79524_80051.png Cynthia_Dwork_80052_80111.png Cynthia_Dwork_80112_80519.png Cynthia_Dwork_80520_80903.png Cynthia_Dwork_80904_84179.png Cynthia_Dwork_84180_84503.png Cynthia_Dwork_84504_84587.png Cynthia_Dwork_84588_84695.png Cynthia_Dwork_84696_84839.png Cynthia_Dwork_84840_86531.png Cynthia_Dwork_86532_87095.png Cynthia_Dwork_87096_88739.png Cynthia_Dwork_88740_88871.png Cynthia_Dwork_88872_93419.png Cynthia_Dwork_93420_93635.png Cynthia_Dwork_93636_93935.png Cynthia_Dwork_93936_93983.png Cynthia_Dwork_93984_94571.png Cynthia_Dwork_94572_94619.png Cynthia_Dwork_94620_94739.png Cynthia_Dwork_94740_94919.png Cynthia_Dwork_94920_95087.png Cynthia_Dwork_95088_96695.png Cynthia_Dwork_96696_97007.png Cynthia_Dwork_97008_97103.png Cynthia_Dwork_97104_98591.png Cynthia_Dwork_98592_99131.png Cynthia_Dwork_99132_99191.png Cynthia_Dwork_99192_102011.png Cynthia_Dwork_102012_102131.png Cynthia_Dwork_102132_102191.png Cynthia_Dwork_102192_103451.png Cynthia_Dwork_103452_103991.png Cynthia_Dwork_103992_104999.png Cynthia_Dwork_105000_105131.png Cynthia_Dwork_105132_105287.png
Today's topic is going to be differential privacy and the US census. And it's an extremely timely topic, and I'm not very ambitious in terms of the talk, but differential privacy will be the confidentiality protection mechanism for the 2020 US decennial census. So for the first time, privacy will be protected by a formal method. And pods and sigmod have played a very interesting role, an important role in the history of this field, so I wanted to highlight that. And at the very least, what I hope is that when you leave this talk, you are able to explain to other people what differential privacy is. And later in the talk, you'll see why I think that's so important. Okay, so in a nutshell, there are really two kinds of data analysis, a statistical data analysis. So one kind is to try to statistically understand the population as a whole. So for example, this is exactly what we do with census data. It's what we do with financial data. This is the brainchild of Elizabeth Warren, the Consumer Financial Protection Bureau. And one of the goals of the Consumer Financial Protection Bureau is to examine loan data, housing loan data in particular, for evidence of discrimination because of historical discrimination in loans in the United States. Another thing that you might be doing is analyzing cell information, images, learning to, you know, training a classifier to distinguish cancerous from non-cancerous cells, working on the data of individuals. And so the idea in all of this is to somehow extract some general or statistical knowledge while protecting the privacy of the individuals who are in the data set. The other kind of data analysis is when you're looking for a needle in a haystack. So this would have been the case, for example, with the so-called Total Information Awareness System, which was processing huge troves of data looking for terrorists. So if you want to do privacy-preserving data analysis, differential privacy is something that's appropriate to this first task, where you're trying to learn statistical trends of the population as a whole, and it's not relevant to the needle in the haystack task. And in fact, if what you're trying to do is find the needle in the haystack and you want to somehow preserve privacy for the non-needles, so to speak, you need a different solution. Differential privacy won't do it for you. So it's the wrong tool for that. Now, statistics in general feel private. That is, so a statistic is a quantity that's computed from a sample, and it's supposed to tell us about the population as a whole. So everybody's intuition is that the statistic somehow is not talking about the individuals within the sample, but is about a bigger thing. And for example, two data sets that are collected independently, but using the correct sampling technology from the same population should tell us essentially the same things about the population. And our sense of the privacy of a statistic is, I think, derived from this fact, that there's a kind of intuition of, gee, nobody knows that I was in the sample. I could claim that I opted out, or I could claim that nobody asked me to be in the sample. And it's not about me, it's about the population as a whole, and the proof of it somehow is that, well, if someone had collected a different data set that didn't happen to contain me, the same things would have been learned. So this intuition is good, and it's on the right track, but it's not quite enough to give us privacy. And the role of differential privacy is to kind of help this intuition along and make an honest intuition out of it. So statistics, differential privacy is supposed to give us this kind of statistical out opt-in intuition for all computations, including total population counts. And that's what a census is. So here's how we're going to abstract the problem. We're going to have here, I have an analyst, data analyst on the right, and I have a database on the left, or a data set. And the data set contains a lot of very, very useful but potentially sensitive information. In our abstraction, our analyst will interact with the data set by posing queries and getting responses. So a query could be something very simple, like how many people in the data set are over six feet tall, or a query could be something much more complex. Give me the following set of marginals, or carry out at least squares regression, or do the following study of the data. And then we get an answer. And based on that answer, so adaptively based on that answer, the analyst can ask a new question. And our privacy is going to be against the analyst. So we want to keep the analyst from somehow violating the privacy of the members of the database. But we have to give some information to the analyst, because that's the whole point. The abstraction is general enough to capture the fact that you might have different people asking questions of the same data set, and they might or might not be conferring, first of all, in their choice of questions, and secondly, in their desires to compromise the privacy of the individuals in the data set. And it's also general enough to capture the fact that researchers carry out studies. They look at some data, they publish some results, and then new studies are created based on the findings of the old studies, follow-up questions, or the first study might suggest some other new areas of inquiry. And people may go back, possibly, to the same data set or an overlapping data set and ask questions. So it's a very, very general formulation. Now the problem of privacy-preserving data analysis dates back at least to 1965 randomized response of Warner. And so it is an old problem, and when I began this work, I was working with my then intern, Adam Smith, and our driving scenario was that of the US Census Bureau. Our idea was that, first of all, the motivation should be fairly clean here. It's an analysis of the people's data to allocate the resources of the people, hopefully for the benefit of the people, and there is a legal mandate for privacy. So there's a law about privacy of the responses in the Census. So there was real motivation, we felt, on the part of the curators of the data to ensure privacy. We'll talk more about the Census, of course, later. So here's an example, flossing. Flossing will be our favorite. Going back to the intuition about statistics being private, I said that this intuition needs some help, and here's the problem. Suppose we have exact answers to the following two questions. How many living physics Nobel laureates floss regularly, and how many male living physics Nobel laureates floss regularly? If we had exact answers to both of those questions, then we would know whether or not Donna Strickland flosses regularly, and this would be a compromise of her privacy. So even though both of these could be very large sets, it's their intersection or their set difference being so small that is causing us a problem. This differencing attack is just one example of how seemingly innocuous questions, possibly posed over very large sets of data, can be combined to compromise privacy. And more generally, we have the fundamental law of information recovery, which says that intuitively if you have overly accurate estimates of too many statistics, then this is completely non-private. You can totally break privacy. So this was a seminal result of D'Norah Nisim, and many variants of this basic theorem have been proven. The definition of overly accurate will change according to the number of queries. So if you're going to have a very large number of queries, then to prevent total loss of privacy, you need to have a lot of noise in the answers. But if you have fewer queries, you can get by with smaller noise. And this result applies equally to interactive and non-interactive systems. So I gave you a picture before where I was clearly indicating interaction, question one answer, one question, two answer, two. But I said that those questions could be pretty broad, like give me the following collection of marginals. So the same is true here. The question might be, give me a table that lets me reconstruct the answers to the following very large set of queries. So early on when we were doing this work, I got a call from a medical researcher who said exactly, can't you just give me a noisy table that will let me get answers to all of the questions I want to ask as I figure out what they are? And the answer is no. If I gave you something that would in fact let you accurately answer or relatively overly accurately answer too many of those questions that you're choosing on the fly, then it would be a violation of the fundamental law of information recovery. So even if I hand you a blob that you can compute on and get relatively accurate answers from, the same problem would show up. So what's the definition of differential privacy and how did we get there? This is a picture of Cecilia Helena Payne Gapushchin, 1900 to 1979. She was among the first women to obtain a PhD in astronomy and she ascertained the temperatures of different classes of stars and estimated the great abundance of hydrogen in them, much more than there is in Earth. And so her dissertation work disputed the incorrect belief at the time that the Earth and the stars had the same composition. So here she is, Payne is in this database. What kind of privacy should we guarantee for her? What does it mean to say that we are protecting her privacy against a data analyst? So the first thing that we would try is a definition that says that the analyst can't learn anything about Payne that she didn't already know about Payne. Nothing new. And this is a definition that's very evocative of semantic security for a crypto system and it is also the disideratum that the statistician, Tordelinius, articulated for what he called the statistical database in 1977. So the problem with this definition is if that's your goal, then what's the point? So for example, suppose that I'm from Mars and I believe that all humans have two left feet. And in particular, I think that Payne has two left feet. I carry out a statistical analysis of the dataset and I learned that the vast majority of humans have one left foot and one right foot. So now my beliefs about Payne have changed and I think that she has one left foot and one right foot. I have learned something new about her, something I didn't know before. Have I violated her privacy? So that's a definitional question. You get to make a decision about that and your definition, your intuition may say, yes, this is a privacy violation, but it was not our intuition. We said this is not a privacy violation and the reason it's not a violation is that the same things would have been learned about Payne even if she had it opted out or even if she had been replaced in the dataset with another random member of the population. So this is Henrietta Swan Leavitt, another physicist who was the first to know the relation between certain variable stars' brightnesses and the period over which that brightness varied. And that, her observations gave rise to a law which proved a valuable means for estimating distances in space. Okay. So we're going to be learning, if we would be learning the same things, independent of whether any individual opts in or opts out of the dataset, our intuition is that it's not a privacy violation for these people. So that's led to the English language definition of differential privacy, that the outcome of any analysis should be essentially equally likely independent of whether any individual opts in or opts out of the dataset. So even an analyst who knows the whole rest of the database and who thinks there are two possible worlds, it's this database all by itself, that's the bottom picture, or it's this database plus the data of Payne, that's the other database. Even such an analyst shouldn't be able to determine which of the two databases is actually the case. Okay. So an adversary, again, knowing both datasets in their entirety should never be able to distinguish which of the two cases is the reality. And so you have to ask, what's the source of uncertainty when I say that the outcome of an analysis is essentially equally likely? What is that likelihood over? So our algorithms are going to flip coins. Our guarantee is going to be worst case for all pairs of databases that differ in the data of just one person. And the probability spaces will always be coin flips of the algorithm. And that's good because we are the algorithm designers, we're the good guys, we can make sure that the algorithm flips its coins. So if you're not used to thinking about similar probability distributions, or if you're ever going to be explaining this definition to somebody else, the following metaphor might be useful. Think about a fair coin versus a very slightly biased coin. So your fair coin has probability a half, or specifically, let's say, 500 out of 1,000 of coming up heads. And our slightly biased coin will have probability, say, 501 over 1,000 of coming up heads. So think about the coin now as playing the role of the database. And we have an algorithm which is going to flip a coin and tell you whether it's heads or tails. So given one of these coins, the flipping algorithm will now produce either heads or tails. And the probability distribution on the outcomes is, as you can see plainly, nearly the same for the two coins. The probability of heads in one is 500 over 1,000 and in the other is 501 over 1,000. So they're nearly the same. And given one or even several coin flips of the same coin. An adversary can never actually determine which of the coins is the true one with any degree of certainty. Now, it's a very strong definition of privacy, almost the same output distributions independent of the participation of any individual. Why does it allow us to do any kind of data analysis at all? So some of you know something about machine learning and you know that stability, that is the stability of the output of the algorithm to small changes in the data set is actually essential for the ability to generalize from your data set to the population from which the data set is drawn. So stability preserves privacy, but it also prevents overfitting. And so that's just a little bit of an intuition as to why, even though we think of sort of adding noise or randomness as interfering with utility and putting privacy into conflict with utility, it actually is helping learning. Privacy and generalization turn out to be aligned. So here's the formal definition now of differential privacy. Our algorithms are called M for mechanism. And we need the concept of adjacent data sets. And those are pairs of data sets exactly as we've been discussing. These are data sets that are almost identical, but one data set contains the data of just one more person. Oops, I want to go back to this definition. One more person. Now you have an algorithm, the algorithm maps databases to some output space, and so we can look at output events called, say, S. And the definition of differential privacy, and this is due to joint work with McSherry, Nisseman Smith, says that the probability that we observe this event, any event, S, when the algorithm is running on database X, is at most e to the epsilon times the probability that we see S when we're running on database Y. So what is this epsilon? In differential privacy, privacy is not binary, but rather there is a measure of privacy loss, which is called typically epsilon. And this is controlling the ratio of the probabilities of observing S on adjacent data sets X and Y. Those are data sets that differ in the data of just one person. And the probability spaces here are over the coins of the algorithm, our mechanism M. So if you're not so comfortable with e to the epsilon, when epsilon is small, this is approximately one plus epsilon. So this is a statement, differential privacy is a statement about the behavior of the algorithm M. It has absolutely nothing to do with who knows what. I don't know why this is advancing. It has nothing to do with who knows what now or in the future. So if you see an output, it's like seeing a head or tail from that coin flipping algorithm. No matter what other information you get, other than telling you which of the two databases it is, which of the two coins it is, you won't be able to determine which of the databases it is. And the intuition, of course, is that if you can't even tell whether or not I'm in the data set, you certainly can't be learning details about me that are specific to me and aren't just general statements about the population as a whole. So this says you can learn about pain, but you can only learn things that you could have learned without her participation. And as I said, we call this a bounded ratio condition. I've just rewritten the inequality. And notice that the roles of X and Y are completely symmetric in this definition. We said that X and Y are adjacent, meaning one of them is larger than the other and the larger one contains the data of just one more person. But the inequality holds whether the larger one is X or the larger one is Y. So going back to the needle in the haystack, I said that differential privacy is the wrong tool for privately finding the needle in the haystack. And the reason is that differential privacy protects the outliers. It protects every individual. And indeed, this was intentional. Our feeling was that the outliers needed protection perhaps more than everybody else. So if you think of X as the haystack and Y as the haystack without the needle, what you're going to observe in outputs from a differentially private algorithm will be essentially the same, independent even of the presence of the needle. So it certainly isn't going to help you to find the needle. So here are some key properties of differential privacy that follow immediately from the definition. First it's resilient to present and future information from other sources. It also composes gracefully and automatically. That is, we understand the cumulative privacy loss over multiple computations on the same or on intersecting data sets. In the very worst case, the losses add up. More advanced analyses involve understanding that the privacy loss is in fact a random variable. And nicely, sometimes it's positive, but sometimes it's negative. So that we do get cancellation effects and there are concentration results. That's beyond the scope of today's talk. As we understand how privacy loss accumulates over multiple computations, differential privacy becomes programmable. That is, you can define small, differentially private primitives and then combine them to carry out in a differentially private way more complex statistical analyses. And you can control by setting the epsilon parameters accordingly, you can control the cumulative loss. And this is what makes it so strong. There is, to my knowledge, no other method that permits this. So composition is the sine qua non of differential privacy. So here's one technique just to give you a flavor. There are many techniques for achieving differential privacy and many little computational primitives that you might have. Here is one extremely useful computational primitive. So suppose what you are interested in is computing some function F on your data set. A key quantity for us is going to be how much the value of any single individual can swing, how much the data of any single individual can swing the value of the function F. So we look at the maximum over all adjacent data sets. Those are data sets differing in the data of just one person of F of X minus F of Y. And we take that absolute value, that's our sensitivity or delta one. And the theorem is the following. So this is the Laplace noise distribution. And it takes a parameter and you can see a bunch of different values of the parameter. Probably you can't read the font. But the idea is when the parameter is larger, the data, the spread is fatter, the curve is fatter. And I've centered it at zero. So what does the theorem say? It says that if you want to release the value of F on your data set in a differentially private way, it suffices to first compute F on your data set, that's F of X, and then add Laplace noise that's drawn with parameter, the sensitivity divided by epsilon. So let's just talk about that parameter for a moment. Intuitively, if the data of one person can really swing the value of the function F, then you want a fat curve. And indeed delta one is sitting up there in the numerator, so a bigger sensitivity gives you a fatter curve. If you want very good privacy, then again, you want a fat curve. You don't want a curve that's really peaked right over F of X. And so really good privacy corresponds to really small epsilon. And here is epsilon in the denominator, so small epsilon again blows up our parameter B. So things are in their right place. And in fact, we'll see in a moment why this works. But here's the first observation. We tended to think about epsilon as a constant. So for thinking about epsilon as a constant, a draw from this distribution is, sorry, so think about a counting query. How many people in the data space are over six feet tall? The sensitivity of this counting query is one, because the addition or deletion of any one person can change the count of the number of people who are over six feet tall by just one. And for any counting query, the sensitivity is one. And so if epsilon is a constant, what we're adding here is noise that we expect will have magnitude one over epsilon or a constant. So the noise is roughly one for a single counting query. Now, I promised a quick proof of this. So the proof is simple, and it relies on the fact that the probability density function for the Laplace noise distribution, when the parameter is some value B, will drop off exponentially, so P of t will drop off exponentially in the magnitude of t divided by B. So for any t, the ratio of the probabilities that we will see the outcome t when, or the density at t, when the database is x and when the database is y, is given by this expression on the left. And just using the triangle inequality, that gives us e to the magnitude f of x minus f of y divided by the parameter B. That magnitude is by definition bounded by the sensitivity delta one, and the parameter B is delta one over epsilon, and so we get this bound of e to the epsilon. Now suppose we want to look at a number of different queries or some k-ary function. You can think of k different queries as a k-ary function, but it could also just be something else in high dimensional space. Then the same theorem and the same proof works, but for a slightly different definition of sensitivity. Instead of the absolute value of f of x minus f of y, it's the L1 norm now, which is the sum of the absolute values of the individual coefficients. But the same theorem holds, and what we're doing now is we're drawing fresh random noise scaled to this new sensitivity for each of the k different components of the output. So in particular, what that would say would be that for k counting queries, you would need noise that scales to k. I mentioned work that involves looking at privacy loss as a random variable and using cancellation, and with that you can get a relaxed notion of differential privacy where this value turns into something it's closer to square root of k. So now though something really interesting happened. In particular, think about a histogram query. So in a histogram query, you have your space of individuals and you carve it up into some arbitrary number of cells of arbitrary shape, and you want to know how many individuals are in each of the different cells. But a histogram query has sensitivity 1. That is, adding or deleting a single person can change the count in only one cell and can change that count by only one. And so the sensitivity of a histogram query is actually, again, just one. Even though it might be a large, large number of cells, you only now have to add noise scale to 1 over epsilon rather than k over epsilon to each of these cells. All right. So three notes from the history of pods in SIGMOD. So this fundamental law of information reconstruction, the seminal work in this area, was published here in 2003 at pods. And then it won the test of time award. And section three of that paper says that it's not a heavily looked at section. It says that you can get meaningful privacy analysis for almost n squared queries. And so the power of the reconstruction theorem is it says, look, we don't know what you mean by privacy. But we're going to show you something bad that can happen. And you're going to agree that whatever you thought of privacy as, this bad thing violates that. So that was really powerful. But there wasn't yet a real definition of privacy. And in fact, when Colby came to visit me at Microsoft, and I had been thinking about privacy for the hotmail user database, which at the time had like 500 million users. And he was showing me some attack. And the attack took n squared queries. And I was thinking, you know, n is 500 million n squared, not so likely. And I said, well, what happens if we cut off the questions after a little while? I mean, you don't like sneak off and secretly ask 500 million queries, let alone that number squared. And we worked on this, and we were able to repurpose an argument that Colby and Erit had for some other thing, and show that we got some kind of meaningful notion of privacy. So but as I said, we didn't yet have the definition of differential privacy. And two years later, also here at PODS, there was another paper, this was with Blum, McSherry, and Niseem. And there what we said was, okay, we understand how to, with this sort of clumsy definition of privacy, how to ask privacy preserving counting queries, let's look at that as a computational primitive and see what we can do with it. And then we showed that you could carry out a lot of common data mining tasks, like a version of the perceptron algorithm and singular value decomposition and K-means computations, and in fact, anything learnable in the statistical queries learning model in a differentially private way. And this sort of algorithmic beginning, I think, was key. So PODS played a really key role in this history. And it's, there were other publications about differential privacy and other interesting work on privacy in general here, but I'm just mentioning three. In 2009, Frank McSherry in SIGMOD published a paper on what he called pink or privacy integrated queries. And this is a general programming platform to facilitate programming with differential privacy, including monitoring of the privacy loss budget, how much privacy loss has been happening. And I wanted to particularly mention that because it's winning the SIGMOD Test of Time award this year, so congratulations to Frank. Now, there are lots of algorithms for many different tasks, and there are also relaxed studies of lots of different things that are related to differential privacy, and in fact, the fields has kind of come to encompass all of these. Relaxations for privacy loss that I mentioned before. Things like studies of lower bounds on sample complexity, lower bounds on computational complexity, economics perspectives. This is all like from the outside, right, this is all work done in DP. There are applications of differential privacy also to other fields. So there are results that came in geometry from insights derived from differential privacy, also in economics, in online learning, and most recently in a paper by Scott Aronson and Guy Rothblum in gentle measurements in quantum. So there's something I think very fundamental to computing with a little bit of noise that seems to be helping in lots of different directions. Just want to mention before getting onto the discussion of the census, one surprising application of differential privacy, and that is that it neutralizes the risks to validity that are caused by adaptivity. So choosing your next question based on the answer to the previous questions. So this is a very, this is a risk always in data exploration where you sort of trawl around in the data looking for stuff, and so it's going to eliminate the sources of p-hacking and overfitting that come from adaptivity. And I only have time to give a little bit of an intuition, but here's the intuition. So fix a query queue, any query that you want to know something about for your population. And then go off and recruit a database X, and you're going to now evaluate this query on your database and try to learn something about your population as a result. So of course, with high probability, the database that you go out and recruit will be somehow representative of the population with respect to Q. This is why statistics works. This just, that's how it works. You have this thing you want to study, you go and you get a sample of the population and you study it on the population, and you expect that it's telling you about the population as a whole. That's why it works. So if I think now of p-hacking and overfitting as kind of an adversarial attempt to find a query for which the dataset is not representative, differential privacy is going to protect. So we have this initial intuition, or this initial fact. Now you could reverse the order of the steps if you're careful. So first recruit a database using proper sampling technology. Now without looking at the database, choose your query. Well of course the query is still independent of the database, so you're in the same situation that you were in before and you're really unlikely to choose a query for which your database is not representative of the population as a whole. Just as, because you've done something completely equivalent to what happened in the previous case. So now suppose during the course of interacting with your dataset, the analyst can find a query for which the dataset is not representative. Then intuitively she must have learned a lot about the database because we just saw that when she didn't know anything about the database, she was really unlikely to come up with such a query. And so differential privacy prevents the analyst from learning enough about the dataset to find a query on which the dataset is not representative. So differential privacy today, it's being used a lot in industry. In Apple, Google, Microsoft and Uber, for example, a lot of this work is done in what's called the local model. Meaning that in the pictures I've been showing you, there's a dataset that's been collected or curated and the analyst interacts with the dataset. In many of the industrial applications, raw data aren't being gathered from the clients, but rather privacy is being rolled in at the client level and this privacy preserving version of the data is being sent up to the server. And in industry parlance, this is called moving the trust boundary out to the client. So certainly Apple and Google and Microsoft are doing things in that model. Now Facebook has recently announced a secure and private artificial intelligence scholarship aimed to equip students with privacy preserving technologies such as federated learning, differential privacy and encrypted computation. And a high up person at LinkedIn tells me that LinkedIn is investing heavily in differential privacy and is, by the way, almost all of these companies are recruiting in this area, so center students for jobs could be very, very exciting time. The oldest deployment of differential privacy, large scale deployment is within a Census Bureau product called On the Map, which is a website that allows the public to learn where people work and where workers live. And recently there's been new work based on census data in the Opportunity Atlas, mapping the childhood roots of social mobility. So this is work by the economist Raj Chetty and colleagues that have deployed something very close to differential privacy in constructing this Opportunity Atlas. And I will say more about this later on in the talk. Now every decade the U.S. government carries out a complete enumeration of people living in the United States. The enumerated population in each state serves as the basis for apportionment of the 435 representatives in the House of Representatives. And in addition, this enumeration is, decides where hundreds of billions of dollars in federal financing is allocated. It also is, this information is also used for enforcing the Voting Rights Act and in redistricting. Okay, in the 2010 census, completely typically, 7.7 billion statistics were released from the data that were collected by census. And there are about some 300,000 individuals. And in light of these reconstruction attacks that I've been talking about, John Aboud, who is the Chief Scientist and Associate Director of Research and Methodology at the Bureau, decided that census should check to see what was the nature of the privacy protection, which is mandated by law, what was the nature of the privacy protection against these sorts of reconstruction attacks. And he looked at the 2010 data. So he knows what was released to the public, and he also knows what was collected because he's at the census. And his conclusion was, as you can see, that technical advances revealed a new vulnerability, allowing people to reconstruct data from tables that were previously assumed to be privacy preserving. And this is a slide from a talk that John Aboud gave in February of this year. He talked a little bit about his attack. And so these are his slides. And essentially, what they did was, first of all, they took all of the released information, and from that, they sort of reconstructed a whole bunch of putative individuals, of everybody in the data set. So that means that they wrote down a collection of attributes. This is without names, but a collection of attributes for each of the individuals, supposedly, in the census. And then they linked these putative people to commercially available data sets that contained names. So what do I mean by linking? I mean, you have basically the, you have a bunch of attributes in your putative reconstructions, and in the public data set, you have some of these attributes and the names, and you match them up, and now you have names for the people in your data set. So they did a lot of linking. And they weren't able to link everybody, but they were able to link many. And when they did this, they got hold of now the names for these putative people where they thought they had success. And then they were able to look at the census data to see did they get the names correct, and moreover, did they reconstruct the attributes correctly for those people? And what they found was that they had perfectly reconstructed 17% of the population. That's 52 million people. And the specific things that they were able to reconstruct for these people, the harms that they envisioned, is that an attacker carrying out the same reconstruction would be able to learn people's self-response for race and ethnicity. Now, yeah, okay. You'll see in a little bit, I'll show you the census form. It doesn't have much more than that. But there's another census form which is not part of the decennial census, which is much more rich, and the privacy harms could be more dramatic. For example, you could learn if somebody was adopted or not. Okay. So Abeld says, we fixed this for the 2020 census by implementing differential privacy. So what do you think the response was on the part of people who work with census data? Were they thrilled that they were now sort of going to be morally in the clear because there was no privacy compromise? Well, no. And in fact, this is greeted with a lot of concern and anxiety. So first of all, there were simply people who say, well, the old protections worked well and the law doesn't care what you learn about people. It only cares whether or not you can match a record to a name. If the law doesn't care what you can learn about people, then I don't understand the point of the law. And in fact, this is a very interesting question, but okay. And then there was a lot of concern about utility in general. So what happens when you ask questions and require a certain amount of accuracy and you sort of use up the privacy budget? You can't go any further because the fundamental law is about to kick in. Huge amounts of money have been spent gathering data for the census. It's the largest peacetime mobilization. And also for other surveys by federal statistical agencies, just billions of dollars are spent gathering these information. What happens when we can't use them anymore? All right. So these are real concerns, and I don't, as a computer scientist, I don't have answers to these questions, but it's important to sort of think again about the context. People share their data because they are assured of confidentiality. That really is drawn into stark relief when you think about what's been happening in the United States and the push, for example, to include a citizenship question, which at least temporarily has been pushed back, but we don't know whether that's going to stay. The Supreme Court said we don't like your justification, but you can try to come up with a justification that we do like. Okay. So assuming, though, that we're going forward with differential privacy, let's talk about some of the specific challenges. So one of them I have already alluded to. It's the allocation of the privacy resource. So in some sense, we have a privacy budget, which is a cap on the cumulative privacy loss that we think we ought to be tolerating. So first of all, how do you choose this privacy cap? How do you choose this budget? And who should choose this budget? The question makes sense for census, but it also makes sense for the various industrial uses. And once you have chosen a budget, there's a finiteness to everything. And census has to figure out among the questions that it is going to answer or among the statistics and tables that it's going to release, which ones should be given priority? Which ones should be given the best accuracy and get to use up more of the privacy budget? And which ones have to have less good accuracy and use up less of the budget? And this is not the kind of question that census has had to confront in the past. So they're trying very hard to find out from their users, what do you need? What are the queries that you need to be able to answer? Now this question about how and when to allocate, I mean, how to allocate the budget, this is one where perhaps economists have something to say. And in fact, John A. Bowden and Ian Schmouta have a paper about exactly this question. And they say that, and I'm quoting now, economists recognize this is a problem of resource allocation. We propose an economic framework for solving it. Statistical agencies must allocate information in their collected data between two competing uses, production of statistics that are sufficiently accurate, balanced against the protection of privacy for those in the data. We combine the economic theory of public goods with cryptographic methods from computer science to show that social welfare maximization can and should guide how statistical agencies manage this tradeoff. And the paper is very, very interesting. Okay. What's another problem? Another problem is that the people who work from the census data and the released statistics, so historians, sociologists, demographers, economists, are simply not trained to interact with the data in a differentially private way. They're not trained to ask queries and get responses. If you take a class in statistics, the first thing that you're told is, look at the data. Well, you can't look at the data in our methodology. You can't see raw data. You have to ask queries and get differentially private responses. Now, you might say, if you have a database of 300 million people, what does it mean to look at the data anyway? Aren't you, in fact, always looking at some statistic of the data or some illustration of the data of some sort and can't these things be done in a differentially private way? Maybe often the answer is yes, but still, the people who work with the data are not accustomed to this. And in no way do I want to minimize the difficulties here. This is a sea change in the way people have to operate. Another thing is that they have to be trained to deal with noise. Social privacy intentionally adds noise at various points in the computations. People are used to thinking of things that the Census Bureau releases as actually being noise free. It's not true. They've always been adding noise in one way or another. They've always been doing something in order to protect privacy. It just hasn't been enough, and that was what the results of the 2010 attack showed us. But everybody is used to thinking of everything that's released as being ground truth. Here you have to learn to adjust for the noise. The nice thing about differential privacy is the methods are completely public, and a trained analyst can, in fact, adjust for the noise. And this is different from how things were in the past, but you have to learn to do it. Now the Census Bureau goes to a lot of effort in their work to kind of make some of the artifacts of differential privacy invisible to the user. So for example, in differential privacy we add noise, and we might be looking at a count, and the count that's released might be negative, or it might not be an integer. And these are fine. We understand how to interpret a negative count. It means that the true count is very small, and the noise pushed it negative. Okay, fine, not a problem. We know that there aren't really a negative number of people, and similarly with nonintegrality. But when I say they go through a lot of noise, I mean they're solving integer programming problems in order to produce nice, integral things. Some day, perhaps, people can learn to deal with non-integer negative things or inconsistent counts because you've added noise differently in different places. And again, if you understand what's going on, you can cope with this, but that requires a high degree of sophistication. And we're definitely not there yet. And finally, a lot of research remains on a purely technical level. So we know how to do a lot of things very well using differential privacy, and there are a lot of things we might want to do that we don't yet know how to do well. The field is still relatively young. There's essentially no work on differentially private data cleaning, or we need to do more work in order to investigate things like tales of a distribution. Social scientists will often tell you that all the interesting stuff happens in the outliers. I have no answer there. That's my needle in a haystack. And I'm also not enough of a data analyst to know how I should interpret the statement. But maybe some of you do. Now, I've been talking about the decennial census. So this is actually a picture of the entire 2010 decennial census form. As the website said, 10 questions, 10 minutes. So what are the things that are being asked? Because I'm sure you can't see the font. There's a householder who is supposed to fill out the form. And in fact, information has to be given for every member of the household. But so for each person, first of all, how many people are living in the home as of this certain date? How many other people often stay in the home? Is the home in a house, is it an apartment, is it a mobile home? Phone number, name, sex, and age of each person in the house. And then questions about ethnicity and race. So Hispanic or Latino origin, and there are a number of categories there, and race. And there are several categories there. And people can check all of the boxes that apply to them. And then finally, there's a question about whether this person ever stays anywhere else. So for example, in college or in a military barracks or in jail, for that matter. So this is the easy case. And why do I say this is the easy case? Well, it turns out that there's 44 bits of information collected per person. Not that much in these fields, not including the name, of course. Every year, a random subsample of the US population also fills out another form. So this is, I think, a 5% I'm not sure sample of the population. Fills out another form called the American Community Survey. And this is what used to be called the long form, but now this is done every year on a rolling basis. So here are the things that are covered in the community survey. Building ancestry, journey to work, computer and internet use, disability, employment, family and relationship to the householder, fertility, food stamps, grandparents as caregivers, health insurance coverage, Hispanic origin, home heating fuel, housing costs for owners, industry occupation and class of worker, marital status and history, ownership, home value and rent, place of birth and citizenship and year of entry, plumbing, kitchen and telephone service, residence one year ago and migration, school enrollment, sex, vehicles available, veteran status, the year built and the year moved in. So you can see that this is an extremely rich collection of information about each person. If things are difficult now with this form, what's going to happen with the ACS? Okay. So one thing that people talk about is a different mode of interaction with the database. So an example is restricted access data centers. This is a picture of Steve Feinberg pictured with his wife Joyce. Steve was a renowned statistician and an expert in disclosure limitation among other fields. And early conversations with Steve starting in 2004 or 2005 led to close ties between members of several communities. For example, this is how the differential privacy people were brought into contact with the labor economist John Aboud who is now the chief scientist at the census. And the field of differential privacy has benefited enormously from this cross-disciplinary early contact. And it's through Feinberg that I first learned a little bit about how statisticians approach data and the sea change that would be needed to make this new approach accessible to even very trained statisticians. So Steve died in December of 2016 and Joyce was one of 11 people murdered in October of 2018 at the Tree of Life synagogue massacre in Pittsburgh. And I miss them both very much. Now there's this discussion of increased use of restricted access data centers for viewing census data. And this question starting a couple of years ago led to what in formulae is called the Feinberg problem. So the Feinberg problem is basically, Steve would say, I need to look at the data. And I trusted Steve. We all trusted Steve. And he knew what he was doing. And he was smart and he was well-intentioned. And so the question is, could we allow him to look at raw data and then think, you know, do whatever he normally does, but when he decides that he has found a statistic that he wants to make public, we would publish that statistic, but we would redo the computation in a differentially private way for that statistic. So we'd like to be able to do this. And it turns out to be difficult. And the reason immediately is that the choice of which statistic you're going to publish may itself be disclosive. I may, you know, Steve may only choose to publish a particular statistic because he happened to see Bill Gates' data in the data set and that made him think of something or other and he decided that would be an interesting statistic. So the choice of which statistic to publish is, could be sensitive. And the way to think about it is sort of, you have to get the right level of abstraction. Estimates are just functions that we don't understand that interact with data and make choices about what to publish. So we need a way of making this differentially private. And astonishingly, there are some, like, toy ways of going about it, but there's a lot of work to be done on that problem. Now in addition to publishing estimates and tables, the Census Bureau also publishes something called public use micro data. And you can think of these as little synthetic data records, except, sorry, they're not synthetic there. They've taken real data records and they've pulled out some identifying information and they've carried out something called swapping, which means that occasionally they take a family in this geographic region and one over here and they literally swap their data. And the point of swapping is to introduce uncertainty about whether what you're seeing is really a person who lives down the street from you or is in fact the data of someone swapped in from Michigan. So can we do privacy preserving micro data? And the answer is, well, maybe, but again, the fundamental law applies and in fact there are hardness results. So in the interest of time, I'm going to skip this slide, which gives you some intuition about hardness results, because I would like to end on a positive note, which is an interesting, wonderful recent piece of work. So I mentioned the opportunity at last before. And I'm going to describe now as a result from a paper by Raj Chetty and John Friedman, a practical method to reduce privacy loss when disclosing statistics based on small samples. Quoting from their paper, actually I won't. So what they do is building on techniques from differential privacy. They suggest a method to reduce privacy loss for certain kinds of statistics, such as ordinary least squares, regression elements, estimates based on small samples. And there is a technicality that makes their technique not differentially private, but first of all, our intuition says that this shouldn't be very risky, and as I'll tell you in a moment, it also led to improvements or strengthenings that are in fact differentially private. So this is a graph of low income black women. On the x-axis is in their census tract what percentage of the homes are single parent homes. And on the y-axis is the teen birth rate. So it's the teen birth rate for low income black women. And this is a picture of what was obtained with noise infused data, and the conclusions that they reach are the same as they would have reached. I mean, they were able to check without the noise. So what they're showing here is in this image, you can see there's a clear positive relationship between the two variables in ordinary least squares regression. So in other words, the context matters, and if there are very few single family homes, then these poor black women do not have teenage mothers. But if there is a large percentage of single family homes, then they are more likely. And you get this nice, or nice, I don't know, you get this clear linear relationship. Now this involves looking at census tracts. And a commonly used technique previously before differential privacy is called cell suppression. When you have counts that are very small, say less than five, you simply don't report the results for this cell. Although often the results, if the count is zero, they will report because that's not viewed as being disclosive. So this is what happens when you have cell suppression. So what's going on here is that it's completely obscuring the linear relationship. And this actually happens for two reasons. By omitting the cells that have few teenage births, you're omitting tracts with low but nonzero teenage births. These are the tracts that happen to have few single parents. And so those data are simply being written out of the story, and the results are biased accordingly. The second effect that's going on is that black women who grew up in tracts with smaller black populations have fewer teenage births, and these in turn are more likely to be suppressed. So not only are you not getting the story, but you're getting a really biased story. It didn't say, hey, we fail. It said, here's what's going on, and it's actually the wrong story. And this kind of distortion contributes to the myth of hypersexualization among African-American women. So finally, I mentioned that spurred by this work, and in conversations with Chetty and Friedman, a lobby McMillan, Serati, Smith, and Vodan have been looking at new algorithms that are differentially private for ordinary least squares for this particular setting with very small samples. And roughly speaking, the green in the picture is what Chetty and Friedman were getting, and the orange in the picture is the better algorithm, and the blue in the picture is the not so good differentially private algorithm. But we can see that the orange is approaching the green, which is all I have time to say. Thank you very much for your attention.
talk, but differential privacy will be the solution. Differential privacy won't do it for of it. So statistics, differential privacy is US Census Bureau. Our idea was that, first of over very large sets of data, can be combined to of stars and estimated the great abundance of statistical analysis of the dataset and I learned distinguish which of the two cases is the Now, it's a very strong definition of privacy, statement, differential privacy is a statement to do with who knows what now or in the future. haystack and Y as the haystack without the from a differentially private algorithm will be parameters accordingly, you can control the analyst interacts with the dataset. In many of the nature of the privacy protection against which is not part of the decennial census, which we fixed this for the 2020 census by implementing worked well and the law doesn't care what you on the cumulative privacy loss that we think we field of differential privacy has benefited