ZK10: Zero Knowledge Differential Privacy: The road to two-way trustless data sharing - Manuj Mishra

Transcript

[Music] okay uh so yeah I'm presenting on zero knowledge differential privacy um which is a way for two-way trustless data sharing between um a curator of data and people who want to make aggregated queries on a set of data so first I'll start by sort of motivating this problem uh this is not a fairy tale this is a real world uh story of of something that happened so in 2009 Netflix um realized that they could improve their movie recommendation algorithm massively If instead of just working with the ml engineers in their company they um created an open competition for everyone

in the ml Community to have a go at trying to produce the best movie recommendation algorithm of course this was a great idea but Netflix has a lot of private data about people so what they did was they completely pseudo anonymized it names addresses any personally identifiable information was hidden so you couldn't see personal identifiable information associated with movie ratings in this database they then released it into the wild and leted people have a go at producing the best machine learning algorithm the problem with this was that hackers were able to um uh use auxiliary data sources like the IMDb database and match up movies that people had um rated on IMDb to their ratings in Netflix and

what that meant is they could then Trace back exact individual users and their names from the IMDb database and personally identifiable information was able to be extracted from something that was supposed to be completely private because of pseudo anonymity um so this kind of reconstruction attack is inevitable in almost any sort of um scheme where you are making infinitely many queries and you're giving perfectly accurate answers about data which is where differential privacy comes in so um this whole conference is about zero knowledge and zero knowledge has a slightly different use case I mean this is a very high level sort of like analogy you can can say that you know ZK can say that I have some data I can I can prove certain properties about it with without revealing what that data is differential privacy is about something

else entirely it's about taking aggregate queries on a database and saying you know I won't give you the exact answer because if I give you the exact answer you can use some other public data that's floating around on the internet and reconstruct and do reconstruction attacks so I will give you a slightly inaccurate answer um and um how this works is essentially um if you make an aggregate query on a dat for example you might be asking uh you know you have a database of users and their screen time and you ask what's the mean screen time of any user um you might have a version of a database with JN in it and to Pro protect J's personal privacy privacy what you want is when someone U makes a query to database D Prime they should never be able to tell whether John was

in that database or not and so instead of returning the actual mean of that database you return a sample from a slightly noisy distribution where the the mean is well the mean of the distribution is the mean of the database so you have a distribution associated with joh being in the database and a distribution associated with John not being in the database and you want the difference the the Reni Divergence to be specific you want the Divergence between those two distributions to be below some privacy threshold uh that's the essence of differential privacy you have neighboring data sets and you want it so that any person who's quering a database can never tell whether your whe whether the state of the database is what it actually is or some neighboring state um uh this is the formal definition about

half of you had already come across differential privacy so I'm sure you've seen this definition before um but essentially what it's saying I what I just described was what's called Epsilon zero differential privacy which is where you um are saying that the probability that a mechanism the output of a mechanism on a database is in some set of outcomes is bounded well okay Epsilon is very close to zero so X Epsilon is close to one so it's saying it's very close to if there was some neighboring database and you took uh you took a query on that database and it was in the same set of outcomes and then um plus Delta is a term to sort of increase the bound and and what you what that means is basically there is a one minus Delta probability that the database is Epsilon differentially private I mean this is

going into the the weeds of it but um I hope that this example gave you a sense of what differential privacy is trying to solve um what what qualities does differential privacy have well it means that once you've taken a query of this database and you get a noisy outut it's completely immune to post-processing so regardless of what someone does after that you know they could take the mean and they could then run it through as many machine learning algorithms as they want they could try and use the IMDb reconstruction attack they could use some private data that they've collected it doesn't matter they will never be able to reconstruct um individual information about that data because it was fun it was noisy enough that the probability of that doing that of that of them doing that is below a certain bound it's composable um it's composable

with the caveat that if you make more and more queries your data becomes less and less private I mean this is just the way uh the these things work that you know if you take uh an you know if you have an Epsilon one bound on a particular query and an Epsilon 2 bound on another query and then you're using both of the results of both of those queries and you're you're composing them together to get some more information the bound on the privacy of the composed result will be Epsilon 1 plus Epsilon 2 so it gets worse over time so that is definitely a caveat to think about in terms of like what the use cases of this technology are uh and as I said it's robust against the kind of Netflix attacks that I was talking about before so this is how it works at the moment I

mean in terms of real world like the US Census uses this for the first time I think the most recent US Census used a differentially private database the UN uses it for their um information on like the Rwandan Genocide and the families which escaped you know anywhere where it's individual privacy is critical organizations are already using differentially private databases um and these are the reasons why the problem is this is oneway trustless so if a research team is going to a database held by the UN and then they're getting this noisy data back they trust that the UN is giving them the right noisy data back and you can easily construct scenarios in which this might not be the case and the holding organization the data curator might have an incentive to treat certain uh queriers differently you know there might be people who

