Anonymous Credentials and Decentralizing ID Systems with Foteini Baldimtsi | a16z crypto research

Transcript

this morning we're going to have the the second talk of the two this week about fatini bar mitzi who's one of our summer faculty fellows and professor at george mason all yours all right thank you tim um so the plan for today is to talk about anonymous credenzas and uh i'm gonna spend most of my talk actually giving you the background on the on the space and explaining how anonymous dancers and anonymous authentication used to work in the past and then towards the end of the talk i'm going to kind of modernize things a little bit and discuss how decentralization can can help in the space so um let me start for a second and have you all think

about how many online electronic transactions or like digital transactions we now do um we use like the metrocard from the office every day we use cryptocurrencies we use services like netflix social media online storage services and so on and let's think for a second um how much personal information do we take through all these services that we use okay and also pause back and think how much information would you like if you were paying for all these services with for example physical coins um or if you were not authenticating before accessing any of these searches so the amount of information that we is

allowed and even if we don't think that we're actually looking information that can identify us this is very often wrong there have been studies that actually saw that a very large large percentage of the population can be uniquely identified by having three unique attributes like date of birth gender and zinc so towards this end there have been quite some policy discussions the last few years and how can we actually minimize the data that we provide online both in the european union but also in the u.s mostly in certain states i would say the main principle for these guidelines is that the collection of personal data should

remain the absolute minimum that we need for whatever service we're using so the question that we're trying to answer here is you know if we want to retain our privacy does this mean that we have to stop all these very convenient and nice electronic transactions and the answer is no luckily we have a lot of research and many cryptographic techniques in the space that can help us with that we can use privacy preserving protocols and the main focus of today's talk and i think a core focus for um for anonymity digital transactions is that of authentication because if you think about it mostly most of the information that we are telling it

happens at the point that we authenticate in order to access the service so what is our goal here so let me start stating what we want by anonymous authentication so ideally we want to have users that have digital credentials that is the whole bunch of attributes like their name date of birth address boundary maybe some unique id number we want these credentials to be issued by some sort of legitimate is here you could think for example as this being like the state identity um from of alex and

then what we ideally want is to use this credential to use this information in a completely privacy preserving market so let's think for a second what happens um when people go to buy liquor today right so you walk into a store like visiting actually you walk into a store and you saw your identity card and the information that you made is so much more than what they need to know so what they need to know is basically that you're over 21 years old it doesn't matter if you're 22 or if you're 55. it doesn't matter what's your name what's your address or any of these uh or anything so ideally when we're building towards private analysis authentication we should aim for the you

know for for the best privacy that we can get and the ideal goal here is that we should just literally be proving statements about our attributes that reveal the minimum amount of information that is needed for any current type of transaction so for example here just that the aids that is embedded in this credential is always going to be 21 years old another crucial property property that we want from such digital credentials is that we want the issuers of the credential to be unable to trace the transactions of the user so this is not as easy in the physical world so the state of new york it's it would be very hard to try to trace you

where exactly you physically saw your your state's id but in the digital world if you just think of this like this as being you know like a series of beats it's much easier to actually trace where this information is being used so an ultimate goal of a non-instrumental and anonymous authentication is that whenever a user is using their credential and this might mean that they either might you know literally solve the credential as it is or so certain predicates compute certain proofs on top of the attributes of the credential this sewing process would be unlimitable to the issuing process to the issuance process so if the verifier colludes here with the credential issuer they shouldn't be able to figure out who was

the user that's all this this group additionally even if the credential user creates more proofs to access other services as well even if the proofs are on the same attributes and here i'm you know conveniently bringing up an attribute that's not unique because if it was like the id number then maybe there is like an obvious uniqueness property there um that should also be on the intel okay so this proof should not be incoming to this proof no matter who colludes no matter who gets access to these like verifiers issuers nobody should be able to do this again are the goals clear good so if you think about it and you know if

you ever took like a crypto class you might already start thinking how can we achieve these properties by known uh cryptographic tools and if you again think of what are the properties that we want here we want credentials to be issued in a way that obviously this should not be forged that's not just be able to create fake credentials and then if i want to do like proofs using some sort of privacy it might become pretty clear to you that we might be able to construct some certain generic constructions using digital signatures for the instruments of the credential and then zero knowledge proofs for the credentials showing the problem with this approach although it technically works is that it's not really efficient okay so this if you just try to

randomly combine different types of schemes together um you're not going to come up with the most efficient constructions and in certain cases of authentication you actually really really care about efficiency so you should be able to access the service and issue proof in like milliseconds even seconds are not acceptable okay so we literally think of entering the subway right imagine if everyone would have to sit in front of the um of the end drums and take like 30 seconds when okay this is yeah so basically we can just create a fresh zero knowledge proof for everything that you do for every statement that you saw and they don't

