The past, present, and future of threshold Schnorr signatures with Chelsea Komlo | a16z crypto

Transcript

so it's my pleasure to introduce Chelsea KLA today Chelsea is completing her PhD at University of watero she's also been a sci Chief scientist at zash foundation for a number of years Chelsea's work is on threshold schnor and threshold signatures in general uh she's been a co-author of one of the draft standards for ITF on two round threshold schnor signature and it's very exciting to see uh being standardized hopefully it will eventually be um yeah and please welcome Chelsea she's going to talk about her work on the threshold schnore thank you all for having me uh this title is a little misleading so I am mostly going to be talking about my work but I do hope to uh highlight other people's work in the space as well um so yeah the main

focus of this will be the work that I've done in the space but I do try to kind of like highlight um other Trends and other things that people has have done in this space and one thing I want to emphasize is this is about um threshold uh signature schemes there's also been a lot of work done on N of n or multi signature schemes so I'm not going to be talking about that but there has been like very similar work and parallel work in that space and we can talk about it but it's not something I will be reviewing today so I guess just a little bit about me um so I like to call myself a real world cryptographer uh before I went to grad school I was actually an engineer for a number of years and I did

things like I worked on uh encrypted encrypted mail for aning mail I helped contribute to the off the reccord messaging protocol which the um signal protocol is based on and I also contributed to the tour protocol as well um and in my work recently I've been part of the zcash foundation and I've helped uh uh contribute to informational drafts within the I ITF and really like my experience as an engineer has influenced how I do research and it influences um what I design and the decisions I make in uh the protocols that I work on so really whenever I do research my main focus is thinking about like what would be easy to implement

what would people want to implement and what is a good user experience and I try to use that as like my um North Star I guess when I'm working on cryptography and um so yeah overall this is about uh threshold schnore signatures but I would love to collaborate and I am really excited to be here and learn about what everyone else is working on as well a lot of work I've been doing right now is on threshold schnore so it's kind of been uh a wave but it's something I'm uh I'm now starting to look into other areas Beyond just threshold Shore so I know many of you here are familiar with threshold signatures and threshold schnor signatures um but maybe can I just get a hand for people who are working on like the economics side of things or consensus or formal

verification so okay good this is helpful so I do have a fair amount of background in this talk um for many of you this will be a little boring I try to have like things that are not boring to those of you who are in the space um but I will go through some background um for those of you who are not familiar with with this work so just to recap um what a threshold signature is so it's a public private scheme where similar to a single party signature you have one public key that represents a group but then you have some set of parties each which hold a secret share and we generally say that it's a t out of V scheme so here I'm showing you a two out of three setting where you need at least two parties to participate in signing in

order to issue a signature and key generation it can either be done by a trusted dealer or uh distributed key generation protocol um and we'll we'll talk about that in a little bit what's nice about these schemes is they allow for some kind of distribution of trust and uh utility in the case of failure so even if one party were to be corrupted the security the scheme would still remain secure and that's something we we really like about these Primitives another thing that's nice is when signing is being performed secret key material doesn't need to be sent around to other parties secret key material can remain local and oftentimes you can use a public channel in order to perform signing there are a lot of applications for threshold signatures most of them

are in the blockchain space but something I'm hopeful to see in the future are things like adoption for certificate authorities and that was actually one of the original U motivating examples of threshold signatures is having something like a certificate Authority which um is used in the web pki be able to issue signatures it's really interesting how quickly threshold signatures are being adopted but I do think there's like real practical interest in threshold signatures and one example I like to give of where they would been useful is in the mount goau example so if you're not familiar with Mount goau it was an exchange and all of users assets were maintained in one wallet and then the assets were later to be stolen so um

threshold signatures really are a tool in order to distribute trust in order to ensure um basically like any kind of authorized action over some kind of valuable asset so I do like to have like real world motivating examples of where we might use these things again it's not just like cryptographers trying to sell people on their work uh there has been a call by nist to it's not a standard yet but they're asking for submissions of threshold signature schemes they we can think about it more as like an open call for nist to see what schemes exist out there right now they're working with cryptographers and we're in the process of submitting one of our schemes and then hopefully in the future we'll

