Digital Signatures for web3 with Foteini Baldimtsi | a16z crypto research talks

Transcript

so today's talk is going to be some sort of tutorial on what kind of signature schemes we have encountered on the blockchain space and by no means this is not going to be exhaustive i'm not going to cover every single every single thing that we have seen in terms of digital signatures but um i'll try to give like a pretty fair overview so let me start and say why do we um care about digital signatures and what are digital signatures so i'm going to use um the cryptographic definition of a digital signature scheme so if you ever took a cryptography class you have seen this definition so typically we define a digital

signature as a protocol that consists of three algorithms there is a key generator algorithm that takes as input some security parameters and outputs a pair of a secret key in the public key there is a sign in calgary that takes as input a message and the secret key and outputs a signal tool and then there is a verification algorithm that takes us input the methods the public key and the signature and if the signature verifies for that particular message under that particular public key the verification algorithm you say accept otherwise it will save them so the idea is that the verification algorithm can be run by any third party as long as it knows the public key of the sign the two

crucial security properties when we talk about signature schemes are correctness which basically means that if a signature was signed with a secret key that corresponds to the public key it should also verify under that particular public key and enforceability which informally says that if you don't own the secret key if you don't know the secret key you shouldn't be able to produce accepting signatures under the corresponding public key and i'm going to formalize this um this definition soon so why do we care about digital signatures in web3 because they're literally everywhere um every single blockchain system uses digital signatures at one point or another um

and the main reason that we use digital signals for is to authenticate transactions and you know if you just recall for a second how bitcoin transactions work that they have inputs and outputs uh basically in every single bitcoin transaction you need a signature for every single input in the transaction okay in order to verify uh to verify the transaction so beyond that beyond like the basic use of digital signatures we've seen many more exotic as i want to call digital signature schemes that appeared in the blockchain space we have schemes like multi-signatures threshold signatures ring signatures

adapter signatures and we also care a lot about certain properties or features of digital signatures like malleability and aggregation so what i'm going to do in the rest of the talk is um to cover the three most popular digital signature schemes that we have seen in the space of 0.3 discuss the properties of aggregation and malability and then also overview at least the the feature the properties of this like more exotic as i call signature schemes like multi-signature threshold and so on and feel free to stop me at any point or you know ask questions whenever you have so i'm going to start with ecdsa

because this is a signature scheme that is used by bitcoin and many many more systems it was introduced back in 92 by scott vanstone and [Music] probably some of the reasons for which ecdsa was adopted by bitcoin from the very beginning is that it is a standardized scheme um it is efficient it is a curve based and it's not patented okay so it was freely available to use so i'm gonna give you a description of how cdsa works and for all these schemes i didn't clearly define that when i gave you the

algorithm from which and the signature skin consists of but for many of the signature schemes there is also some sort of setup phase that certain parameters are decided so for the ecdsa signature scheme we need an elet curve specifically bitcoin uses sec p256 k1 we need the base point in the curve uh the point z and we also care about n which is the order of the point z in order to generate your secret and public key you start by picking the secret key as a random indicator in the space from one to n minus one and then you do one point multiplication between the secret key and the base

point z to get your public key in order to sign a message you start by taking the house of your message and then crucially you pick a random nouns that i'm going to call k and if i compute the elliptical point that is defined by this random landscape so you're going to do again a point multiplication with z and get the coordinates x1 and y1 you're going to isolate x1 and take it module n and then for your signature you're going to inverse your randomness k and then take the house plus the secret

key times the randomness that was generated by k modulu yes what is this so this is the particular ap care that is being used by bitcoin so there are many many different options on the applications that one can use in such schemes and this is the the specific one that is used by so what you output as your signature are those two values are and theirs how do you verify the signature and i'm not gonna really show you correctness here i'm not really gonna show you why things work out but um just to have an idea of what kind of computations are happening here

um so basically again when you verify the signature you need the message the public key and the signature consists of those two values r and s you have to check that k um sorry that are that's a typo that aren't s are in the correct space you recompute the hass of the methods e and then you inverse s take s to the minus one and you compute two values e times s minus 1 and r times s minus 1 and then you do two point multiplications with both u1 and u2 to get an elliptical point x1 y1 and you're going to output that your

signature divides if the r that was given as part of the signature is equal to x1 and again i'm not going to show you correctness here because i would have to dig into a little bit on how this point multiplication works and why there is like a symmetry here but you have to trust me that indeed if the signature was correctly computed um r is going to be equal to x one here okay for other signature schemes that we're going to sit down the path it's going to be much easier to actually verify correctness yourselves what i want to highlight here a little bit is um a few um important points uh in terms of security and again i'm going to formalize things a little bit more the security of his tsa actually relies