get these proofs and not kind of really randomizable you can you can yeah so do you have any concrete numbers like how slow it might be to use a generic ckp like let's say yeah that's that's a good point um i don't have concrete numbers and nobody has as far as i know this might make like a nice i don't know student project um but even if my my understanding is that even verification you know could not maybe it's not that bad still computing the the proof itself uh with you know any sort of these like genetic proofs it's gonna be pretty angry again we're talking about

it many seconds here why does the proof generation need to be that fast if you can kind of like pre-compute it that's a very good point uh so you might not always be able to pre-compute it so it might be the case that actually the authentication process is an interactive protocol um with the you know with the entity that you want to authenticate you might not know ahead of time what kind of attribute exactly they're going to ask for it might be time specific again like for the subway it might have to be tied to the exact time that you're entering the subway because maybe the charging policy has to do with how many hours you're using the train so there are many many parameters that generically you cannot say that precomputation is acceptable there's also issues with difference between time of use and time of check or

time of issuing some time to check right so um i imagine that would be even more crucial here with the anatomy anonymity right right so absolutely together there can be a issue so the reason for you know uh the reason that such generic constructions um are not efficient as i said is if you just like plugging things together kind of randomly it's very very hard to make them compose well and nicely and very efficiently and this is the reason that we actually have um over over i think at this point like 30 years of research on the subject of anonymous condensers which basically means that how can we build specific cryptographic primitives for this very particular problem so very tailored and

very very efficient so when we think about anonymous credentials i like to kind of speak them in two categories um the so-called multi-use anonymous credentials that are based on general signatures i would say well with certain properties in some cases and zero knowledge groups and the so-called single-use anonymous credentials which are almost exclusively based on a special type of signatures called the blind signal tool and potentially xenons proofs depending on what you're trying to solve here and as i said there is a very very long line of research i'm not exhausted by any means here starting back in the 80s uh at the same time there have been

quite a few efforts to actually commercialize to implement to implement those protocols by microsoft um ibm and microsoft consortium under european projects that later kind of spilled over hyperledger envy and even signal these days actually uses anonymous credentials techniques for authenticating users in groups when they're doing their messaging so what is the difference between the two and um you know what what do we prefer in its case so the idea of a multi-use credential is that i get a credential issued once from the issue so i interact with actually once i get one object and then i can reuse this object multiple times

in order to authenticate so naturally multi-use condensers make sense in subscription services or if i actually want to digitize my state id or my password single-use credentials are credentials that are literally issued and can only be used once and as a matter of fact if you use them twice you might actually use brightness okay so you might be absolutely ah i'll be cleaning them together however there are certain cases where single-use conventions is what we need so for example you might want to use some sort of like single-use coupon um you might want to issue you might you're using this type of credentials if you want to build like a new voting scheme where you have to you need to

have like a download that you can only use once and also simply use credentials um naturally give what um it's called or what we used to call in the in the space before blockchain against electronic gas so they would naturally give this coin that we can only use once the caveat here is that single-use condensers are actually much more efficient and this is going to become apparent because the main idea is that you get a credential issued you get a signature and then during presentation depending of course on what kind of statement you're proving you might not even need to do a zero knowledge proof you might just literally saw a signature and presentations just literally means

signature verification and done so you're not verifying the proof it is later it's verifying the signature and maybe the prover needs to do absolutely nothing to say that i represent the signals so i would even argue that in certain cases that you know that you're not going to use a credential many times so let's say that i know that i'm only going to use a condenser like two or three times it might actually make sense to issue three single-use credentials instead of getting one mouth i use previously so it might actually be more easy so let me start the discussion with single-use credentials because i think that absolutely the techniques are pretty interesting here and they were first introduced back in the

90s and um as i said the core primitive is a special type of blitz type signatures are called blind signatures and for those of you that were here on tuesday you might got bored hearing me talking about all these different types of signature schemes but i saved one for you today they didn't cover on tuesday blind signatures i could have easily put that on tuesday as well because they are used in certain one three layers to mostly applications but i wanted to to say one more signature for you so the core primitive is a behind signature and i also think it's a very interesting type of signatures and they want to explain to you how they look so um when brands stephan brans defines single-use credentials they and he used an elliptical based

blind signature that was three rounds and uh the problem with that scheme was that and again thing that were back in the 90s people do not really have so formal security models definitions um so they're not they don't care about security proof so much so the problem was that no security proof was given and um the interesting part here is that microsoft conveyor digital identities product you prove background was actually adopting this signature scheme so when i started working as a phd student one of the first tasks that my advisor assigned to me was to actually improve security of this scheme she was like well people are talking about this game for so many years it doesn't have a proof security so you know i i was trying really hard and that was

failing and at some point we actually came to a realization that um it was kind of impossible to do this institute so again we didn't find an attack we essentially came up with an impossibility result we ruled out in a sense a number of techniques that one could use to prove the scheme secure for the cryptographers and then we did that using a technique that's called the meta reduction so we said that if there is a way to prove the skin secure then you can break a heart problem okay so um again this is not an attack we're not saying that this game is not secure but this is certainly an issue right we're not as cryptographers we're not so happy to implement and use schemes for which