eventually see some kind of standard but hopefully there's a lot more development in the space and then we'll actually start to see some codified standards in the future I've been talking about threshold signatures and their security and now I'll Define that a little bit more uh precisely so when we say a threshold signature scheme is secure one of the main things that we talk about is the notion of unforgeability so we want to make sure that some adversary can't forge a signature that's pretty intuitive that's something that we would say for any kind of signature scheme another thing we need to think about for threshold signature schemes is the notion of live so basically if you do want to create a signature the system is able to do so and I do think liveness is sometimes

lost when we talk about threshold signatures um but both Notions are are quite important so even if you had a scheme that uh an adversary wouldn't be able to forge a signature if they were able to prevent funds from being used then that's that's also an attack we need to think about and then one more terminology I'd like to throw in there is the notion of robustness I has told you about liveness basically robustness is a technical term that we use to say that the protocol should be able to succeed as long as te players participate honestly so it's basically a technique that we use in order to achieve liveness um I'll use this term later in the talk but it's something that I just want to say it's it's a means to an end in order to achieve livess so I'm going to show you uh an En forgeability

experiment and this should look similar to what you would see for a normal signature scheme with a slight twist and that the adversary is able to participate in the protocol so basically we say a threshold signature scheme is secure uh as long as the adversary can't output some forgery that forgery means that the message was not queried to any of the honest signers and the signature is valid with respect to some public key the main difference in this experiment is that the adversary is able to determine which of the parties are corrupt and then it's able to receive secret keys for any of the parties which it uses as long as the corruption is within some threshold here I'm just modeling unforgeability by key

generation Happening by some centralized party uh you can also model this using uh dkg you can model the dkg in the experiment um but here I'm just showing keyen as being uh done by the experiment itself and then yeah throughout the experiment the adversary can interact with honest parties it can query any of these signing oracles on messages of its choosing and then the wind condition as I said is that it should be able to Output some forgery so this is a game based definition of unforgeability I know uh I think Yuda tomorrow will be talking about simulation based Notions but at here I'm modeling this as a game and like I said adversary is allowed to participate as a signer okay so now I'm going to remind you all what schnor

signatures are just really briefly so a schnor signature scheme is just uh a zero knowledge proof of knowledge that's bound to the message via the Fiat Shamir transform so for schnor it's very simple Le uh we generate a key pair so it's just some secret key and the public key is the generator raised to that secret key to sign the message we sample the kns at random and then we generate the commitment which is just the generator raised to that kns challenge is the hash of the public key message and commitment and then the response is the nons added together with the challenge and secret key and then for verification the verifier red derives The Challenge and then they just check in the exponent that this relation holds so the verifier receives the public commitment r um the

public key and the challenge and then they check that in the exponent Zed uh satisfies this relation for the committed values do you know exactly what patented about this idea that is a really good question um is it actually F did he patent something he he definitely patented it um I don't know if it's proof of knowledge it it might have been how the nons is used given how the structure of ecdsa is different um so if I had to guess it had to it must have been this like linear check given how like ecdsa you don't have that same linearity um but I've not looked at this

I guess sorry to repeat the question for those on Zoom uh the question is do we actually know uh what schnor patented in terms of this check okay so um yeah so I just reminded you what schnor is so the main challenge when you're designing multi-party schnor signatures there's actually two so the first challenge is how you actually share this nons and the Second Challenge is how you share the secret key and when you look at these different types of schemes the differences between the schemes really comes down to the strategies that they take for these two different questions um I'm not going to focus too much on how the secret key is shared I'm going to focus more on how the nons is shared and I'll just show you one strategy for how the secret key could be shared one strategy again for those of

you who are familiar with Shamir you can you can tune out for this but for those of you who are not basically uh what you could do for sharing the secret key is you can generate a polinomial where this uh constant term is the secret key each party will then just get a point on that polinomial associated with their identifier and the public key will just be the generator raised to the secret key and each party will get their secret key share where that share is a point on the polinomial and the public key so right here I'm just showing you plain Shir secret sharing but where the public key uh is the generator raised to this constant term and this is used in many of the schemes that I will talk to you

about and then just so all of us have notation uh later I will show you this implicitly but to recover the secret key we just do polinomial interpolation where this uh Lambda I is the LR coefficient so just to interpolate we take at least uh t+1 points and we use lrange interpolation to interpolate to the secret key so I just showed you how you can do key generation in a centralized manner you can do all of this using a dkg I'm not going to show you how to do that but it is uh something that we can do and we can talk about it more later if you'd like basically the main difference with the dkg is no party knows the corresponding secret key okay so that's background for those of you

