ZK11: Anonymous Credentials Based on Programmable Zero-Knowledge - Johannes Sedlmeir

Transcript

[Music] so my main motivation is to show you an application of zero knowledge proofs that's somehow outside the defi ecosystem and to give you a glimpse of why Regulators are in fact quite interested in the opportunities we have from programmable zero knowledge because we have quite a lot of limitations on like all the zero knowledge systems that we can overcome at a certain cost so so to give you some background today in the morning there were already two very interesting sessions that are using biometric passports and then creates your knowledge proofs of statement derived from basically signed biometric or non-biometric identity

information derived from a passport and in fact the discussion of how to use digital identity systems um is already much broader particularly in Europe and Canada and so basically governments have noticed that often times they're quite dependent on identity systems that are not really under their control what does that mean today when we authenticate with a service provider we usually have two main paradigms so the first Paradigm is using a lot of different accounts and so for example when I want to rent a car then I usually need to go through a tedious registration process in which I

need to provide my name my banking information and prove ownership for example of a driver's license and this happens in a video identification call where I show my driver's license and I need to smile into the camera and somebody either an AI or an employee is verifying that that's really me and that I have a driver's license so those teaches registration processes need to be repeated when I go to another provider of car rental so I need to repeat the same registration forms and processes for verifiable data over and over and beyond that users typically also struggle with key management or password management there is an alternative that is based either on corporate or government identity platforms so maybe you have heard about

for example India where you have the adhar system which is a very efficient system but unfortunately it usually doesn't give you a great level of privacy with respect to the identity provider and also you have certain dependencies on those often Federated identity providers so for instance Google has repeatedly locked out businesses where unfortunately for example a photo a child was uploaded to sent to a doctor and they accused them of child pornography and so particularly the European Union is quite concerned that they have a huge dependency on big Tech identity providers from another legislation so the question is can we do better and in particular both of those approaches usually don't give us access to for example a remotely machine

verifiable driver's license diploma ID card and so on so what would we like to have so ideally we would have a system that is quite similar to the way we have physical proofs of identity which is we carry them around with us and we show them if we need so without the need to contact the issuance party so the one who gave us a passport the one who gave us a covid certificate and the like so we would like those documents in a digital wallet app carry it around with us and if we need so use selected identity attributes from different documents so in this case from a passport a vaccination passport and an event ticket in order to show that they

belong together and to reveal the required information to a relying party so in fact the European Union has noticed that this is quite important and there is recent regulation that will basically Force every member state of the European Union to provide their citizens with such a digital identity wallet in the next two to 3 years and so the question is basically what is the role of privacy in this approach and how can we use Zer knowledge proofs to get the best privacy guarantees out of this now how do those systems usually work and how will the European digital identity Wallet be built it will be built on digital certificates so essentially like the way the public key

infrastructure works we have for example an x509 certificate and we replicate the properties of an ID card and other verifiable documents using digital signatures so we record different identity information inside the document we have the signature of the issuer which corresponds for example to The Watermark that we have on this physical card and we usually also have a binding key which we use to make sure that only the authorized holder is the only one who can present this document so to have some information asymmetry we have a cryptographic key pair and we record the public key of the holder inside this digital certificate so how do we usually present this probably most of you have seen this

before so we have a verifier relying party the holder has this digital certificate and the private binding key and so in order to prevent replay attacks the presentation usually starts with the verifier specifying a challenge and specifying a set of identity attributes they need and the restrictions that those need to satisfy so for instance that they only want to have uh the first name and the last name that is signed by a public institution they know so by specifying the public key and then the holder will sign this challenge with this private key send over the whole digital certificate to the verifier and the verifier will check a is this properly signed and B does the signed challenge correspond to The

Binding key that is recorded here does this make sense so far or are there any questions so this is probably well known to most of you in fact it's a little bit difficult because usually Regulators also require revocation methods so if you're caught driving drunk your driver's license needs to be revoked and this needs to be publicly announced because no nobody can force you to delete all the copies of the documents you have and we usually also have a kind of a hierarchical issuance so for instance my ID card would not be signed by the government directly but by some municipality who is certified to be allowed basically to issue this with another credential or certificate they have on their own so now if we look into this it turns