on the hardness of the discrete logarithm problem in lp curves so if you see the public key it's hard to extract the secret key here and one more point that i want to make here is that the way that i defined is dsa here is um deterministic what does this mean this means that if i'm signing the same message with the same secret key and every single time i pick a different random nuns k i'm going to produce a different signature there is a way to actually make ecdsa deterministic and um you can refer to a particular rfc if you want to see the specification for that in a very high level the idea is that you're basically not just picking k randomly but you are

passing the methods together with the key in order to fix a particular value for that message and key but you can refer to the to the specification for more on that so in terms of efficiency you know you this might seem like a lot of operations but many of them these are actually pretty pretty um the operations that we actually care about the most expensive operations in this scheme are actually the point multiplications and as you notice during signing there is a single point multiplication and what i also want to highlight here is that at least for the non-deterministic case you can actually pre-generate these k-entry values because you can see that up to here i'm not really you know

using the message the methods e is only used at this part so this operation and this operation could potentially be precomputed so you can kind of save a little bit on the signing phase um during verification you have to do two-point multiplications and there are also some tricks there with like pre-compute tables and something that's called the same streak that could break this down to roughly one point multiplication there is one more operation here that is kind of expensive not as expensive as the point multiplication and this is the inversion of the value s but these are the most expensive operations here in terms of sizes um the signature size uh is um 64 bytes

and the key sizes are 32 bytes technically for bitcoin the size of signatures are a little bit larger roughly between 71 to 73 bytes and that's because um ecdsa was implemented with the openssl library and has a particular encoding that need that the signatures need to satisfy which kind of blows up the size that you can get okay so the size of signatures on bitcoin i think most of them actually these days are 71 bytes all right so you know we any questions on how the the scheme works high level here i bet most of you have actually seen ecdsa before

like full node implementations actually compress the signatures and i was actually looking into this and i'm not aware yeah that's a good that's a good question exactly yeah because if you bring this down to 64 that's yeah that's actually important so yes what is yeah so so basically it's a combination of pre-computations that you can do on certain points in the curve and in versions that you can do a little bit faster i can it's hard to describe it but i can give you references if you want to look at yeah um and my understanding is that actually certain full nodes are using such tricks to um to verify signatures a little bit

faster so it's like for a specific generator point you get much faster versions or like what's the yes yes again with certainly compute pre-computation tables um so um moving on into security as i said the critical properties for digital signatures or correctness which is easy to describe um and also unforgetability which i will now describe a bit more formally because you know this kind of actually matters a lot for security so usually in cryptography we define security via a security gearing so we're trying to capture exactly what

an adversary can and cannot do um with with a security game so here the idea is the following um we define a silencer and we have an adversary that tries to be able to break the possibility of a scheme the challenger typically we pick a pair of a secret kind of public key we send the public key to the adversary and when the adversary will start the so-called silence phase where it's going to select messages and send them to the chancellor the silencer will sign the messages with that particular secret key and send back signatures to the adversary and this can be repeated many times technically a polynomial number of times

and at the end of this game the person is going to output its forgery this n star and sigma star and we're going to say that the adversary wins the adversary in other words breaks the possibility of the signature screen if it manages to output a signature that verifies and the message and star wasn't created before okay so this is what we call um unforgivability uh and with all these existential thousand messes so having this definition when we're trying to prove security of digital signatures or you know authentic

cryptographic schemery what we're trying to the ibl theory that we want to give is that the signature scheme xy is unfortable under a particular hard problem in the standard mode so this is like the ideal security definition that we want to give so what is the case with ecdsa um we know like there has been a lot of research uh in trying to actually formalize and pinpoint exactly what is the level of security of this bsa starting back in 2002 so back in 2002 brown produced security of its vsa in the so-called generic group model

which is kind of an idealized security model it's not like a standard model under has collision resistance um later in 2016 we had security again in the gm under different house assumptions and um an idealized function that was used for like the mapping of the random numbers and the etiquette points and very very recently a couple of months ago we had a new proof of security by growth and soup on a special version of the generic group model that was specifically tickers so you know for those of you who are not photographers in the room this might

sound kind of you know funky and really wondering what are the differences between these results well in practicing as cryptographers we really care about the you know the underlying assumptions the models under which signature schemes are being proven under and the problem with this dsa is that all these systems other bits these security groups are given are actually kind of idealized models of computation so again they're not like standard mobile groups again this doesn't mean that these are insecure or you know there are certain attacks it's just not the ideal type of security proofs that we'd like to have okay just to clarify that again there are no attacks i'm not claiming any attack it's just that we cannot we don't

have crucial security for ucbsa that are under you know the most acceptable standard uh models okay um beyond the theoretical security and as i said there has been a lot of effort on the app ects is actually pretty uh implementing vcds actually pretty notorious and there can be many many issues that completely happen at implementation level or you know incorrect configuration of apis and so on and i just want to highlight a couple of attacks so there is a well-known attack that allows an adversary to recover the secret key from a signature