who are not familiar with this area of work so I'm going to talk to you about the past a question I have gotten quite a lot or at least I used to get is why are we looking at multi-party Shor signatures now and I think that's a really valid question to ask given that schnor signatures have been around for a long time and I think like some people have said well schnor signatures have been around for a long time why don't we have good multi-party schnor signatures now and um something that obious said that I want to highlight is that well here this is actually where we're running into the issue of patents schnor published his paper in 1990 and I we believe the patent came out in 1991 and really this delayed a lot of

research in this area and it is the reason why we have eastsa and I really like to highlight this because it seems like a lot of people who are newer in the space don't actually know why we have ecdsa and the they don't really fully appreciate I think the complexity that ecdsa introduced into the EOS system so I do want to highlight the fact that is because of a patent um and yeah now we're just starting to see the reemergence of schnor and that's why a lot of the research that we've done recently which you know could have been discovered a long time ago I think was just no one was really paying attention to the space so but I think a lot of the reason people are paying attention to this now

as well is because um right because uh Bitcoin is starting to move or I think they have moved to schnor signatures and then we also have something like the nest draft so we are starting to see a lot more interest in emergence in this space another thing I want to highlight is like something that is said about schnor signatures is that they're easy like and it's an easier quote unquote problem than ecdsa and so I'm going to show you a first attempt of how you might design a schnor signature and this attempt like was done in the literature like myself and my co-authors have made a mistake with this first attempt and it's easy to do and then we'll look at the fixes that were developed around this attempt okay so our first attempt of how you might

design a schnore signature a multi-party threshold schnore signature is you might uh generate the kns so each party might generate the kns and the commitment and then they would send all of the commitments to each party and then they would receive commitments from each party and then the group commitment would just be the product of everyone's commitments okay so super simple the challenge would be the same as in single party schnore and then the response would look very similar to as in single party schnor so you'd have your nons challenge secret key but then we would actually additionally add this lrange coefficient into this relation then all parties would output what I'm going to call Signature shares and to combine uh to get the actual output response Zed

you would just sum all of the signature shares and then the signature would be this uh group commitment R along with the response Zed and this would satis this signature would be valid under the schnor relation check this scheme is secure in a sequential setting so if you're issuing one signature at a time this scheme would be secure but what's interesting is it's actually not secure in a concurrent setting and I think this comes down to the question of security proofs and how do we model security proofs and concurrency there's proofs in literature that only considered sequential security and didn't think about concurrent security and so this bug uh was not actually caught for a long time what I mean by concurrent

security is that you have some adversary which is able to perform the first round of signing many times and it's able to get many of these commitments before it decides which uh signing sessions to complete and in doing that it's able to lead to a one more forgery attack this attack not only influences threshold signatures it also impacts multi- signatures and blind signatures as well so this kind of uh concurrency attack where the signature is linear does come up quite a lot not just in threshold Shore but in uh other linear type signature schemes as well basically the overall strategy to this attack is that the adversary needs to be able to query honest parties for their commitments

before revealing its own commitment so this is like one thing that's necessary for this attack to go through I guess I'll just kind of show this I had some more detailed notes but I'll just show this to you in more detail so really for uh what I'm referring to here is the Ros attack and what the challenge to the adversary is is given L signing sessions the challenge to the adversary is to find some challenge C star such that c star is the sum of challenges from valid signing sessions and this looks a little intuitive you would think that this would be hard to do um but this is the RW problem and it's been proved that

it's actually not hard so the you solve this problem in time relative to the number of open signing queries that are allowed okay so right so basically that's that's what our one more forgery adversary has to do and we know that they can do that with the scheme that I just showed you okay so since so that was the past um so two main approaches in the literature have emerged of how to fix this problem so one technique to fix this problem is to force the adversary to commit to its contrib R butions that's like I would say approach number one and approach number two is to tweak essentially tweak the signature after