out that those digital certificates include some more information than what the holder is usually aware of and what the verifier needs to know so in particular we have a bunch of unique cryptographic identifiers that are either unique for this particular document or even unique for the holder itself so for example this binding key if this is for example Hardware bound and so usually the holder is not really aware that they are sharing much more information than what they think with the relying party that the relying party then can then use to track for example the holder beyond the identity attributes that should be shared and so to make this more detail so usually what the verifier needs to know is for example a selected set of identity

attributes maybe first name and last name but not date of birth and place of living and there is a feature that is called selective disclosure that is as we will see not too difficult to achieve technically that the verifier should have the opportunity to request only certain selected identity attributes and the holder can be sure that they only share this data but there is a lot of privacy issues that go beyond selective disclosure so for inance stand we often want to have range proofs so this is a commonly cited example where instead of receiving the true date of birth of the holder the verifier just wants to make sure that they are older than 18 or 21 for an activity we have linkability through the value of the digital signature so in fact by seeing the digital signature of

course the verifier can check that the document is valid but they can also use the value of the digital signature to recognize another use of this certificate so this is more than what the verifier really needs we have the same for the holder binding so instead of just learning that the holder was able to for example create a signature that shows that they um are the owner of the certificate the verifier also learns the value of the public key which is correlatable we have the certificate expiration date that is potentially linkable we have the revocation ID of the certificate which is again a unique identifier of the certificate and we also have basically the certificate chain for the issuer which can also be sensitive because for

instance if I show you my ID card to prove that I'm German but you see which municipality has issued my ID card you can infer where I'm living so we see that there's a lot of excessive information that a the verifier doesn't strictly need in order to achieve its goals and B about which holders are usually not aware if they share this information because on their mobile phone in their Wallet app they will be they will see please share your first name and their last name but there will not be be aware of all the cryptography under the hood which may share more linkable information and so what we see currently in the EU is that this privacy Gap is getting attention from multiple sides so of course we have technical researchers

who know about the properties you can achieve with your knowledge proofs who say well this privacy is suboptimal and we could do better there is social arguments why this is preferable because we want to avoid surveillance Potential from governments and corporations we have certain citizens expectations and if citizens become aware that they share more than they see they will probably hesitate to adopt the solution which is against the interest of the regulator and we have even legal arguments why doing better is necessary because for example the European General data protection regulation mandates to engage in data minimization if it is technically possible and obviously if we share additional identifiers that are not strictly needed this is more data

than is strictly needed so it contradicts data minimization and basically it violates also the consent requirement that you have for a user so basically they need to be aware of which data they are sharing and so basically legislators have become aware of these issues and so fortunately in the regulation that mandates the use of digital identity wallets by European member states we have explicitly mentioned unlinkability and the use of zero knowledge proof we will see to which extent this will then be in the end implemented but at least this is basically an amendment that was was demanded by the European Parliament and in the very last revisions of the eidas regulation this has been built

in the question is how can we achieve this so today we have quite good privacy preserving identity Solutions out in the wild so for instance the German Eid achieves all of those requirements that I previously told you but not on a certificate based um approach but on a hardware based approach so essentially we have a secure uh element inside this ID card and if I want to reveal my identity to a service provider then we will have first a step of Chip authentication so basically there is a private key stored on my um ID card which is the same as an 10,000 other ID cards it will basically prove to the relying party that it is a legitimate ID

card and after that step in the authenticated Channel it will only symmetrically encrypted um answer to certain questions so for instance tell me your first name and tell me if your age is older than 18 or not so this was designed because it is a quite efficient way of achieving data minimization and it avoids sending signed data to the verifier which the verifier could then use for example to sell authentic data on the black market which would then cause problems from a security perspective because it allows for social engineering yeah so this is a privacy by Design solution unfortunately it doesn't really scale to the broad number of identity proofs we aim to support so I don't want to carry around a plastic