if this random landscape that was used during signing was revealed so if for any reason this random scale that we picked during signing was revealed then an attacker can extract her secretly and to make things even worse this can actually happen even with like parts of k being uh being public or even by having a way to have like a biased randomness generator that spits out this case and you can figure out something about the the next randomness it's going to be so these are harder attacks they usually like create analysis lattice-based attacks and there's like a plethora of um compressed forms

so the good practice there is to actually keep on case uh use secret do not reuse and be very very careful get to the front of the sample to do any of the wallets generate them like pseudorandom using uh using a prf are they all i don't know [Music] lipstick e is like very much designed to not lose balance because then you might have a bad randomness generator and you run into these issues so the better way is just generate it let's chosen from your

private key uh pseudonym if you don't know the bias video like there exists some bias can you still like attack it i don't think so i think they actually need to know you know certain patterns on the um on the next nonsense that they're going to decide um the second point that i want to make about this dsa is that um easy they say signatures are malleable okay and what all this means um so uh specifically for cdsa it's actually pretty pretty easy uh to see why this happens uh because the 80 curves used they have some sort of symmetric

properties it's very very easy for an adversary looking at the message in the signature to just take the symmetric point of the signature on the curve and come up with a second signature that is also valid for the same lessons so this can create replay attacks especially if signatures are used as the unique transaction ids of transactions in bitcoin and this was a case with mount kos many years ago and what is important to enforce here is that there is a single canonical signature for any given public in fast methods and this is something that is

actually adopted by ethereum so they kind of remember that i said that it's very very easy we see this area to have to just take like the symmetric of your signature and have like the minus sigma also being a valid signature so um what the theorem does is that it kind of splits the space in half to essentially not allow you to have to be able to pick this symmetric point um and another thing that you can do here specifically if you care about this unique transaction ids is as bitcoin does basically treat the transaction like this differently with the segwit introduction and again i'm not going to

get into too many details on this because there is so much to cover um so this kind of concludes my discussion on it's the essay and uh what i'm going to do now is to actually move into different um signature schemes and see what else is out there i need more questions and you see the essay and again i'm happy to give you references there's a lot going on there so what do we have beyond this bsa um there are basically two more types of signatures that we've seen a lot in the blockchain space um the first type of signatures is the so-called snore signatures which are now accepted in bitcoin

post top root and polka dot and there are also the edsa signatures which are basically the deterministic smart signatures um and we also have um signatures which are adopted by cello and hopefully i think so i will basically go over snore and be a signatures and then move on with the other model different features and properties of signatures so before doing that why do we care about different signature schemes um we care about

more efficient signature skins we care about schemes that have better or more standard proofs of security and we also want extra features as i'm going to discuss which were not supported by uh cdsa so um snore signatures are actually kind of older compared to ecdsa um the problem though is that uh snore signatures were patented up until 2008 so many people actually believe that this was the reason that they were not immediately selected by bitcoin uh they're not standardized yet as far as i know uh there is a specific um specification for bitcoin

uh for that particular for the particular ap curve that is used in bitcoin and let me show you how they work so um the parameters that we need for the scheme is a group g a prime order q with a generator or etsy uh you want this group uh to be selected in a way such that the description problem is hard so now i'm going to solve the scheme not by using electric curve notation or by using point multiplication to kind of make it a little bit easier to distill so the key generation algorithm picks a random secret key computes the public key by taking the generator and raising it to the secret key again because of the discrete lowering problem it's hard

to figure out the secret key from the public key and now the signing algorithm again picks this random numbers k it sets r to be z to the k passes the message along with this randomness r and computes s to be k plus e which was then output of the house times sk the secret key are molecules and outputs what's that um good point yes you need to include the public in the house yes so

to verify uh it's actually easier to see why the signature verifies uh you literally compute e and here if you obviously do the public key you have to include it here as well and verification is pretty simple you just take the generator raised to s and if you see s is this k times e secret key so this is z to the k z to the a times s k and that's r which is against e to the k so that will give the case go away public key raised to the e and again if you see z to the e times the sk you can see that things actually cancel out and it's very nice it's much easier to see that in verifies compared to easy dc so

in terms of efficiency things kind of look similar to ecdsa we have one exponentiation that is needed during signing and two exponentiations that are needed during verify you can think of exponentiations being almost equivalent to point multiplications here so efficiency explicitly similar and the signature size is actually 64 bits and again the keys as before 32 bytes uh sorry 64 bytes and signals which is um are 32 bytes similar to twisted dsa for the same security okay so what do we know about security uh for snore

so it's not actually has a better uh unforgettability property has a better enforceability definition so recall the portability definition that i gave you before um i was saying that the adversary wins if it outputs and methods and the signature such that the message was not created before so now i'm allowing the adversary to win even if it outputs a new signature on a message that we did query before okay so basically again if an adversary manages for a message that it has

