ZK11: Arke: Privacy-Preserving and Decentralised Contact Discovery - Nicolas Mohnblatt

Transcript

[Music] so um this is going to be a bit of a departure from what we saw so far very technical talks this is a very different kind of cryptography that we're going to be doing here and in a much more applied context so privacy preserving and decentralized contact Discovery this is Joint work with Alberto sonino from M and Labs Philip yvanovich from UCL and Kobe Gin from geometry research so as I said we're going to be talking about identity based cryptography which I don't think has been covered at previous ZK Summits so that's going to be quite fun and we're going to use that to bootstrap decentralized social apps and I'll explain what I mean so we'll

first go through some motivation what do I mean by contact Discovery what does it mean to do this privately and what is the threat model we're working under then we're going to look at sort of a related work section good attempts that fall short of our privacy dorata then we're going to go over Ary in two parts firstly a highle construction hopefully everyone can follow that one and then a cryptography which hopefully everyone can follow as well but this is the fun part um and then quickly a few other applications for the construction and some warnings on what not to do with it so let's start on a little journey the year is 2020x and in this year we can create Anonymous blockchain accounts from our email address pretty cool we

can prove prove in zerk that we own a specific social media handle and we can also build entend private messaging and payment apps and this is all really cool and this hopefully shouldn't sound too foreign to most people in this room and that's because this is actually happening today a lot of these things blockchain accounts from email addresses there is a talk today about this appto keus ZK proof ownership of social media handles or even email addresses you can do this with ZK email and I think they're presenting today uh messaging and payments app we've seen already great so now my question to you is are we ready to build the next generation of social

apps and this is kind of my my crude answer of we'll build a privacy for social app we won't have a mechanism for users to find their friends on this app and because it's private well it's really hard to find people and so suddenly users can't socialize with their friends and are just not going to use the app so this is the same reasoning is explained a lot more eloquently by Moxy Marlin Spike back in the 2014 article called the difficulty of private contact Discovery and so he notes that most software today is social even privacy enhancing Technologies are social and that these things only have value proportional to the people that use them what kind of network is using

this and so he says well for our app to be useful we need to access an existing social graph and that's what we mean by contact Discovery especially because in the context of signal the social graph they tap into is mobile phone numbers so your contacts so a bit more concretely again we consider a user joining signal and they want to know who in their contacts is also using signal so the problem sort of kind of looks a bit like this right we have a set of contacts a set of all signal users and what is the intersection turns out we need a bit more because knowing that my friend is on Signal is grade I also need their public key to do some cryptography there I also need to

know where to send my messages like physically where should they go so we need this intersection and some extra information now if we want to generalize this Beyond signal and phone numbers we could use other identifiers like emails or um you want to contact your exf followers and it would look a bit like this so we have users they have an existing identifier this could be their email their phone number again or uh some Twitter handle and they have a new ID which here in this example I'm using what looks like some kind of Bitcoin like block blockchain address so maybe you've used ZK login or app to keyless and you've linked your email to an

address now the question is how can a friend who knows my email find me find my sort of keyless account so we again have friends in my old graph but on the right we have users of this new graph and I have this as a dotted line because there might not be an existing set of all users in the signal example you sign up to signal with your phone number Signal knows all right all these phone numbers are registered with outto keyless or ZK login all these mechanisms no one knows who's registered so this set on the right here might not exist we also need kind of a mapping in the signal example my contacts have phone numbers signal has registered phone numbers great phone numbers in

both cases in this example we have an existing identifier some kind of handle and a new identifier which might all match so we also need this mapping what does it mean to do this privately um and I kind of have three layers of privacy here the first one is nobody should learn my contacts I shouldn't have to reveal who my friends are to find them the second one is I should be able to filter who finds the link between my old id my email address and my new account my blockchain account right like if I do ZK log and out to skus again I'm spending so much time so much effort hiding this link between my email

address and my blockchain account why would I then reveal it here the third layer is kind of hard mode it's not even revealing who signed up to the new social app that we're building against who do we want to defend well anyone right users of the app my own friends maybe they want to know if I'm friends with a specific person um so dishonest users and the service itself great so now that we have a notion of the problem at hand and so the requirements I want to look at some related works the first one is the one actually most apps use right now is just upload

all your contacts to a server and do the matching in the clear so this is what WhatsApp telegram do um the pros of this approach is that you know it works the cons is you have no privacy whatsoever and even worse you're sort of centralizing something that wasn't centralized so the mobile social graph for example I have my contacts on my phone but no one else has them as soon as I upload them to Whatsapp they can start drawing out this graph connecting the dots between my contacts your contacts and everyone so they suddenly have this almost proprietary info that no one else has so basic approach terrible second approach is private set intersection um I've been drawing these