the fact and we'll look at both of these approaches next so now I'm going to talk to you about I guess the present and where some of the current literature lies today so this first solution for adversary to commit to its contributions it is exactly what you'd expect so we can take that scheme that we just looked at and again each party generates its nons its commitment but then it generates essentially a hiding and binding commitment to its commitment so here you could just hash the nons the message and the signing set and then each party will issue this commitment to all other parties so they're not actually revealing their RI they're revealing a commitment to it they receive it from everyone else and then

they open and receive the openings from everyone else okay so this is just a plain commit open protocol and um here I'm showing you some work uh so this reflects a scheme that I worked on called Sparkle similar techniques have been used in a scheme called zeros um a scheme by Yehuda in a couple years ago and a scheme by musig before then so why does s need to be included in the ash yes that is a good is that a technical there's an issue for that or is that like session ID um we needed it for the simulation um basically to distinguish which session but I mean if you had a session ID wouldn't that be enough

because so at least for the way we proved security you need to program and if you didn't know uh the S and you only had the message then the adversary could query across different messages but different signing sets and and so the the commitment R would change for example no yeah so I know so what you just said there sounds like if you just had a session ID for each signing session oh sorry then that would be suffice that would suffice to distinguish essentially the different that yeah I think that could that could work um in general the feedback I've heard from Engineers is that session identifiers are hard to enforce so here instead of using session

identifiers we use the message and signing set um it is true that yeah with like a unique counter you could probably get around that um when I've talked about session IDs with Engineers there's generally the question of like how do you enforce consistency how do you but doesn't the adversary the adversary can create several sessions with the same set right mhm and somehow you don't have to you don't need a different Oracle to program from the it's the it's the combination of the message signing set and the kns and all of those things together we're able to to simulate um yeah I can I can go over the proof I don't go over the proof in too

much detail here but there there are differences in when the message and signing set are sent so in some proofs you can send it in the first round for adaptive security we had to send it in the first round if you have static security you could only send it in the second round for example so basically with the scheme it is nearly identical to what I showed you however we just have this commit and open strategy okay and so with this we're able to get concurrent security so basically this is a secure scheme it does have three online rounds and it's not robust so it is a step up from what I just showed you but there's some disadvantages as well the next strategy you could do so if you don't want a commit reveal strategy the next strategy that you could do is

essentially use a tweak we know how to describe this now after we designed Frost but when we designed Frost we didn't actually understand that's what we were doing but really like this is a strategy to tweak the signature in a way that the adversary doesn't have control so basically for frost what we do is instead of generating one nons we generate two nonces and then we generate two commitments to those two nonces then uh instead of committing to those nonces and revealing them we send those commitments directly in the clear and we receive them from everyone else so essentially you're just sending T PS around then each party uh deres a hash of the public key message uh the commitments from everyone and then this

I and this tupple here is the identifier so you're also hashing in essentially the signing set so really what you're doing here is you're hashing in everything that was in the transcript of the first round the commitment is then the combination of each party's commitments in conjunction with this hash which serves as The Tweak and then you derive the challenge in exactly the same way as single party schnore and then the response uses both of these nonces in conjunction with this tweak uh and again the challenge secret key and the lrange coefficient combining and verifying is again exactly the same so we just sum everything up and then the uh verification is the same as in single party schnore so in talking to Engineers about the scheme the reason why they

like it so the reason why it's appealing to them uh there's a a few things that they like over other schemes one uh the first round can be batched so I do know of implementations that do batch the first round um another thing that they like is the fact that the first signing round is agnostic to the message in the signing set so you could start the first round if someone doesn't reply or I don't know maybe one party has run out of nonces you don't need to restart the protocol at all you can just continue forward with whoever is available so these types of uh features actually differ between some of the other signature schemes and so I just want to call that out something that is

desirable in practice so this requires maintaining State across signing sessions right yes so that's I feel is it okay okay or I don't know what so it's we will actually get there yes so yeah um yeah that is a great so I'll repeat the question the question is or the comment actually is that this requires persisting State between signing sessions is that okay and I think ideally no so I think um and I'll talk about this in a little bit but ideally that we wouldn't have that state so it is used now but it's not something that I guess is necessarily desirable so I I I'm assuming you'll talk about it

but how does this get around the this Ross attacks like what's the intuition yes um that is that is interesting um I don't actually so the intuition is a little hard to think about um I guess some intuition is whenever C changes whenever what ever goes into C changes uh this a also has to change so everything that's in this challenge the public key are in the message if the adversary were to say like try another set of commitments this a completely changes and I think it's