already queried to output a different signature than the one that it received during the challenge phase this is still considered an attack so we still consider this adversary to be breaking the scheme okay and this is a stronger property this is a better property than the one that is satisfied by csa and this is basically the reason why uh the snore signature scheme is not marriable okay it doesn't allow to have multiple signatures for the same assets so what do we know what are the theoretical results that we know on the security of of snore signatures so there is this very celebrated and famous uh result by ponce

valenstern in 96 who formerly proved a snore signature scheme in the random oracle model under the discrete algorithm assumption so they introduced a technique a proof technique that it's called the forking glenda and it's a proof technique that it's used in many many security proofs of signature skins um they give a huge reduction again i want to highlight the random more of the mode similar to the generic group model that was used in ecdsas again like an idealized model commutation it's not standard model but it's probably a little bit more standard compared to um and uh there was again like numerous results and i'm not being exhausted here

that actually improved the tightness of the reduction that was originally given in 96. so um i just want to mention that just because it popped up like a couple of days ago and many of you might have seen that on twitter um so as i said before evdsa is the deterministic version of snow and i just want to highlight an implementation pitfall that was actually discussed on twitter by um by costas one of the sui mistanians cryptographers so basically they found out that roughly 40 eddsa libraries for the particularly

beam 255 255 19 they would expose the private key if the signing function was misused um added then they are on purpose and what was the problem there so basically the problem there was with the signing api of the library so the signing api essentially embedded the secret key but allowed to give us input the public key as well on top of the message so this could potentially give rise to an attack such that an anniversary could extract the embedded secret key if it asks for signatures on the same message under two different public keys

and again it's a little bit hard to show you like the math behind the attack but it's actually not that nothing fast it's not again expensive at that person so um the reason that i wanted to mention that again as i said it's because it just popped up like a couple of days ago and it received a lot of attention on twitter and uh it's it's a very clear example of how things can go wrong completely in an implementation okay so um no there were no known at least um vulnerabilities that would actually you know be an attack vector but um many companies that were using these libraries they're trying to pass things up okay

so um it's very nice properly of the snore signature scheme and here i'm just recalling the snore signature for you is what is called uh bats verification and this is a property that is not supported by acdsa so what bad sperification allows to do is the following so you assume that you have a minor and it looks at the block that has a whole bunch of signatures and of course um the miner should verify all signatures first so the nice thing with snore is that you can actually but reduce the cost for the verification of the signature so

basically what do you do is that you take all the signatures and look again this was the expensive verification operation that required two exponentiations so you would have to do two exponentiations times n to verify all the signatures individually but because of some essentially linear properties that snore satisfies you can take the sum of all the s's raise z to the sum with their quants pronunciation now and then multiply all r's together and then do of course the separate exponentiations for every public key so the nice problem here is that you're taking this from two times seven exponentiations to n plus

one okay so this is a significant improvement on the time of verification here um i'm trying to draw some comparisons uh between cdsa and snorlax i'm also gonna add bs in the picture so again specifically for the case of bitcoin ecdsa signature signing verification cost is pretty similar in terms of security snore has stronger security and it doesn't support my ability and it's also proven securing a kind of more acceptable security model and it also has this very nice feature

of bat verification that is um is missing from from the cdc so next i'm going to move into bis are there any more questions some this would be essential before going back ggn model contained inside the rl model or uh sorry can you pick that the gtm model contained inside the rl model no so these are two very different computational models and um in general the dji model is considered more strong compared to the random model model and in cryptography when we say something you know when we say the model is strong it's kind of worse um it's the best verification and

you just showed it like there's an add-in do not need to take a random media combination yes yes it does i mean i'm just selling the the basic yeah i guess of course so just summarize there's basically no reason to use uctsa ever i would like to make such you know to come to such conclusions but um no known advantage besides patents for like standard implementations [Music] browsing online because it was so much

on the edge people say that this was the reason that it was not and it was not standardized back then even now snorer as far as i know is not standardized as i said there is a specification for bitcoin but there is no like central standard i guess the great irony is the patent was like it expired right i mean again this is just speculation why it wasn't used and you cannot cannot be switched um all right so um let me move into blx which is going to be the last scheme to calvin

so uh business signatures are much more modern yes compared to ecbs a.m snow introduced by dan bonner bengali in 2004 there is a standardization effort in progress right now and uh they use a different um primitive uh instead of just like the basic discrete log that uh snoring vcdsa was using um they use something that is called the biennial pairing and they rely on the electric curves that are actually very friendly and what i want to highlight here is that the particular iot care that is used by bitcoin does

not satisfy this problem okay so we could not implement bls on top of bitcoin so i just need to give you this like very short claim here and what the binary pairing is and then after you understand that you're going to see that the scheme itself it's actually very very straightforward and very easy to um to digest so a bilingual bearing is basically a mapping where that takes two inputs from z where there is a pairing friendly curve and gives an output to another curve the very very nice property that you have here is that if you have two values to the a and z to the b that are parts of