security is unclear the better reduction was for proving security in a particular way or we were i don't think that the way that it works we're pretty much like ruling out many ways so it's not like one particular way but uh um yeah yeah yeah so we're wearing out like we were even saying our meta reduction says that even if you assume that the scheme itself is secure you still cannot prove it secure which is kind of funny yeah so with the reductions i think you know we've seen meta reductions for different primitives in in twitter the last

like these sort of impossibilities reductions for different companies in the last years and something that i should also note here is that actually blind signatures are a type of signature scheme that is notoriously hard to prove and there are many many there are many subtle details when trying to prove security and i'm going to come back to this topic soon and after we realized actually that this scheme was not um was not secure well not wasn't secure it was not probably secure uh we actually came up with a scheme with very similar efficiency um that we could actually um production so let me give you a high level idea of how blind signatures work and how we can get anonymous to themselves from blind

signatures so the idea of a blind signature is kind of untraditional to the regular signatures that we have a user that has a document and has the signing keys and assigns the document uh instead you can think of a blind signature as a two-party protocol you have a user that has a document and then the sign there is a different editing so what is the goal the goal is that ice wants to get a signature on your document from the signer while hiding the message from designer while having comfortability so i should not be able to compute signatures that verify in the designer's public key alone and at the same time we also want any ability which basically says that if the signer at the end of the signing process sees the final signature it cannot link

that it cannot connect that to the signing process so it doesn't know that this is a signature that was issued to artists so um in the universe the idea is that alice can take the document put it in a box lock the box and you can think of this as being some sort of a cryptographic commitment here so i can commit to that had some secret randomness that was used for the commitment send this committed document this hidden document to the signer the signer using its secret key is going to compute a signature that they call sigma star on top of these hidden lessons send the sigma star back to ice and then alice using sigma star and the randomness that's

used in order to hide the message can actually unblind the signature to a signature sigma that will verify under the signage public key for the original document not for the commitment so we need a minimum of two rounds for some client signature protocols and i hope that this becomes clear because the user needs to send something to the signer before the signing process starts and uh the efficient protocols that we have in the space are actually three rounds okay so we have some constructions in two rounds that are not as efficient as we want here so now um again the important part is that

obviously eyes cannot create signatures himself but also if the signer sees the signature sigma and this document they cannot change it to the signature sigma star that they created here they look like two completely different signatures so how can we use the signatures now as a means of anonymous authentication so let's say that ice wants to provide this credential to some very fire you could think for example this has been some sort of token thing i don't think the uber codes that clear census whenever we go out one night um so we have this like one-time token we want to use it with some verifier uber let's say um so what we can do is that we can

literally just present the signature and the message that says this is one free ride and the verifier will just verify that the signature verifies under the sinus public key and again the nice property here is that even if the verifying designer colludes so even if claire colludes with uber they shouldn't be able to find out um how we travel how it's user used um like one time coupon there one time called okay so to do the unwinding you need to know both like the original document and the randomness yeah so you needed to know the original document because this the signal should be very fun for some document and you typically need to know how you blind

this so basically again in a very high level way you're blinding the document so the signature is also kind of blind under the same randomness and then you somehow kind of divide out this randomness and you have like both the unplanned methods and the unblinded signature in a very high level so something that we have to be careful about here is what happens if um the user is racist and tries to reuse the same one-time token so here the problem is that uh ideally what should happen is that the verifier should be able to reject this token because it has been already used

and unfortunately the only way to do that is to literally maintain a list of all the used credentials of all the contentions that we've seen and make sure that this doesn't appear there okay so there are certain techniques to avoid holding this list that you know might become very large you might have expiration dates in the credentials so you might have you know like credentials that only last for a week or a day or a few hours so that you don't really need to hold anything that has expired so the way that i present it credentials this hexane get used to themselves so far i didn't talk about attributes at all and this was something that we really cared about i just said you have to say a quantum token that you

literally just want to sow it and that's why i said that at this point this was super super efficient you see like during sewing they use it with absolutely nothing like zero computation literally just presented a signature they verified the signature that was it well if you start one if you start adding more complexity in the system now if you start tapping attributes things will also naturally become a little bit more complicated both during the issuance process but also during the verification process so now think that in this like one-time talking we also want to add attributes for the user so who might want to add i don't know like the secret key hidden there the name the date on third or something like that

so the idea here is that so now that the message might become more complicated or in certain cases you could actually think of the attributes as being like a second message concatenated with a message that you're actually signing so maybe a simple way to think about this is either i think of this as like coins digital coins think of the methods as a unique serial number and then think that you're also touching the band of attributes why is this useful if you use these coins let's say to enter the subway you might be able to solve that you get like a senior discount because your age is over i don't know 60 whatever it should be um and uh you might want to actually have this like more rich credentials that have

more information even if they're single-use ones so the idea there is that you can start by committing to your attributes potentially you might need to include the zero knowledge proof that whatever you committed into here is correct and in certain cases you might need some sort of physical means to do that so you might later i need to show like a physical identity to prove to the issue that yeah like whatever i'm putting in the commitment are you know my true uh my two attributes and then uh the challenges now are you want to create a blind signature on some message that also includes the commitment