that interplay between these two that like intuitively means that it's secure so in the scheme that I showed you before where it's just um R plus C * the secret key time Lambda the adversary would be able to essentially take the honest party's commitments and then try its own commitments in a way that wouldn't actually change the honest party's signature except for the C so yeah so R depends on the message here the Big R that the non statuse for signing isn't fixed the message changes it I guess that's one like very syntactic difference okay got so adversity cannot uh cannot see like

the r is R1 r i * SI to the A and A is a hash includes a message yes so the previous thing you could basically the adversary could start a bunch of sessions and have all the RS listed now those are fixed and now you can mess around and pick messages okay ah I see okay so basically the are the you can precompute the RS the RIS and the SI but then what gets used is actually message dependent and therefore there's no way to sort of use that up in an attack yeah I see very nice yeah yeah we don't have like a formal argument for that like the proof we have a proof and it goes through um

so I I can talk about the proof um we're trying to formalize what this intuition actually is it comes up in other areas so like for example right now we're trying to prove the Adaptive security of Frost and we need other proof techniques basically we need a straight line proof technique and with that we actually do need something more rigorous than when the C changes the a changes um so but it it's like a funny thing I think uh we're we're working on trying to formalize this more right now so yeah so I guess like nice so we have something that's two rounds uh it solves a concurrency problem but it's not robust so that's one of the downsides of frost and one of the reasons that have

led to some of the work that I'll be talking about next I can talk about the security proof a little but just sort of highlighting how these schemes differ from each other so the commit reveal protocols have three signing rounds but they're also able to be proven secure under more standard assumptions so um UA scheme is proven under schnor with aborts under simulation based notion and then we prove Sparkle which is a three round scheme under discret log and random orical model uh for Frost and its variance we need an interactive assumption so we do need What's called the one more discrete logarithm assumption which is an interactive which is an interactive

assumption uh I will talk about the lower half in the next few slides so just to kind of like show you this reduction I'll talk about it very briefly so and I'm showing here this a uh so this is algebraic one more discret log in the when when we first wrote the proofs we wrote the proofs under the one more discreet log which is a non-falsifiable assumption the algebraic one more discret logarithm assumption is weaker um and so in our submission to Nest we're writing the proof under aom deal so this is a work in progress but basically the way the proof works is your reduction gets l+ one discrete logarithm challenges and the

goal for it is to return l+1 discrete logarithm solution but you also have access to this discret logarithm Oracle so you're able to query this Oracle on a group element and receive uh essentially the the discrete log of of your query and for our reduction we use that Oracle in order to simulate signing so that's how we're able to simulate two round signing by using this discrete log Oracle we haven't written an impossibility result that you need interactivity in order to have this two this like two round proof but I think I suspect there's an impossibility result but I haven't gotten there so yeah so

basically that's how we use this interactive assumption is to simulate signing can you go back to slides when you said it was one offline and one online uh is isn't this like the first two messages are completely independent of the so that's what you mean the so yeah so you could perform this first message in a batched manner so you could send out many many commitments at once and it's not associated with any message or signing set okay so this so my question is about what applications where that works out so in practice all of these will be different servers and when you have to sign you know some server will get the message and have to

distribute it to all the other signers anyway so that's like signing is always going to be like first you need to send a message to all the servers and then all the servers send something back and maybe that Central party can reconstruct a signature now so it's always two rounds um you could always send this first round in a batch and then I understand that right so the first two yeah so everybody sends some message in batch that's great so this and then you output the signature share so that's however like in practice so if you do the batching we all have distributed that first message now I need to know the signature and I don't know it so and in in any the signer the the the yeah the the threshold parties uh why do they need to

know the output signature no they need to know the message uh the message can come in this second in this part in this round here so I would get oh sorry this is this is a typo um I should have so in this second Arrow I can receive commitments from everyone else and the message so the message doesn't need to be known until after at the same time as I receive commitments from everyone else so I when I'm generating my nonis I don't need to know the message no no I totally understand that the so the first step is before any of us know the message we all send our R1 messages and that back and forth is really just everybody broadcasting to everybody else