of z then if you take the pairing if you apply the function move the a into the b then this is equal to basically bringing the exponents outside and taking e to the g comma z raised to a times b and as you're going to see this property is going to make our life very very easy in uh in verification so let's see how the scheme works um again parameters group g of prime order q with generator g um again you want to discretely be hard the public key and the secret gear selected in exactly the same way as with snow signatures but no housing is done differently

so the signal tool is just online remember is it the same snow before that like you know multiple computations it's the signature so you basically just has the methods and you end your days with the secret key so notice that this has function um needs to have like kind of special properties it needs to be a hash function that maps to points in in the curve so not every single has function can be used here and then to verify that the signature is correct um and sorry this should just be sigma here you just need to check if the pairing of sigma comma z is equal to the hash of the methods comma

public key and here again it's very very easy to see why the algebra works verification is very nice do people see why this verifies it's you know it's much simpler and not before so um something that i want to highlight about va signatures is that they are deterministic there's no randomly speak here and on top of this they're also unique so unique means a different thing than deterministic for digital signatures so unique basically says that there is no other signature so that every signature really match the particular message and secret key and that's unique there is no

it's not possible to compute another signature sigma for a different combination of messages and secretly okay why deterministic says that for this particular secret key and message there is a unique signature okay but again unique the other way is that there is no other combination of masons m-secret key that would give you the same signal okay so it's kind of you know those two properties i feel that they're often confused all right so again what happens in terms of efficiency um so we have the iphone experiment series for the key generation similar to all the previous schemes um and one exponentiation for signing and for the verification what we need is

to compute two pairings so typically this pairing computation is more expensive than the exponentiation computation so this is something that we have to keep in mind when we're looking into business so verification can be more expensive signature size is much smaller it's like half compared to um to snore and icdc because it's just one group element so it's just like effective two technically beats and bites and signature sizes are also private what's the size 96 right sorry it was just counting publicly secretly sorry i should have used that i'm just like

signature size class publicly secretly but it's ignored so what do we know in terms of security um the security of bls has the same so bls is the same portability definition as with snow because it is stronger a version of of unforgeability and uh in terms of theoretical results uh the original paper showed that bls is securing the erato molecule under so-called computational difficult assumption and then there was a more recent result that actually managed to make this reduction a little bit tighter in a

new model for [Music] so again if i try to put together and draw some comparisons here um [Music] the main advantage of ba signatures is that they're much shorter um signature verification co-signing costs about the same verification cost is higher because as i said like the pairing operation is typically more expensive than exponentiations um the security is comparable to that of snore and it also allows for uh for battery verification so i mean do people worry about like you

can only implement bls and carrying friendly curves so they're like there's more chance of some discrete log break because the curves have actually yeah i think they do yeah yeah so there's a lot of discussion on the right cares and so billions though has many other nice properties that make it attractive and i'm going to highlight some of them does the same that go up until uh is it one hour or one hour and a half okay so right okay and we started a bit late so okay so um right so a nice property of bls signatures is that they also allow for aggregation and

let me explain what this means by giving you kind of the definition explaining what an aggregateable signature is so when i defined digital signature before i said that they consist of three algorithms kids and sign verify an aggregateable signature screen will add two additional algorithms the signature aggregation that is going to take as input a vector of messages a vector of keys and the vector of signatures and how to the combined aggregated signature and a verification algorithm for this aggregate so if we kind of try to view that as a graph the idea is that we have an algorithm that takes

signatures under different public keys and distinct messages and combines them to a smaller with much sorted aggregated signals so let me show you how this is possible to do with um with bmx and obviously the the main advantage that makes this property very sexy on the blockchain space is that it can really compact the space the storage space in a block instead of storing every single signature you can just aggregate them together and you know really reduce the storage space there so again remember how the bis signature works i'm just recalling the scheme up

there and let me show you how can you possibly combine multiple signals together the idea is pretty simple um you just take all the signatures again think different signatures different messages different public keys you multiply all the signatures together and then in order to verify uh which in a sense also supports box verification at the same time in order to verify we just take the pairing of aggregated signal tool and then you multiply the pairings of every single message with the corresponding quality and if you do the math and you bring out the exponents here you're going to see that

this actually very fast so again the nice property here is that instead of storing n times 32 bytes for the signatures on the chain you're now on the store intended to buy something still again you would have to store separately the public keys and then the messages because they're different you just you can just combat the signature size um together you can just like combat the signatures okay and uh as i said this naturally gives you bad verification and it takes the pains from two times seven twenty five okay is it clear why this works in vls yep so this is a very very

nice property so a different property that is also very commonly discussed in the blockchain space is that of multiple signatures and if you think on you know if you think about what multi-signatures are you can think of them as a special type of aggregate signatures but now the difference is that you want to produce a single signature but on the same message again remember that in aggregate signatures you had different public keys different messages now you want to have like a bunch of signers sign together the same methods such schemes are possibly interactive