if you just later i signed the commitment this is gonna get problematic why because we cannot just rely on the user to randomize the commitment because maybe the user will randomize the commitment in an anonymous in a malicious way and that different attributes from the ones that actually designer verified that are correct so if we just consider c as the message that we had before and allow the user to hide it who guarantees that the user is just not putting different things in there okay if it's completely hidden from the issue so the science here is to actually create a blind signature scheme such that the user designer joined the random ic in a way that the final signature will be on a c

on a commitment that the signer doesn't know but at the same time the user cannot change the committed attributes so to achieve that we define the variation of blind signatures that we call blind signals with attributes and things there get quite more complicated but sorry show you how it works but again like the higher level idea is this joint um randomization of the commitment in order to issue the signals so at the end what alex gets is a credential sigma a signature on a randomization of the commitment c on the attributes c prime such that

it was created in a way that it guarantees that are the same attributes included as the ones here that the signer verified but also in the way that um guarantees and ability with the c that the signer knows for this commitment for this user and if you think about it um you could literally think of this phase as being some sort of like a one-time registration phase so if you think of this as ecas you can think of the issue as being the bank that you register once so your full credentials open your account and whenever you go to your bank to get one-time tokens one-time coins you just run this page so you basically keep on

re-randomizing these commitments okay and potentially the bank you know will be crossing out coins from your account does this make sense i know that these are quite complex ideas if you've never heard the work then yeah is it easy to say in a sentence or two a little bit more with like jointly randomized means so literally what happens here is that again think of these are like three-round protocols so the assignment starts by randomizing the commitment if these are tenders and commitments for those that they know that they're based on like the

screen clock uh literally the the designer can pick some random and put it on the exponent um of the commitment and then this is sent to the user the user is going to add some additional rank elements uh the point there is again that you want to make sure that the user is randomizing whatever it got from the signer and not something new so the signature will only go through if the this the the committed message is the randomization of what the designer commuted so it might not know what was the second randomness factor used by the user but it has to guarantee that it's just like adding extra randomness or

whatever the signer started with because again if if we allow the user to completely randomize things and do whatever they want they might just put different attributes there that they're not find so it's actually it's pretty tricky i mean this again for the cryptographers i guess in the room this blind signature schemes in the sense work as an our proof um so the sign the user is well the sign is actually either proving that knows the secret key or that knows this like randomization so it's a bit it's they're kind of um pretty involved so on top of the properties that i was mentioning before like unfortunate unlinkability uh obviously what you want here is that when you open if you open

these credentials you shouldn't be able these commitments shouldn't be able to open with different technologies so here when you're using these now tokens this um one-time credentials with attributes when you present them if you just want to present them as a one-time token i have like this one-time axis again as before you might just literally reveal the signature on the messenger c prime and or if you need to do some sort of parsing partial opening the nice thing about this commitment is that there is a very easy and efficient way to just open one of the attributes so just all the aids and nothing else um or if you don't even say want to sell

the aids that saw some sort of predicate like my age is over 21 years old add some sort of zero knowledge proof on top of that okay so having that of course like you cannot avoid the zero improve here if you want to do something more complicated some more complicated um again the properties should be that these are unlimitable so no matter how many accounts designer controls no many no matter how many commitments designer knows and how many tokens it has creatives it shouldn't be able to link any presentation with credentials and of course like you should we should be like mindful about privacy here so if an issuer has a single

user that is over 90 years old then obviously they can be anonymized right so you should always think that the level of phenomena that we get here is some sort of set anonymity on other people that have the same or similar sets of attributes as you so as i said we came up with this nice scheme that we call it anonymous cadence's life and it kind of stayed the state of the art for many many years um the scheme is besides getting this like three rounds it is based on olympic cares um it's relatively efficient uh it just has like it's this critical base it only has like a number of exponentiations uh but the thing that i want to highlight here again as a cryptographer is that

the security proof that we had for the enforceability of the scheme it was only um working in the so-called sequential setting so we're saying that the scheme is unfortunate it's impossible for an attacker to force groups as long as the issuer was issuing one proof at a time and again remember that these are interactive protocols so if you think of the issue as being some sort of you know server in real life you might actually want it to have multiple signing sessions open with multiple users but we didn't manage to prove security and the parallel composition we left that as an open problem so almost 10 years later um we actually had them back okay so there was a um

a very nice um a very nice paper that came up and said that many blind signature schemes mostly discrete cloud-based are not well actually yes mostly display-based are not secure on their parallel composition and the pilotations so this was a concrete attack this is not some sort of impossibility result it literally said that if there is over threshold of open um issuance sessions then we can actually forge signatures okay so um this was pretty annoying so yeah consider the existing signature schemes considered just naive naive parallel composition