sets and this little question mark so at some point you're like all right are we going to find the intersection of these sets um the answer is no but I'll tell you why in a second so private sence section is uh a family of protocols where we compute as it says the intersection between two sets private means we don't reveal either set we have protocols to do this in the unbalanced case so like when the set on the right is much bigger than the one on the left which is kind of the case of contact Discovery um and it's pretty practical although signal refuses to use this because they think it's too much work and they'd rather sort of emulate this with trusted

Hardware the pros is that contacts remain private by definition of how these things work the cons is that you do need this set on the right you need someone to know the list of all users and you need someone to know the mapping from their old identifier to the new one um the other problem is you can actually scrape this you can show up as an honest user with what you claim to be your contacts get the intersection but in fact you didn't show up with your contacts you showed up with a list that you're enumerating trying to find find out who is signed up or who isn't um this actually happened to Facebook back in 2019 and there's a

paper that goes over how signal WhatsApp telegram have a really hard time defending against these attacks so PSI cool but not enough so the Le the last approach we're saying all right if this second set on the right is decentralized well we're going to have to do this in a decentralized manner so that's what I'm calling peer-to-peer contact Discovery and the idea here is that users will take it on themselves to send messages to each of their contacts to say hey here's my new like my new identifier on this new social app uh this is what we do with Ary and this is what other concurrent works are

doing udm and pudding um the pros is that we can achieve all our privacy goals the cons is that now the users have to do a lot more work they take it upon themselves to send these messages and they also have to check and receive these messages from their friends all right so how do we do this peer-to-peer contact Discovery we start with users know their friends identifiers this is great I have my contacts and I want to exchange a message privately in a way that's undetectable it seems like I've haven't moved the problem forward at all right because I was saying oh I was trying to contact friends and now I'm still trying to contact friends but we can work through this and we'll

go from exchanging a message we know that we can do encryption to exchange a message privately that's great as long as I have a shared secret I can re encryption how do I get a shared secret well some more cryptography I can do a key exchange so as long as I know someone's public key we can find a shared secret and then we can do encryption so we're happy the question is how do we do this final link from someone's identifier to their public key um so so one of our concurrent works udm just publishes this mapping and that's fine because the public key reveals nothing it's just specific to the contact Discovery scheme and then what matters is the messageer exchanging it does fail at what I was

calling hard mode privacy because it does leak who is registered and who isn't what we are doing is we say your identifier is your public key so that should strike you as a bit weird um because it is and this is where this identity based photography comes into play so if your identifier is your public key then we need to somehow derive your private key from the identifier it can't be derived just from the identifier otherwise everyone could do it so it needs to be identifier and some Randomness and that's what we'll see next how do we do this um just very briefly the reason why I'm bothering to do a key exchange and then symmetric encryption is because we actually want

to exchange a message over a public Message Board without being detected and so that will require some extra work and that's why having a shared secret is nicer than just encrypting directly so this is our system this is what it looks like we have sort of three four phases first is a setup phase where your users interact with a discovery service they prove that they have their identity and they receive a corresponding public key oh sorry private key yeah um then once they have their private key and they know their contacts identifier I.E their public key they can do this key exchange locally then having done the key

exchange that was you know the little thing we were looking at earlier um you can write to this bulletin board encrypt it and read so we're going to go through this sort of bit by bit cryptographically and open these black boxes and hopefully I'm also going to convince you that this identity based thing isn't too crazy and it it is actually secure so identity based non-interactive key exchange so we read this as ID night because it's a bit of a mouthful they assume a trusted third party so red flags all over but in three slides we're going to get rid of that trusted third party and we're going to be happy uh formally it's defined by three algorithms setup which outputs po

parameters and a secret key to go to the trust of third party we have this extract algorithm that takes the secret key and and an identifier to extract the private key for this identifier and then we have the shared key function which using someone's like one user's private key and someone else's identifier deres a shared secret so importantly it has to be shared so it doesn't matter if I take the secret key of ID and then the public key of ID prime or if I take the secret key of ID Prime and the public key of ID I should be getting the same secret uh the security property of these

systems not going to dwell on this too much but it's that this shared key should not be distinguishable from a random value which also means you shouldn't be able to compute it great so how do we build these there's uh a construction from 2000 by saai orishan kasahara before I explain this a quick reminder on how pairings work we have this function e where you can put in two things G to the a h to the B um this one is a symmetric pairing but we work also with the more common asymmetric pairing so what you can do in the symmetric case is you can flip them the G and H that's great and the pairing has this property that it's bilinear so these exponents can be taken outside of