but not always and essentially the idea is that instead of having this like single sign algorithm you might have an interactive algorithm that is running among every signer in order to produce the final signature signal when you verify the signature you still need to know all the public keys that were involved in the sign okay again the main difference is that we have a single message so what do we know about first why do we care about about multi-signal solutions with three and blockchain systems they're very very valuable in multi-user wallets where you want to have multiple users signing samsung um in order to go through

uh but we've also seen them being heavily used in layer 2 protocols like certain um bitcoin tumblers and also on them um on payments and things like that so um let's see how we can build bls multi signatures again i'm just up here just recalling how various works and now let's think that you know i'm doing the same operation that i was doing before as the with aggregated signatures but now again keep in mind that all the signatures now correspond to the same message so basically what i'm doing is that i'm multiplying both the signatures together and now verification looks even simpler because on that side i'm still taking

the same pairing as before actually forgot to change them subscript here that should be the multi-signal tool and i can only do likely two pairings here by just multiplying all the particulars together and taking the half of the methods because this is there's a single message here so um this would very nicely give you a multi-signature scheme if it worked but unfortunately um this is very mirable uh it is vulnerable under a special type of attacks that are called the long public key attacks and basically if you did bls multi signatures this way it would allow an attacker to create a

wrong and adversarial public key which i'm calling the public key star using a knowledge user publicly and then kind of frame this user the honest user as also signing the message although the user never signed the lessons and himself so the idea is that if an attacker does know the public key of a user can set its own public key to be as pk star z2 sk over the public key of the user whereas case absolutely sk star the the secret key of the attacking sign this way with just its own secret key but then the signature will verify under

both pk and pk star so it will look like also the honest user sign receiver okay so this is actually a problem um we wouldn't like to to be able to do that and um now i'm going to ask you guys do you actually want to see how bls solve this problem do you want to see the scheme or just take it as granted that there is a way to resolve this issue be less and move on slide

and i'm just using the slide actually by um by the author so this um optimization this um this extra feature on bls signatures was not added with their introduction but it was added in a paper called combat multi signatures for the blockchain that was published in 2018 and the idea here is the following um so again key generation as before i mean here they're using different um like a bit of different notation for the generators um but now here is how do you aggregate [Music] the the signature you need to start by first aggregating the public keys so

what you do is that you take all the public keys of the signers of your methods and you multiply them together after raising them to this value alpha which is computed by taking the hash function on the concatenation of the public key that you're multiplying and all the rest of the public keys okay so again it's going to give you a different alpha for every public key because you're changing the order of the of the input so then after you have a select aggregated key in order to sign you first compute all the you know separate signatures all

the sigma i's and then you also aggregate them together in the same way you did for the public key so you take all the signal tools and every corresponding signature you raise it to the corresponding value alpha which is again the house of your own public key and all the rest of the families to verify we just need two pairings uh you take the signature and z2 on the one side as you always do with vs and um here you just have the message and we take the aggregated public key so this result was actually proposed in some forum post by maxwell aviv and then as i said was formalized later and

this gives secure multi signal to bls multi signal source and the sound claim of the cd8 problem either of the motor mode so is pki also included in the uh the setup or the contamination on the right side um i think it does it's yes but again the important point to notice here is that this ai is going to be different for every key because you're you know you're putting that particular probability first and again either you can think of this whole thing as a concatenation or something are g1 and gt required to be the same in the setup or is it more general they're different in the previous right i was doing this as being the same personality but in practice

does that affect no it's just now it was mostly done for notation to simplify the place so is it important that each one and each knob are different yes they are different cost functions the crucial part of this has function with this particular hash function here that is used in signing of vls is that it is a special hash function that maps to ethical points and this is important i'm not that the case manager satisfies that this is a regular first function that the smartphone indicates so there's more flexibility uh and again implementations would be like there's quite some discussion and maybe there are also some relevant research papers and they said has ready to get points

functions which you know might also give some complications obviously like a point in the recommendation of bis that kind of needs a little bit of specialty so [Music] in terms of security again their affordability game saying this when we refer to multi signatures it's not the same as before um so here the idea is that again you have an anniversary takes us input the public key this is like the owners the user's public key that the person doesn't know the secret key because this is a multi-signature scheme um we might ask them adversary that western might ask the challenger to receive a bunch of signatures other

corresponding secret key but also that person might create a bunch of security pairs secret publicly pairs on its own and we're going to say that the adversary breaks and possibility if it manages to output this like multi-signature on this egg combined public key that also includes the honest user's public key on a message for which it didn't receive a signal to appear so we're basically saying that it managed to create a multi-signal tool that includes particular methods that includes a signal tool from the honest user as well although we always use another sign okay so again you see like a different favor