it was not naive that the technique was you know actually using some like math uh but um so they later i showed an attack that said that if you have multiple issues um sessions open so if you started interacting with multiple users for multiple messages uh if you so think of this of some sort of like linear composition so some sort of like linear equations if you combine all the information that you know from all the open signing sessions uh combining all them together allows you to create a forged signature for something else so it's not even like you need them to be proceeding in two holes like back and forth it's a block step this lockstep no no you can pull the information from all of

them right so if you're if you're like a network attacker that you're observing what's happening and you have your call this sessions open and again i mean you need like enough sessions to be open but again the parameters will depend on every particular scheme um but yeah you could like some sort of binary compose all the information that you have and um manage your phones and they can listen just like any possibility thing they didn't just say that security is impossible in the parallel setting they actually saw the attack okay this didn't violate anything with our proof for example or other proofs because our proof was only in the sequential setting we never tamed the security in the parallel setting um but this is something that actually you know raises concerns about how to use the

schemes so how did you use the facts how does the proof use the sequentiality like is there some way that like one signature it depends on the result of the previous one no no so so basically so again the reason that this attack works is that um so these protocols are usually three rounds so they they use the first two rounds of every open session not the third one in order to conclude to a third one like a closing one that works um so if you do sequence if you close every single session before you move to the next one then you're not able to do that but if you are able to interact with designer in a way that you can mold things by using other open sessions

at the same time then you can come up with a forza is it a semantic security issue are you using like some sort of uh because you're talking about aggregating it and are you doing like pattern analysis on it or no no it's actually um it's a mathematic based attack it's called the rose problem um i can i can give it it's pretty technical i can you more about it and again it doesn't only affect that particular scheme it affects many blind signature schemes and as i said before it's like improving security of this behind signature screens it's actually extremely hard it's uh i it has a very very particular techniques do you break the

zero knowledge or you break the there are multiple parts so you break them for the baby required right so that you cannot avoid if you want to do more complicated protocols here still there are structures in signature elements that compose bacterial wars with zero knowledgeables so the partial opening is a revealing

age good yes so if you literally want to evaluate and not so some predicate over your aids actually you can do that very very efficiently so no need for zero knowledge proofs we just very very efficiently can open part of the commitment and if you want to produce something more complicated some sort of arranged proof for example in your age that you're between some reigns or over some some threshold this is where you would actually have to do zero but again just literally opening one predicate it's very very efficient so in practice actually when people consider these single use credentials they will try to avoid zero knowledge proofs so they would literally for example you know for the senior discount on the subway that i mentioned before they

would model this as a binary attribute zero one so you would literally just open and not do any sort of signals but again this is very application specific are you going to talk about how to make it concurrently composable i guess it's like directly about how to do that uh actually i'm not i don't have slides we have some work in progress on that it's not complete so i cannot claim that we've done it yet uh what we know is that there have been some medicine works um i believe europe 2022 that gave some efficient um blind signature schemes using the agm model it's by stefano cesaro that are parallel secure that avoid this

attack however they do not support attributes they don't allow you to do this like double-sided randomization of the commitment so we currently have some work on that but as i said it's not complete so that again okay so the main challenge is to make it efficient i guess theoretically yes right so we do have blind signature schemes that are not do not suffer from this attack they're in the standard model but they're not office so um we don't have like the script log base around the molecule based efficiently well we have this very decent work as i said like europa 2022 but again it doesn't support attributes so it's not direct so it's not directed

you can just take any blind signature scheme we don't have any sort of generic compiler to compile any blind signature scheme to a blind signature scheme without reviews so this like joint randomization of the messages being signed it kind of needs to be embedded on how its protocol works so we don't know how to do that genetically i guess like if you know it about efficiency you can just use like uh yeah yeah i mean completely solve this problem by just taking decision proof and and the signature scheme but here we want to avoid xenonscripts completely yes so when you say efficient is that like how do you just mean less exponentiation just like a technical

definition of what's efficient yeah i don't have a technical definition but uh yeah so we basically um yeah we just want like a few expectations or a few point multiplications or just a couple of pairing operations and also we want short sizes of all this stuff so um so this concludes my discussion on some videos credentials so this is a topic that i think it's actually open at this point we don't have an ideal single-use credential scheme with all these properties that i mentioned we have some work in progress talk to me offline if you want to hear more about what we're trying to do i'm happy i'm happy to explain um going back to the multi-use setting i'm gonna say

a few things here in the maths higher level in a much higher level so um the core primitive here for multi-use credentials uh where again a special type of signatures but not maybe as complicated as blind signatures and look like completely different definitions here um these are the comments this yamskaya signatures which are basically signatures and committed values that allow for efficient proofs of signature ownership so efficient xero knowledge proves on top of the signature so signature schemes tailored very very specifically for efficiency knowledge groups so the original series signatures were based on rsa so they were pretty large and they had some expensive operations

later works gave signatures with similar properties that are based on ethicals and diana pairings so for those of you that know things in the space this is what we usually call the bbs class signature so again signature with similar properties but more efficient so the idea of this multi-use credentials is more similar to the generic constructions that was mentioned before you have a commitment to your attributes you start with again some sort of phase that you have to prove that what you have is correct all these credential systems need some sort of bootstrapping you need some point of you know actual truth on how to start um and then you get one of these special