R1 S1 right okay but now in any system now we're all waiting around for the message presumably it's like some one Central server gets the message that needs to be signed because some users requested some signing then that Central server has to broadcast to everybody this a and then everybody then responds to that so like what I'm saying is the modeling of this the the the thing that you need is not a oneline offline signing but actually in practice you're always going to use two offline messages two sorry two online messages the first is I need to receive the message because I don't know it and then I have to respond to something so it's exactly what you said in that message when I receive the message

presumably I can also receive something from at least the central machine the central signing thing and then I have to respond so the optimal threshold signing should be something you have an offline message and then you receive something online and then you send something back and the that one party can reconstruct so the way that I think this is used in practice is there's a central coordinator yeah coordinator okay so the coordinator will query parties for all of their commitments and then the coordinator receives the message to be signed oh oh I see okay right so it's not all to all essentially that diagram is everybody sends their R1 S1 to the coordinator yes sorry yes the

coordinator then sends one message to all the parties after it knows a the message yes and then everybody responds to the coordinator okay but still that's three exchange or that's like one two three right yeah I I don't show the coordinator here oh so it's not really batch wait yeah I I can draw it out basically the way that I think this is used in practice is you have many signers and you have like a central server which is a coordinator um the coordinator orchestrates the first round where all parties publish their announces to that coordinator the coordinator has some message sent to them you can think of it as like an orchestration server coordinator has a message sent to them

and then the coordinator takes that message and the commitments it's received and it orchestrates the second round then it performs the aggregation itself and it outputs the signature okay so the way I count that is one offline message because everybody sends their R1 S1 to the coordinator then first online message is coordinator sends M to all the parties and then second online message is everybody sends a message back to the coordinator but that's three rounds in total one offline and two online yeah okay yeah I mean we that that same logic would apply to all of the other schemes I'm talking I totally agree but I'm saying yeah that's fine is there a model in which that your protocol is actually better it's actually one online and

somehow magically if everybody if there was a situation in which you knew what the message had to be signed then it would only be two messages but I can't think of something in practice where that can actually lead to a benefit yeah that's my question I'm not sure but I would love to talk about it so um yeah it's true we didn't really kind of yeah thinking about like the external architecture of like how I'm doing like the simple modeling here but it's true that maybe there's other architectures where and other use cases were be more efficient the thing is you pay so you have this nice feature which is it's only one message online however you pay for it with this one more discret log which I suspect you're right there's no way around that if you're only going to have a one message reconstruction

protocol so that's what I'm saying you pay for that and then can you think of a situation where that wins out yeah well I think pract so I can kind of at least highlight practically where people do seem to want to use this and like it is useful for them so yeah so I guess kind of like continuing where we are in the present so uh as I told you we've written uh this is an informational draft for frost it is not a standard um so yeah so we have this informational draft for frost we started let's see in 2021 and it's gone through 12 versions since then um and we're finally almost almost done so for any of you who are interested in standardizing

your cryptography it takes years and many iterations but you do eventually arrive at the end so we've finally almost completed this Saga Chelsea can you talk a little bit about the process like how it looks like and what's involved yeah so um so myself and my coauthor Ian did contribute to this we didn't just like throw it over the wall to Engineers um we we helped uh write this draft um but basically it was us and then like working with Engineers to take everything that was in the paper and codify it in a way that's uh more specific so we have everything I didn't write this part of the draft but there's things like Cipher Suites in there how you hash uh basically like the order of hashing like I don't know diagram like

more in-depth diagrams basically um so for cfrg they're a little less strict about what goes into it right now we're working on the nist draft and that requires a lot more effort and in-depth kind of analysis but for this it's it's basically so that an engineer could take this and Implement without having any questions about how to do so and what goes next uh when you when the draft is ready uh you submitted for review or you participate in meetings where voting is happening yeah so we just got the final review so it should be published as an informational draft soon um but it I think it went through like 10 different rounds of

review so it took a while I guess in conjunction uh the zcash foundation has written their own specification about how they use Frost in practice and so they've implemented Frost and now they're starting to work on developing wallets that use Frost and starting to use it within the ecosystem I want to highlight really quickly the team we have for nest and I guess like one thing I kind of want to say in terms of what I've learned as someone who worked on the initial protocol and then has like worked on standards since then and had people use it in practice and like the one thing I really want to emphasize is this is not a one or two% effort a lot of people have contributed both like in the follow-up papers on Frost who have