we have to be very very careful in how we define these things um and um again i'm putting certain things under the right here but these definitions can be even more complicated they might allow that person to be like adaptive to incinerate more keys as you know as the game um keeps going so there are many many different favors of this definition so just giving you the very basic one so um what do we know about multi-signatures for the bls we already saw the result

and the nice thing about the basmati signature is that as you saw before it kind of looks like an aggregated signature it doesn't really need interaction between designers um multisignatures are also supported by snore so it's you know it's not a feature that is missing from snow but snow multi signal tools require interaction in order to produce the signals they cannot be done by kind of aggregated things to give there um any protocol is easy to see without interaction actually but again with the insecure under this similar key um again there has been a long line of research on normal signal tools um giving the only like the most notable

results there was an impossibility result at some point on two round snores style multisignatures and more recently there was a favorite detachable man to overcome this interaction by sending a little bit how the designing process would work and this is the so-called music 2 scheme for those of you that have heard it and the nice property about those signals which isn't small is that the final signature is actually indistinguishable from radiation from radiation you cannot even tell the signature is um is a multi-signal ecdsa also supports

naive multisignatures in the sense that you can just concatenate things together but without all these nice savings in the size of the signals or in the verification so this is what we know in terms of multi-signatures and again the main point here is that for snow you need to okay so i want to cover a few more signature notions not in as many details as um so i'm not going to be showing you how schemes work i'll just speculate in the finishers and i try to highlight the differences between you know the different properties that

the signature skins have so the next signature i want to mention is the so-called threshold signatures so multisignatures have this analog sign policy you want to have it all and signers signing the lessons but people have other policies what if he wants us to get these signatures out of a set of any public keys and so on so threshold signatures allow us to do that and um they have like an important factor though an important point that we will be careful about so the kids generation process is not independent as before it's not the case that every user can just generate their

own keys typically in threshold signatures you should think of them you know actually administered and whereas in multi-signatures you should think that every user has its own keys and they can put their keys together to sign something in fresco signatures you should think of it as a group of signers as a key and they break down the skin pieces and give all the pieces all the sales of the key across the different members of the group that's why the key generation process in other gate signatures is actually a multi-party protocol it's a proper between the participants of the blue between albion parties in order to

define a single public key that looks okay they are signing public key and all the sales of the secret keys so you might you might have had this as being called the disability generation protocol there is a lot of research on just this part of the protocol like leaving the threshold signing aside it's like how can we efficiently create those those keys and i think sarah also has some reason for her to decay at the kdz and there is then the signing protocol is also typically interactive so we want all the signers to interact together using the cells of the keys again the nice part is that you can only have like

tea of designers the signature will verify as long as the correct threshold of signatures was satisfied do you rely on a secret [Music] out that i'll say about authenticated science [Music] so one of the nice things as i said before the signature is completely

distinguishable from a review signature the same for the public key um and the nice property of threshold signatures is that you actually get privacy for designers so you don't really know who are the p signers out of the end that actually signs the problems are this interactive expensive one-time key generation it's hard to obtain the public key so let's say that you want to remove a member from the group or other new members you have to recreate new keys and also the signing is necessary interacting while you know as i said before from bas for example in multi-signals which there was no impact

so if you try to compare threshold signatures and multi-signatures it's really a trade-off it depends on what kind of applications you want what kind of features you want the most important things is that you know in terms of sizes typically threshold signatures are softer um you just need a single public key multi-signature eventually you need all the public keys the key setup is required in threshold signatures in multi-signal which is completely transparent everyone has its own interaction is needed in threshold signal tools not always for multi-signal multi-signatures and cyber privacy threshold signatures height

who signed the methods multi-signatures on the other hand offer accountability in the sense that you know it so the privacy thing can be a feature or a problem depending on what is there what is your goal are there impossible results [Music] is the resulting and threshold signature are the same no matter which t signature you have or the signature might be different the signature might be different but still it doesn't allow you to distinguish that the second you know itself can be different but kind of distinguished uh on the previous slide uh when you were doing the

um i guess the aggregation step in the middle is the message required to be the same for each of those inputs yes [Music] so what do we know for threshold signatures so on top of correctness and comfortability i'm not going to give you the full definition here but essentially comfortability you want and possibility against t minus 1 for a producer so as long as you have less than the threshold for active users you shouldn't be able to afford signatures um and the property that is often required in threshold

schemes is that of robustness which basically says that if one of the parties are boards you want to be able to still complete the problem what do we know for the signature scheme that we have been discussing um in this we say there is actually a very very long line of work on threshold signal tools there is there are the most notable techniques someone some of these works is that they're doing some pre-processing to use the costs of online signing phase and that would be works that actually have identifiable goals so maybe the program is not robust but at least you can identify and potentially finalize the boarding parties for snore maybe one of the most motivated notably recent schemes is