they're biased towards who they might want to give more accurate results to and people who they don't like who they want to give less accurate results to and and you you would never sort of know um there's no guarantee that the data is pure that they're not meddling with the data inside there's no guarantee that the amount of noise they're adding is minimized you know we have a mathematical bound on WE we've agreed that okay you need to add this much noise to protect the individual's privacy sure you can add that much noise but how do you know they're not adding anymore so what I did in the in the hackathon project in Paris was essentially just add in I mean the difference between these two slides is a there's a ZK proof at the top of the private answer that you get so um you

you do a ZK proof of the noise computation um and we don't need to go into the depths of all of this but I've the reason I've had the slide is so you can look into the paper that uh I was using the equations from for uh differential privacy I mean in essence what I was doing is you have um you have a um well the noise that you're adding is coming from a g gaussin distribution and you can work out the exact amount of variance on that gaussian distribution that you need to maintain privacy at a certain level and you can do that that variance calculation within a ZK proof and so that's what was uh happening there um and to summarize yeah ZK differ privacy is a way for two-way trustless data sharing between an organization

that is curating some data and queriers that are trying to use that data both parties care about the anonymity of individuals in that database But ultimately you want to be able to analyze data uh in a way that is safe to the to the individual inside and you want it to be in a way that um both parties don't have to trust that the other is you know doing things the way they should be doing and and this is why ZK can be used for something something like this um uh what I would be very keen to hear is if people have ideas for sort of like um areas where they think this could go further and applications in which the they feel that this uh this kind of stuff can be used in uh and I'd love to chat to you afterwards about that uh happy to take any questions

[Applause] now thanks a lot do we have any questions yes hi uh thanks a lot for the talk um so I just have a um quick question about the randomness so um I understand that in um in providing zero knowledge guarantees in in zkps that Randomness is out of bound so it's it's trust in a sense it's trusted Randomness um could you maybe talk a little bit about what the assumptions are around how that Randomness is seated and how that affects the the security proofs yes I think that's the most difficult bit of the ZK uh DP Paradigm is um doing provable Randomness that's not a bit that we tackled inside the one day hack project and in fact what we were doing

was just the um yeah the the seed the seed of the randomness was outside of the ZK proof and everything else so from the random seat onwards everything else was in the ZK proof so um yeah that's not a bit that we've what we've cracked yet basically follow up um so like just thinking about it right now um is it as trivial is saying the um the querier uh sends a random seed and the response is um the prf out the verified prf output of that seed as the seed Randomness as part of the thing or because it it kind of gets a bit weird right because you you sort of would then need two proofs

one of them would not be zero knowledge and the other one would be I'm just spitballing here but I don't know if you you've thought about this stuff yeah this is not an aspect of it that I've had to time to think through but I could imagine like the verifiable randomness coming from the user being a potential solution to this for sure yes uh some somewhat of a related question which just like if they you know if the goal is to make this into like a bulletproof setup right you'd also want to reason about not only the process of noise addition but also like exhausting the Privacy budget right so you don't want to have basically infinite attempts right so and then you basically I think would close the loop so what are your thoughts on that I I think this is yeah spot on

um this is a question of use cases then like it comes back to like this is a paradigm that you would want to apply somewhere perhaps where so so the way the the UN applies is they will allocate an amount of privacy budget to each team that is that has got access to this data and once they've used up that privacy budget they can't access the data anymore so you know a research team could choose to make one extremely accurate aggregate query about the mean age of everyone in the US and they would get a very very precise answer that's correct to you know thousands of decimal places um well maybe yeah uh and um that might not necessarily be the best use of their privacy budget they could also make a bunch of less uh accurate queries um one area where I think this is

particularly interesting is dynamic data so if you're if you have a database where you know you have some kind of level of churn um where the data is sort of expiring and you're you're sort of ejecting some data from the database and putting in new data then uh some of those privacy guarantees can sort of be like reset it's almost like you could refill your privacy budget and I don't know um I haven't looked into if anyone's working on this but uh I think that would be a very interesting Direction and people talk about EPO and yeah data that's like moving over time that sort of thing yeah so just a question related with kind possibly an extension um have you ever thought about how to um make the query itself private so to have

everything private and also the query itself Oh you mean like a like a proof of API call or something like that no I was thinking more like for example U maybe using multi party competition or something for the query itself to be private so so not to disclose the the query itself I don't know right um uh to to not disclose what the query is to the data curator MH um yeah that is definitely a Direction so so that's that is not one which I've I've explored but yeah you this is another area that would sort of coming back to whoever was talking about closing the loop there are there are many aspects of so I think back on the slide the bit I tackled was the bit I felt that was most needed

which is the ZK proof on the private answer that Arrow there but yes essentially every single arrow in the space you know even this bit um how are you collecting data from the generators and and putting it into the database this is where we come back to like Hardware attestation and sensors and all this kind of thing every arrow here needs to be like sort of thought about uh and yeah there's a lot of work to do in terms of closing the whole Loop all right so yeah I think we have to up so thanks again man thank you very [Applause] much