card for my ID card for my driver's license for my digital diploma for my library membership card and so on and so we basically want to replicate those functionalities on our mobile phone without the need to carry around those plastic cards I already told you that we can do so with digital certificates and in fact there is a nice document by the basically standardization body of the European Union that summarizes all of those different approaches we significant opportunities to improve the Z knowledge prod so if you're interested maybe reach out and we can together improve this so what are the solutions that have been suggested so two of them I really don't like the first is on demand credentials so basically every time you

need a certificate you reach out to the issuer and you get a new one this is basically exactly the model we tried to avoid because this corresponds to the Federated identity providers the second one is that the issuer initially could just support give you for example 20 ID cards instead of one and each time you need it you use another one in order to avoid linkability this is not very elegant because you carry around with you a lot of unnecessary information it also makes you traceable by the issuer because obviously the issuer knows which credentials they provided to you and so if the issuer colludes with the relying party then they could track you so not very elegant um selective disclosure I already said is quite um easy to achieve

you can do this with Merkel proofs or you can do that with salted hashes so basically you record as identity attributes in the certificate you don't directly include the identity attributes but only salted hashes thereof and then you can basically provide the digital certificates and reveal only the pre-image of those salted hashes for those attributes that you were asked for so this is quite easy and this is basically now what is mandated in the implementation of the European digital identity wallets so there are uh Json selective disclosure and ISO Moc so to driving licenses which have been standardized uh many years ago that will be implemented we can also Implement range proofs with some interesting and elegant

constructions like for example hash chains but unfortunately none of those Solutions gives us unlinkability because all of those Solutions I showed to you will reveal the issuer's digital signature the holder's public binding key and the revocation ID to the relying party because we still send over the whole certificate and so this is basically where what is called credentials come in and those are zero knowledge proof based attestations which allow us to achieve unlinkability as well so sometimes some of you may know this also as attribute based credentials um those have been implemented for quite some time so they were initially developed the first time in a practical way by kamish and Lan skaya um there has been an improvement that basically goes to elliptic curve

cryptography from RSA based cryptography to make proofs even shorter and proof generation even faster they are amazing because proof gener ation is really fast so there are Sigma protocols this is not snarks and they have recently been developed in a lot of large scale Pilots both in Canada the US and also in Europe so with large industry consortia of around 50 companies and several government institutions they have been developed and there are wallets for example also by matter and by lissy um so maybe you have heard about those projects so they probed Anonymous credentials at a large scale and those Anonymous credentials can indeed achieve unlinkability so they only create a proof of knowledge of the issu issue a signature without revealing the value of

the signature and a proof of holder binding so the knowledge of the corresponding private key without revealing the um public key but only proving that this is part of the credential so this all looks nice the bad thing about this is things get pretty complex so this is all quiet Niche cryptography so for example equality of committed values and if you look at the specification of the hypera Anon creds which are used in most of those projects you see that this is getting quite long and quite tedious just to achieve uh verification of knowledge of a signature a private key and non- revocation and so by the way this is the protocol specification this is not the security proof so you can

imagine that there will be bugs and in fact one has already been found so this doesn't scale very well we also have additional Problems by when we want to use those implementations in the wild so on the one hand revocation doesn't really scale so if you think about it you really need her privacy on revocation where a revocation list and the proof of inclusion or exclusion refers to a collection of millions of credentials because anything that gives you less Hur privacy will fail once you combine multiple credentials in one presentation because then the combination of basically slots in the revocation Registries will become a unique identifier for you so you need order of tens of millions credentials

covered by one basically accumulator for which you prove inclusion or exclusion in practice we get to 30,000 because after that the um different files that need to be distributed will become too large to store on a mobile phone Hardware binding is also an issue so those CL and BBs signatures they don't work in the secure elements on our mobile phones so the secure elements on our mobile phones they typically support the nist curve but they don't support any fancy zkp signature mechanisms so if we want to achieve Hardware binding which is mandated in a lot of cases like for example online banking then right now we cannot get unlinkability because we always need to expose the

corresponding public key yeah and thirdly also certificate chaining it has at some stage been developed also for the CL and BBs signatures but in practice this has never been implemented because it's too complex so it took 15 years to come up with a theoretical solution and it's nowhere near being practical so we see that basically all of those nice and highly performant systems are reaching boundaries once we connect them with the regulatory requirements that we would need for large scale adoption and so basically this adds to the complexity of the protocol that I shown you previously and this should illustrate that basically instead of using special purpose Z knowledge proofs which are very elegant and highly performant and work very very well for very specific cases maybe the