looked at the protocol and helped uh form like even better formalize the security proof and Notions and um and like right now we have a lot of people on our nist submission team spanning many different organizations so I think something I just want to say in reflection is like it's fun to write papers but really to like build and deploy cryptography for the long run it's been a lot of like building Community working with people who are you know experts also in the field and kind of building a coalition and that's something I think we've we've done pretty well and this is this is very much like a team effort so I just want to highlight some of the people on the team who have been contributing and

helping lead to this as well so this is a fun slide uh so this is where I know Frost is being used in practice uh every once in a while I like go to GitHub and I you know try to find repositories that use it there are people who have or organizations that I know that use it internally that I can't talk about which is unfortunate um but yeah but we know it's being used in practice so like one thing is called Frost snap so they're developing Hardware basically like Hardware backed wallets and um they're using Frost so um Frost is deployed on a satellite for crypto sat which is kind of fun they like the low latency for frost um I can actually show so that's where they need it but it's that's where they

need so they do two party and that makes it such that they can do one they have basically yeah it's two of two and that's how they can have the one two flow and I can write that out later how they do it but yeah for them uh one round is is very important okay um so yeah so it's been really fun to watch um this being moved into practice and I guess like working with so many people and helping uh arrive at that goal what I want to do now is I actually want to highlight some open problems or things that are developing in this field that I think are really promising so a lot of this is not my work so I will do my best to talk about it um but really I just want to

tell you some of the things that are happening in threshold Sher signatures that I think are exciting and that I think will further continue to move the needle and and how usable these schemes are so I basically told you um a lot of the schemes I just showed you are not robust and robustness is very important for the notion of liveness and so especially in settings where you have a lot of servers or you need liveness and order to do something like consensus um having robust schemes is very important there's been some really interesting work in making uh threshold schnor signatures robust so one scheme that's been worked on is a scheme called roast so it's basically just a wrapper to frost and it runs like simultaneous

signing sessions using Frost but some more recent work that I think is really interesting is a protocol called Sprint so Sprint essentially allows for performing many signing sessions in batch what's been shown is that if you use the frost technique of essentially using these two random nonces you able to get uh concurrent security so I think you can either use Frost or you can use a Randomness Beacon but if you don't want to use a Randomness Beacon basically the tons trick plus Sprint allows for concurrent security of Performing many signatures in parallel so yeah I just want to kind of like quickly highlight some work that is being done that I think is promising and um it it would be interesting to see

like how much more performant these schemes could be another thing that I think is important but is a hard problem that doesn't have a really really clear solution is the idea of statelessness so the schemes that I showed you before are randomized so they require every party to keep state in between these signing rounds and something that would be quite useful as a countermeasure is instead having deterministic schemes that doesn't require this kind of steping so just to like motivate statelessness a little bit more so for yeah as I basically told you for something like frost all party sample Rand at the beginning of the protocol and then they

have to P persist that state all the way to the end and the state is very sensitive so key recovery attacks are possible if the state is reused for example so it's very important that the state is persisted carefully and correctly and for engineers that means you require locks and careful deletion and that's like a hard thing to do in practice there has been some work done in stateless signatures and I'm going to talk about some work that I did recently there's other work that has been done as well and I would sort of characterize it in terms of efficiency um so there's some schemes that yeah I guess I would characterize as a little less efficient

that have used snarks or generic MPC and then there's some work that I did recently that doesn't use either of those but there's a trade-off and that it requires honest majority so in this landscape of what we have for uh stateless signatures I I do think that there's kind of an unsolved problem about uh what is the ideal scheme without having to make some of these trade-offs so what's your uh what's your vertical access what's on the left and on the right versus in the right oh sorry so randomized and stateless sorry yeah so just to show you like there's been a lot of work done on the randomized side but on the stateless side there's not quite so many and I

think um hopefully we see more actually this has been done in practice so I'm going to show you an attack and this is actually someone who's an auditor told me that they had seen it so it's kind of fun to highlight so one thing you might say is well why don't we just take something like Frost and make it stateless by using this threshold EDSA trick and basically what this trick is is instead of generating Don Nots at random you hash the message in the secret key and we use this for threshold EDSA in order to prevent issues from Bad randomness but one question you can say is like okay why don't we just take something like Frost and generate the nons in this way but yeah we can't do that because it is insecure to do so and the overall