signature schemes that allow facing zero knowledge proofs the the high level ideas that you're able to randomize the signature schemes multiple times if you just want to solve the credential without uh proving anything about your attributes literally you just need some sort of um randomization that's still more expensive than single-use credentials that you just literally saw the credentials you do zero but you do nothing you literally solve a signature here you have to keep on randomizing them because you want to maintain and incapability designer no matter how many times you use the signature they should not be linkable and um as i said you can repeat that multiple times for the case of multi-use policies there has been

again like a lot a lot of research in the space and many extensions here for example things like conditional anonymity you can identify misbehaving parties and their well-defined conditions um revocable anonymity how can you using some sort of third party or threshold techniques can you figure out who was the user how can you dedicate these credentials i have a credential i'm going to be on vacation can i dedicate it to one of my employees for example how can you use consistent pseudomeans across different services there have been certain optimizations in the case that the issue if you know that in a specific setting they should verify

the same entity you can actually have much more efficient schemes um and there have also been schemes that actually use um transit enclaves to optimize certain things and get some additional thoughts yes um is there are there ways to do non-repudiation without revealing the identity here or so uh without revealing the identity one of the applications would be non-remediation right if someone's trying to claim that they didn't assert something yeah yeah so right but the challenge is always there uh how can we do that without just relying on the third party that has a tractor to just open up the identities of users

so i guess like the first two bullets are kind of connected right so in one hand maybe you want some sort of um specific policy that automatically is going to revoke anonymity without the involvement of a third party well in the second case you might actually involve some factors some threshold some committee of thoughts um so you mentioned a revocable analytic what about just not you don't want to revoke some of that anybody you just don't want their credential to work anymore yes revocation is a very important problem and it's uh it's actually one of the things that makes you know these defenses pretty

pretty hard so the vocational credential invocation is a hard problem even in the non-anonymous set okay so how can we like just think of like certificates um like fearless duplicates right how can we make sure what has been revoked and what not and even like specifically again for the case of tl certificates our solutions are not great are not completely online uh it takes time to figure out what are the acceptance and vocalists at any point so um and there is a lot of visits in the space as well so when you're adding privacy in the picture everything becomes even more complicated okay so um i had actually planned to show you exactly how revocation works but i think i'm gonna

skip it so that i try to keep them i mean i say a few things but i don't so i will not show you the exact solution so that i try to keep the talk in one hour and if we want to stay longer just to discuss the vocation we can do that at the end so again the high level of credential evocation is that you might have like an accept list of credentials for some basic here and just literally throwing the names of the of the users but you could think of this as being credential this and if you literally just skip like a list um it's super easy to add these concentrations especially if they're under under central management but the problem is that the size of the series is getting near to the number of users that you have there the number of

credentials that you list and it's very very hard to support user privacy so the most prominent solution in my opinion for efficient revocation is a special type of cryptographic data structure i would call it that's called accumulators and cryptographic accumulators are basically a way to compute a very short digest of a large amount of a large set that is actually constant to the number of elements that are included in the set and still be able to compute proofs of membership or non-membership that idea are constant in size so you could think of 33 is also being some sort of accumulator that the digest

of the set is just like the root of the methyl3 that's constant size but say the problem with at least metal crease is that the proofs of membership are not constant size their logarithm okay because they're like the paths so accumulators can actually offer trade-offs uh when compared to multi-trees uh to have and the most important one is that the proofs are of constant size so i'm not going to show you exactly how things work i have the example of the rsa accumulator emulator i just want to to mention a caveat of accumulators that um it's it's important the thing is that when you add an element to the accumulator um you have a way you receive some sort of sort proof sort of weakness that we can use

to as i said very efficiently proof membership or non-membership the problem though is that when more elements are added on the accumulator you have to update this proof so ah technically um in the older accumulator constructions you would have to update this weakness both when additions happen and when deletions happen from the accumulator but we have certain lower bounds and newer constructions that actually get season and you can manage to have accumulated constructions that only allow that only require you to update your weakness when deletions happen and not when when abuses happen so if you think that you know you're

storing credentials you could potentially think that it's more often to add new credentials than deleting ones and in that case these constructions um make more sense so we have a series of work on that uh again keep in mind that in these types of accumulators there is some sort of accumulator manager so there is some sort of third party that holds the humidity okay that is responsible to maintain that so in the last 10 minutes of the talk i want to switch gears a little bit and give you like a high level overview what happens in the centralized space by talking about digital condensers and anonymous digital credentials um and um

again i think that we see two types of approaches in the space the first one is to literally take anonymous to themselves as we used to know them in the past and decentralize parts of the process so the main part of the process that you want to decentralize is actually the issues process you don't have a single issue to vouch for themselves but you might want to have more the second approach is to kind of take pictures completely out of the picture or partially out of the picture and have users that create their own digital identifiers that they're not like central manners that attend porn so this blends well with what andre was