duct tape approach is a better one and we use basically snarks in order to well prove arbitrary statements about the c um the credentials we have at hand and in fact this was already mentioned the opportunity to do so by kamish in the 2002 paper where they proposed their domain specific ckps but basically said that this is beyond what is considered practical and now fortunately 20 years later after a lot of investments in blockchain space we are near a point where we can use general purpose zero knowledge proofs also for such statements and do mobile proving on them so basically now the new paradigm is that we use a digital certificate the

holder still has their secret key ideally it's stored on a secure element and then basically instead of sending the signed Challenge and the certificate over to the verifier and doing all of the checks on the verifier side we now ask the verifier what checks they would like to have we do the checks on the prover side on our side on our mobile phone and then only basically report report the result including a zero knowledge proof that we executed the verifier verification logic in the same way the verifier wanted us to yeah so this is basically the Paradigm change one additional thing that's quite helpful there where I come back to what I said previously that we want to avoid sending around signed data if we use uh

snark naely then basically our presentation so what we sent to the verifier will be convincing for any other party to which the verifier forwards this presentation so from a privacy perspective this is not good and also from an incentive perspective this is not good but in fact with a snark we can quite cheaply access a solution that has been proposed by vitalic um to make basically the proof designated verifier in the sense that only the verifier will be convinced and if they forward the data the nobody will be convinced and we do this by instead of proving the original statement we prove that either the original statement is correct or I the holder knows the verifier private key the verifier of course knows that

they Protected Their Own Private private key so they can be sure that I don't know the private key and therefore my originally intended statement must be the correct one but if the verifier forwards this data then anybody everybody will be suspicious that trivially they could create this proofs from the knowledge of Their Own Private key and so this solves a lot of issues because first well we don't run into the risk of verifiable data being sold on the black market we also can to some extent reduce the requirements on relying parties which usually need to identify themselves and be certified for example by a government in order to avoid um man inthe middle attacks now if we put this into a graphic cryptographic envelope we can basically make sure that

the recipient only has two choices basically either they receive the data themselves then they cannot forward it in a verifiable way or they don't even receive it then I don't need to be worried about a man INE middle attack so basically the flexibility that we get from general purpose ckps allows us to in some sense replicate the properties of for example ID cards which have been designed on a hardware base um to maximize privacy also now on a more flexible software layer is this new no it is not so basically it has already been proposed in 2016 by a team around marov kwise so they basically used a generic compiler

from C so GTO into a constraint system to prove the correct verification of a chain of x509 certificates and this is what really is a game changer also from the perspective of governance governments because governments are aware of the status quo in terms of Hardware that is out in the market both available for users but also for certified institutions who need to protect their own signing keys in dedicated hardware and they would rather prefer that we can basically keep all of the infrastructure that we have in place and keep a standard that is highly battle tested and where we only need to fit privacy around it instead of introducing new signature schemes new

hardware that supports these new signature schemes and the like and so the CK credit paper goes into a similar Direction they didn't look a lot into Hardware binding but basically both both those Works consider ZK snark based Anonymous credential which often times people working in Anonymous credentials find confusing because there is a lot of more efficient approaches but unfortunately they can't really incorporate all of the regulatory requirements and the Legacy Hardware requirements that we are facing what are the next steps that usually I'm discussing for example with Regulators so one of them is of course how fast is snark proving on a mobile

phone and it turns out that if you use CK friendly signatures and hashes this is not really a problem so you can verify a lot of signatures within one second uh on a mobile prover um but however if you want to have for example an ecdsa signature and Sh 256 hashing this can take like 30 seconds to a minute on a mobile phone which is well not as bad as you may expect but still not good enough to satisfy a typical user so we need more work on that and we need to incorporate Recent research for example also um with the um binary U binary Fields um where we can have maybe more efficient for example sh 256 hashing one issue that's also often