my e function leave this in a corner and back to the construction so setup looks a lot like our usual setup algorithms we sample a number as our private key and the public parameters is some kind of public key now we get into the interesting stuff extract the secret key for the identifier ID will be a hash of the identifier to the master secret key the shared key between IG and IG Prime will be a pairing of the secret key of ID with a hash of ID Prime if we write this

out I can replace skid with this h of ID to the msk take the msk out and we have this nice e of the hashes to the master secret key and if I worked from the other direction the same thing would happen cool so now how do we get rid of this trusted third party right like otherwise we've we haven't done anything if we haven't trusted thir part the system is useless so the first thing I want you to notice is that extr looks like this it's a hash of something to the power of something else and the question is does this look familiar like have you seen this somewhere hopefully for most people in

this room it's yes this is a BLS signature so your private key is a BLS signature and now the question is how can we make BLS signatures in the setting where no one knows the signing key again hopefully we should know this it's a threshold BLS signature so how do we get rid of The Trusted third party well we threshold ISE this master secret key and everything else works perfectly right still I need to get a signature on my identifier so I don't want to be revealing that identifier to the system again how do I get a signature on a message that I keep secret we also have a a cryptographic name for these things these are blind signatures so we can use blind BLS sign

signatures and a proof of knowledge that you do own the identifier and that you do know the identifier that was blinded to effectively hide your identity um sorry let me go back this means that we fully get rid of The Trusted third party we instead have a signing committee and this committee learns nothing about who you are lovely so now users can get their private key they can use this private key to get a shared Secret how do they exchange a message without being detected and that's what we're calling uh unlinkable handshake I think there are a few different names going around for this thing it's not really defined

um so we have our shared secrets we can use that to derive a bunch of random things including an encryption key like a symmetric encryption key some tag that we're going to use to identify our Cipher text and we can encrypt whatever message we wanted to send so remember in this case the message is my new identity on this new network and then we can publish this tag and CER text onto a public bulletin board the tag is is sort of pseudo random so you can distinguish it from something random the cipher text is also pseo random if we're assuming that we're in the ideal Cipher model which is very close to the random Oracle model in fact

they're equivalent and so this is what the bulletin board would look like just a bunch of tags Associated to Cipher texts and to an external Observer this means nothing but to someone who knows a tag Cipher text pair they know that this is a message from one of their friends so to read a message from a friend I just go up to the bulletin board I also derive the symmetric key and the tag I take down whatever I need and I can decrypt one thing that could leak a link between people is access patterns to this bulletin board so we do require that every right and every read is

performed through an an anonymity Network so you could use Tor right and a new identity every time you go and read and that's kind of it we now have this four-stage process where first in the setup users obtain shares of their private key from these Discovery nodes and although this is drawn as like you know one entity this is actually a committee of signers I should also uh mention that this Committee of signers we can set the threshold to be whatever we want it doesn't have to be onest majority it could be like N Out of n if we wanted it to be uh there is a usability trade-off obviously because users will have to query at least the threshold so that's step one setup you

get your private key in this way you reconstruct the private key locally then you can do the key exchange which is one pairing per friend and then you simply use this key to derive um an encryption key and a sort of identifying tag great so what else can we do I've been talking about the context of contact Discovery but in fact what we've built here allows us to secretly exchange an arbitrary message with someone I know so you could send like a transaction through this a pre-authorized action and you're effectively by doing this paying a friend who hasn't even

signed up to a system but who does have some kind of ID that you know their phone number their email so this is actually a great onboarding mechanism um you can maybe use this as an airdrop where you send these transactions and people don't have to claim and go and see you and be like hey please give me my airdrop the transaction is already there for them to pick up and again it's a very similar logic to the onboarding logic and in fact this idea of using identity based encryption to pay someone based on their identity um is also used in this UT paper um which I've linked here another angle is maybe in games you could have games where teams are set up

at the beginning and teams have to remain secret for some reason say you're playing mafia or werewolf um this could be a way maybe game developers let's see um to have players establish contact within their team without revealing who is in what team if you have other ideas please do get in touch uh because yeah we'd be very happy to collaborate quick words of warning what not to do do not use this as your main Communication channel this is slow you you have to send messages to this message board through tour and then download them through tour you don't get push notifications either you have to go