frost we have one round threshold signatures again with identifiable boards and uh for bls uh we also have um a few constructions something to note about basis that um it has um uh allows for stuff that is the president cannot cover up as i said before additional parties throughout the game which is actually satisfied by spss so here i would say like you know in threshold signal tools bas is doing you know maybe a little bit worse in the sense of kind of

um summarize the properties um that we discussed without of course like having all the caveats on the security modules and so on under the underground is there any idea if that's a fundamental limitation of bls then i'm not aware of any possibility results but i'm also another way [Music] um they asked two signature schemes that i want to mention if people are still are still here with me

um and those are spring signatures and adapter signatures and um so link signatures uh have been used in the blockchain setting for mainly for privacy um oriented cryptocurrencies um so the idea of learning signature is that you have a signing algorithm that takes us into the methods a secret key and a so-called ring which is a set of public keys the secret key should correspond to one of the public keys in this set and in the verification you get the

message that you have a signature and it should accept the reject the important property that you get here and again i'm gonna formalize things faster than just two signature schemes is that you actually want anonymity and what does this mean this means that when you see a signature you don't know who was the sign anymore okay so who was then the user of the site notice that this is different than threshold signatures because the signing algorithm is not interactive or anything i can just say on the sign below i can pull the public keys of whoever i want without them being ever involved and create a signature that is hiding my

key under their keys in threshold signals people work together okay so you shouldn't view this as like one out of ten threshold signature this is not the case so i think i'm gonna skip the security game here but i'm hard to discuss it offline with people if you want to and as i said the most notable use of signatures is in monero where they're basically used to hide who was the center of the transaction within the link we have seen additional applications not strictly on cryptocurrencies but when they were originally proposed they would propose for us as a way of electronic voting hiding who you are

voters and also for whistleblowing which again might be interestingly clear to applications what do we know in terms of constructions so ideally when you construct any signature you want the signature size to be sublingual to the size of the um i really want to avoid any sort of transit center and optionally you might want accountability you might want to be able to figure out who was the signer they were introducing signatures back in 2001 and there is a bunch of subliminal constructions uh in the random world crs and standard model here unfortunately there is not you know a strict mapping

twist dsa dns and snore as i was doing before some of these schemes are under similar computational assumptions but it's not like you know we can just convert for example wearing signals okay so there might be skin that kind of using your skin but it's not like this one-to-one mapping with the properties before um the last thing that i want to mention um just because you know these kinds of signatures kind of you know gain some popularity in the last couple are the so-called adapter signatures or scripted scripts so these are signatures that receive two properties at once

you're able to authorize a message as a radio signature and at the same time i have the littles of a predefined secret one so with the idea here the idea is that this is kind of a very different signature scheme because we have name the secret in the public key and you have some entities some party that it's typically called the public servant that knows some secret and also his investments so what is the idea the idea is that if you get a signature from the designer all the methods then this should allow the designer to extract the secret tablet so in a very high level the protocol

allows the two parties to interact send some messages to each other from those messages you can view this as some sort of like pre-signing process from those messages the publisher can get a signature using the secret um sorry should i emit the message here the methods and those values and this signature should verify under the message and if the signature is posted somewhere you could keep it in a blockchain from the signal to the side you can actually extract the key so you might be wondering why this is even useful um this is useful in a sort of fair exchange

setting where you might have that's gonna go very slowly but um if you want if you have like a seller that wishes to sell some secrets and uh you want to kind of pre-lock the coins of the buyer before starting the exchange uh the signature is kind of i out of the nativity note that this fair extension you know cryptocurrency bitcoin is also possible without the signatures but then you have you're really stuck to use the particular hash functions that are supported by the underlying system while doing it in a signature level might give you a little bit of more flexibility

as as a primitive they were introduced by boy strong in 2017 we have compatible snow and vcbsa constructions and unfortunately we have impossibility results for bls and in general unique signature speeds so again the nice thing here is that if your blockchain system supports snore and vcdsa you can build this adapter signatures but you're not you know stuck to use a particular hospital process yes um and don't you contain some of the semantic content but with them uh i don't think there's any distinction you know whether doubling your type of idea so you should

and then use this protocol just like the fair exchange of coins and i was thinking more an application for something like selective disclosure of a certain part of like a potential right where m would be like encrypted you want to reveal some subs subfields uh containing them uninflicted so i'm trying to keep you younger and i just want to conclude with some takeaway points uh zoo of digital signatures many schemes with many different properties and you know i didn't even cover every single signature skill that we have seen in the

block space space uh blockchain space out there all the skins that i discussed are not post qualms eq so there's a lot of discussion and also what can we do with post quantum secure schemes we know cloud is based based signatures there are efficiency issues or missing features in such schemes um i'm going to highlight that it's very very important to understand the security model when you're trying to decide which signature scheme to use understand you know what attacks is its key security games number what assumptions and very very importantly also look out for implementation level apis use they can be loopholed for vulnerabilities and

we've seen that multiple times in space and with that i want to conclude them thank you and sorry for taking