discussing yesterday about reputation systems so some sort of like a web of trust idea that people create their credentials and then they can get you know kind of some sort of distributed voucher credential but without having some sort of starting point with a specific issue so i'm just going to say a couple of things about what do we know in its case um so in the decentralized issues case of again like taking classic anonymous condensers and decentralizing them the idea is that you might want to have multiple issuers working together to issue a credential for a user one of the most prominent schemes is the coconut credential scheme where actually

sarah is one of the authors and is being used on the nim project so the idea is to use a threshold line signature so these condensers are actually kind of single use credentials um the nice thing is that you can necessarily you can threshold dyes the issues process you can start by having a system where you define a number of potential issues let's say n is years and then for every new credential required of the threshold difference say two of them sign the credential so the nice properties of threshold signatures and for those of you again that were on my talk on tuesday might already remember what are the the good

and the bad things about threshold signatures is that you get signer privacy so you're not going to when you see a credential you're not going to know who were the issuers that vouched for this credential you just know that this credential would bounce by enough is yours um but the problem is that the process of accepting up this set of issues is actually kind of annoying so in this threshold signature is going to be this distributed key generation process that needs to happen in order for them to agree on their initial keys and this is a non-flexible process if you want to add new issues or if you want to remove these years you have to re-run the whole process um also it's not very clear how to

efficiently add add attributes in those schemes um there are ways to add attributes you know in a by using different public keys and uh um kind of more like ad-hoc ways but they're not truly embedded in the system so in a word we actually have under progress um and again i'm happy to talk with people about this with uh colleagues from from umd and uh cispa uh we are trying to do to construct a similar scheme that instead of threshold signatures uses multi-signatures and remember that the main advantage of multi signatures is that they do not need this coordination among the issuers in order to um

to create the credential um they have other issues they're larger but and they also um reveal who are the issues where the um designers of its credential so this can be considered a feature in certain cases so you said that is going to secretively you might actually want to know exactly who votes for it but in other cases it you know it might also be considered like a privacy issue so it really depends on what what's the application here so the last thing that i want to mention let me just you know kind of open the floor for discussion and mention some sciences is the idea of decentralized identities so the main idea on this whole space is

that people want to change the way that we authenticate instead of using password authentication we want to use cryptographic keys like user wallets to be able to authenticate there are efforts like signing with ethereum um or um efforts like the thing we do decentralized identities which is again a research work that andrea is one of the authors he's related to i don't remember sorry and the idea there is that again it's not like taking traditional amongst credentials and trying to decentralize them it's mostly like i'm a user i have some information that i want to use in the space to start authenticating

they have some very very interesting ideas of how can you bootstrap um using articles like deco to transfer knowledge about your uh your keys your identities from other places um they have some nice accountability extensions um the level of privacy that these schemes offer are not to the point of anonymous credentials so if parties are colluding with each other you can actually anonymize users and also revocation is not again very efficiently if you want to do things in practice and again as i said the vocation is a crucial point here something that i want to mention now that i i mentioned revocation for the decentralized setting um remember that i said before that using these accumulators to do the

vocation the centralized setting uh assume that you had somebody that holds the accumulator you had like this accumulator mod if you try to decentralize that if you try to remove the accumulator manager and have a distributed accumulator then things become much more complicated and much more expensive so you actually need to hold the whole accumulated set to be able to compute groups so this is another like open research problem on how can we actually have efficient accumulators that are completely distributed um the practical applications of the decentralized identity like

are there any projects that are building some applications yeah so neem nim is building this idea of like thresholdizing anonymous credentials and i don't know about the status of canadian you know if you know andrew what's my confidence they have like some applications in mind yeah so so i think name actually cooperates with um certain parties in the european union i don't know you know governmental i guess um um they have some governmental access and they're trying to build some pilots for like european identities or whatever and yeah for canadian media yeah so i mean again

europe tried that before with this abc for trust system before the age of blockchains um i guess i really well or when blockchain was starting maybe like 12 13 years ago but they didn't do much after the pilot finished so i i cannot really predict what's gonna happen uh there but i kind of feel that we're getting more you know ready for that um also in this space um neem and coconut we're actually also using smart contracts for these threshold diesel issuance of the credentials so that will literally run basically yes there's a question so one is i mean yeah so um so i think that like part of

their system is actually building these digital credentials uh and then they're using mixing techniques um you know it's like i think it's kind of like two different components there so for the issues with like the accumulators open problems that you mentioned i mean are these also things that are straightforward with generic zero knowledge proofs but it's the open problem to make them efficient or is it difficult so you mean if i don't use an accumulator and literally just use like a list of stuff i guess so or something yeah so this yeah so this would i mean i guess zero knowledge proofs on top of accumulators kind of a second step as well so when you think about accumulators you don't necessarily need to think about