and check for messages so this is not great as a Communication channel it's great to exchange a first message with someone you would otherwise never be able to communicate with what else you shouldn't do is do not set important private information through this um this isn't as secure as other means of communication in the sense that you don't have forward secrecy so with signal there's a key rotation mechanism which means if your old Keys get compromised your new messages are fine with this it's not the case if the master secret key or the shares get compromised if your key gets compromised or if your friend's key gets compromised your messages will be leaked so don't send private Keys um but

instead do send addresses public Keys ephemeral Secrets things that will allow you to bootstrap a secure forward secret Channel with that a few references and some concluding remarks which is that we saw what contact Discovery is we discuss related work and we saw our construction that uses this identity based encryption and the handshake in the paper we do a lot more and we explain how to build this bulletin board you could use a blockchain you can use way cheaper um consensus mechanisms and in fact fully avoid consensus we also talk practical considerations like Access Control to

um The Message Board spam prevention how to verify that you're getting the right Keys all that is in the paper we have the all important security proofs of course and we have experiments we run this for a few days uh over 10 geod distributed locations um and it's quite fast and we think it can actually sustain um the traffic of something like whatsa that's it for me thank you very much okay great thank you very much um we'll move on to any questions y we've got a hand up over there so there are mics on the seats if you could just grab that and just press on little button um and uh

far away are our Q&A mics on hold on don't worry I'll run one to you it's always the tech right it's always a t is that one working there you go have M thank you uh Nico what a great talk what a great project thanks a lot really nice slides really really cool really cool work uh I had a question about two things so the first thing was you said there's some cons and that the users have to do all of this work but it seems like the application can do it for the users behind their back really easily is that fair to say that is fair to say yes so if you integrated this in signal from the user perspective I think it's

totally fine that doesn't seem like a big con right with the difference that your phone is not going to consume a lot more power right whereas you would send so the way signal does it is you send your contacts into a te so you send it and the workload is done remotely here you'd have to compute one pairing per friend you'd have to derive these Keys send messages um and your yeah your client side app would have to constantly sort of check for new messages on the message board mhm I see okay good to understand and those overheads and at some point when you talked about the blind threshold signing protocol you said that you would want the proof of ownership of the ID which kind of hints to me that you might need to employ a general purpose snark to you

know reveal the pre-image of that arbitrary hash function right that's correct yeah and in what type of applications do you think you would need to prove ownership like a signal such an application so the blind signature has this weird thing that if you want your security proof to pass you suddenly needs some part of your system to know the identifier not just the hash but not just the hash the actual identifier and the way we got around that is by having a proof of knowledge so that we can have these extractors get the ID and then use that within our reduction but I thought for BLS blind you can prove security without such a you can but I'm not sure you can show essentially we're trying to avoid

impersonation attacks I shouldn't be able to go up to the signing committee with your identifier ask for signatures ask for signatures and get your private key so I need to somehow show that the identifier that's blinded corresponds to the identifier in my proof of knowledge sorry my proof of ownership of an identifier right okay that makes sense yeah lovely thank you any more questions oh yeah one at the back do you want to test your mic that might work yes it does great thank you very much for the talk pleasure the bulletin board um it seems like the growth of the number of entries there is quadratic in

the number of users or in the number of something um how big does that get in your experiment say or in your projections so this is part of the Practical considerations that I was talking about at the end that we don't talk about here we break up the bulletin board into Epoch of say like one week and at the end of each Epoch we can clean out um entries that have been used actually we clean out everything and then users have to re-upload but yes you have to sort of manage this because otherwise it would grow kind of endlessly yeah if I may follow up um so that means if I'm still looking for some friends who I do not know whether they

have onboarded yet and I just re-upload all of my contact list basically and everybody does this then the cleaning out only helps somewhat question mark you yeah kind of you'd hope firstly that people don't have crazy number of contacts um and secondly that yeah a lot of them will be signed up already so you don't need to query them again thank you great lovely maybe we have time for one more quick question if there are any more Hello um uh if anyone have uh access to Bow up the public is share in the in the database and another one in the bullet and if they monitor all of

the data share by the users are there any way if they can re identifies who publish the data uh no and that's sort of the the Crux of the security proofs is that all this traffic all these transcripts that we post onto the bullettin board are indistinguishable from random even if you've observed um yeah the set of public Keys even if you've observed a bunch of shared uh keys and even if you have like as many users as you want like you can control as many users as you want as an adversary it you still want to learn about what's happening on the bulletin board yes thank you great lovely we'll um stop it there but obviously Nico is

around if you have any more questions thank you very much Nico great talk