intuition is that basically the adversary can deviate from their protocol and it can pick its nons at random and it will lead to a key recovery attack yeah so it's fun to say this because like implementers have done this so I like I try to get the the good word out and I guess just like running through the way this attack would work for those of you that are interested the way the attack works is you have a corrupt party and they would just run the first signing session honestly so they would participate in the signing session without deviating from the protocol and then in the second signing session they would just all they need to do is they just need to sample their nons at random so that's all that's needed for the attack to go through the

reason why is is because their commitment will then deviate from the first signing session and the honest party can't actually detect that the first party has deviated from the protocol and what that allows you to do is it allows you to recover the secret key in as little as two signing sessions so I think the the question is can we build an efficient and deterministic threshold signature scheme I think we did that partially with some work recently that I did that's called Arctic uh the trade-off is that it requires honest majority so in some settings I think this might be a useful protocol but there is an open question of how do you get something that is as simple and efficient in the honest minority setting basically for

Arctic we use something that we call a verifiable pseudo random secret sharing scheme um the pseudo random secret sharing scheme is a known trick in the literature that has existed since 2005 and we just use a simple trick to make it verifiable this is where the honest majority assumption comes in but really all it does is we use this vpss to derive the nons and commitment and then because it's stateless we don't need to remember the nonon commitment through the next round basically the vpss just verifies that all the Pary commitments are consistent and then it can rederive the commitment uh with respect to the message and signing set and their secret key and then the group commitment is the

commitments from everyone in conjunction with the lrange coefficient the challenge again is the same as in single party schnore and the signature is similar to what I showed you before so it's just the non challenge and the secret key the only difference from what I showed you before is the lrange coefficient is added to the signature share across both the nons and the secret key so I think Arctic is nice and that it's uh simple and it's fast for small numbers of parties but there is some remaining research to be done here does it if you go back one slide that attack yes so if you just make the protocol when you send your R1 let's say you can use any external snark

to prove that essentially R1 uh oh I see it's a pretty big statement okay yeah so um there's a scheme musing DN that uses snarks to prove um yeah to basically prove that the nons is generated correctly that would solve it there's no other attack let me take a step back um so they use a uh a snark to prove that some deterministic function was evaluated in order to generate their knots so like the trivial ways you you could do the EDSA trick where you hash um your secet key and message and then

you could use a generic snark to prove that you generated your anounce correctly and so that works that that's stat less and also yes robust against n minus one yes so the idea is like how do you do better than that something that I think is interesting is basically what I show you so Arctic is very fast for a small number of parties and then there's some crossover Point as the number of parties grows so essentially snarks has a crossover point with the techniques that I just showed you so for a large number of parties using a snark is probably better for small small number of parties using the vpss trick might be better so that's kind of the tour of uh where we came from with threshold schnor a lot of the work that has been going on

and some things that I think are really interesting that will make the deployment of threshold schore signatures even easier and hopefully solve uh other real world problems so the main takeaway that I think is important to know is threshold signatures are a useful mechanism and especially when you want to think about Distributing authorization randomized threshold signatures are in use today and they're undergoing standardization so stay tuned for that and I think a lot more work like hopefully we'll start to see threshold signatures deployed everywhere but I think robustness and statelessness they are obviously very desirable properties but they're harder to achieve and we're starting to see some really nice research in this area and hopefully more in the future again stay tuned there's been a lot of work

done and hopefully we'll see more a good question uh curious if you looked at the prevalence of schnor signatures in Bitcoin the people start using it more or still stick to ecdsa you know anys um what I've heard heard is a lot of Engineers want it to be used so sorry the question is um have like do I understand how the transition to using schnor and Bitcoin has been used or like how's it how it is going and I personally don't know but I know a lot of people want it just because deploying threshold Shore signatures is easier um but I think the not it's not going as fast as I think we want but for other

people other people who are in the space might know as well so Bitcoin Community is very very conservative they don't want to change anything any change to bitcoin is very very very slow it's very different culture to the ethereum but still they now support schnor as together with ccbsa so they know support schnor signatures transaction if they work Conservative then they would be using schnor to begin with conservative in a different sense not in not in not in our notion Bitcoin Bitcoin hardcore Bitcoin people don't want to change things cool thank you [Applause]