privacy preserving proofs of membership but what i'm saying is that even in the non-private setting even if you just literally want to show non-privacy that the credential is revoked or not is in the list or not in the distributed setting we don't have great construction so far okay even with generic it's verifiable computing would be the appropriate wow efficient practical construction genetic techniques do you mean that any of these parties can issue and you don't want to reveal who they are right so yes so so what you want to do is you want to get a credential that was issued by many of these issuers

at least a threshold of them without knowing who they are is it do you think um you know either maybe do you think maybe we can actually use the adventure of some sort of multiple yeah that's what we're doing right now yeah we're using it we're trying to use it multiple signals well i'm not sure what you mean by multiple though oh no i meant more like you know we know that say i have two provers and i know that they don't like my assumptions that they don't collude then you mean issuers of the credential or i mean in my mind these are the issues and this is the prover the user that has the credentials okay

um [Music] yeah so some final thoughts again generic solutions exist for most of the problems that i'm raising efficiency is a big challenge think that many of these applications are really time sensitive you want literally milliseconds or microseconds you might want to implement such things in the iq devices not even smartphones if such things are implemented on the block saying like this insurance process or these credentials of these proofs are stored on the blockchain you really care about sizes storage or gas costs if these are around through a smart contract there is a bootstrapping problem of course um and can i be had some ideas on how to uh to start there um there is a big problem for

contability which is a general problem with total privacy preserving techniques so privacy is great but we need some sort of accountability if we want this technique to actually be adopted um there is the problem of how can we do backup how can we do identity restoration particularly in the distributed setting if there's no traffic party to help us revocation is a big problem in my opinion it gets if it gets so expensive to prove that your credential was not evolved it starts getting annoying and i want to claim that basically post quantum secure solutions are non-existent again like efficiently and satisfying the goals that we have so that's again a very open space um so i got a question about kind of like the concept of anonymity that we

were talking about here so it seems like most of it was on the actual like message content or i guess the yeah the message that's being passed back and forth right but um wouldn't you also need some sort of obvious routing or some kind of mixed network or something right if you were able to see activity just so you mean like a network level yeah yes absolutely yeah so i completely let that network level out of here but you're absolutely right that you know even if i'm hiding all my cryptographic keys and cryptographic information if i'm using like consistent ip then of course like there can be like networking and have you

looked at anything like uh autonomic identifier systems so you were mentioning like the uh like the self-issued identity right so there's techniques where you can actually cryptographically issue like your own identifier without even anchoring it to like a blockchain or something right so yeah um creating like delegated versions of those that are just like ephemeral would that address some of the issues potentially like from like a setup i guess right but but again like you need some sort of bootstrapping you need some some point to start right so after you have this bootstrapping after you you know you start by getting some some real life truth that these are your correct attributes and you get your first credential then you can really play along you can like delegate things

you can get additional anonymous credentials on top of your already existing credentials that are unbelievable with each other you can kind of keep on building on your digital identity but there has to be some sort of bootstrapping and uh i mean to my mind this is pretty natural right somebody needs to literally verify your identity at some point again if it's like just a secret key for example ethereum and what you just need to know is that i have a key i have an account it's different right but if you want to start having physical attributes then you need something where you need some entities and fast attendees are there like scenarios where just a time-out based revocation works

because it's kind of like i guess yeah absolutely yeah so you could yeah and that's something that i mentioned for example so this is more easy i guess to doing this one-time credentials um because you know they have like they can have very short expiration dates so you don't even need to develop them basically for this consistent multi-use credentials it's um kind of harder to have experience i mean you might have still but it's kind of hard because you start building on top of them as i said before you use the credentials to get additional credentials down the path so if something expires at the root then things might start going going wrong but even like even if you have expiration dates uh

you know you might lose your device you might misbehave and we really want to evoke you so it's uh we cannot just you know avoid the problem of revocation just by using uh expiration dates but it's a value i mean it's a it's a way to at least kind of reduce the you know the yeah i guess i'm just thinking on like the web with tls certificates that's a much much easier setting and we still haven't really solved our location yeah we rely on timeouts yeah and i mean i we can talk more we actually have some discussions with people who work in the space that builds things like share life

second question which is in a totally different direction when kogan came out and people were talking about vaccine certificates like initially the anonymous uh credential crowd was like really excited this is a good application do you know if that ever went anywhere like was there any quality that said like let's actually try this uh that's a good point i think at some point most of the research actually safety towards uh tracing like privacy tracing but for like new york you're right i do remember yeah i don't remember i do remember talking about this like vaccine for themselves i don't know what happened i would guess if something happened would be in europe suddenly

you're aware of anything i i yeah did we miss the greatest opportunity yeah well again i think that the focus kind of really sitted on on the anonymous uh tracing so because that was what was really being implemented i guess most of the people kind of yeah i guess in retrospect though like the if we had another pandemic we sort of decided the anonymous tracing is worthless but uh yep so maybe that's gonna change all right thanks [Applause] and i was not really paying attention

with some questions i'm sorry need to stay here and we want one mute and tell us more about me more than happy to see the example all right they both have like a digital signature

[Applause] [Music] we had [Music] because the sovereign foundation