considered is outsourcing proof generation so there is quite interesting research papers that would allow for example your computationally bounded mobile phone to only do some initial blinding of your private inputs then Outsource the proof generation to a server and then basically unblind the resulting proof that you get back and therefore you can Out Source around 90 to 95% of the computation GPU acceleration is obviously also a topic so we need to get somehow closer to like 1 second of latency for all those operations to make it feasible from a normal users perspective where privacy is typically not the mo the major concern um another thing is obviously we need to lobby for standardization so if

governments decide that this is uh um worth pursuing they will usually ask their National or in this case European Security Agency if this approach is secure but unfortunately for programmable zero knowledge we haven't seen any standardization approaches on the regulatory side so there is CK proof for instance who are trying to develop those standards but it will need National or International standardization agencies in order to basically audit and certify those different approaches and of course this is difficult in a quickly evolving field in which every two weeks you see a new more efficient proving system um last but not least one important design question is whether you

use basically the ASC or the VM approach to those topics so the problem is that we have a lot of different verifiers and all of the different verifiers will have different verification logic some of them may ask for three identity attributes and Hardware based holder binding another may ask for revocation and expiration proofs in addition so you can think of thousands of different basically um statements you may want to prove now obviously you can't distribute like thousand different large proving Keys into this initial Wallet app so you somehow need a more dynamic or more modular approach to basically choose the verification logic in real time depending on the verifier needs and the

first approach you can do is apparently a zkv m where you can specify the code AS basically a private input a public input but there we usually don't have the performance we need and on the other hand the more performant approaches like for example gr 16 you need to do this circuit specific trusted setup and then basically you need to che check whether you can decompose the typical statements you want to prove into individual gadgets that you can then Link at the time you need them so there's a lot of open design uh decisions that need to be made once you would decide to develop this in the real world so hopefully I could convince you that basically implementing such a Anonymous credential system in the real world is highly

complex because you need to satisfy a lot of business and regulatory requirements but that c snarks may have the sufficient flexibility to incorporate those requirements thanks okay thanks a [Applause] lot do we have any questions for johanes uh hi thank you for the presentation uh I have a question uh at some point you said that the holder has a private key in the new ver version right and how do you make sure that the signature when the holder is generating

the verifi presentation is not shown right how do you prove ownership of the key without showing the the public key right so what what you basically do is that at the time of the issuance where basically the holder specifies the public key that they want to bind the credential to they will basically show an attestation chain that proves that this key pair was indeed uh generated in Secure Hardware so usually you get just a certificate chain that points to the manufacturer for instance and then by governance uh and policy announcements basically everybody knows that a credential will only be issued by this issue or if this Hardware binding is satisfied and then at the proving stage

basically one of the public outputs will be a challenge specified by the verifier so the verifier sends to me this challenge I sign this challenge with my with my private key in the secure element and then I use the sign challenge as private input to the CK circuit and in the circuit I do signature verification against the public key that is included in the certificate and I don't reveal this public key and neither do I reveal the signature I just prove that I'm able to create a signature with a key where the public key is indirectly signed by the issuer does that make sense yeah does that make more sense with adapter signatures it's kind of sounded

to the kind the same logic to me here so instead of verifying it with ZK like I present an encrypted signature with an adapter version so an adapted signature I'm kind of sure it's also easier to actually generate on chip cards so because you can do uh them more easily than to storing uh uh large with the large constraints and stuff so doesn't that wouldn't that make more sense with adapter versions so I'm not familiar with this approach so I'm happy to discuss it so from what I've seen thus far is that most of the more efficient Alternatives either don't work with Hardware that is deployed in the wild

because they only support a very narrow set of signature mechanisms and you don't want to to wait for 15 years until all the mobile phones in the market will have a new generation of secure elements that support those New Primitives or they are quite challenging to combine with like the other quite generic statements you may want to support and therefore rather than like tailoring five different cryptographic Primitives that are highly spe uh specific but more performant rather opt for the more generic and less performant approach to avoid like needing to audit five different stacks and rather stick with the one stack thank okay I think we have to wrap up

here um I'm sure johanes is still available during the break to discuss your questions so yeah thanks a lot everyone and see you after the break thank you [Applause]