A whirlwind tour of threshold signature schemes / Thor Kamphefner

Transcript

foreign hello everyone I'm Thor there are my slides um yeah welcome to talk it is a cryptography talk and the math will be screwable I hope um we're going to be talking about threshold signatures today which you can download a free blog post on that I

wrote about a month ago in particular that blog post will cover a thing that I'm going to kind of brush over which is the key generation step of threshold signatures so there will be another chance to get that blog post at the very end of the talk but first type uh we knew a thing up to her about hype we cryptographers made cryptocurrencies possible and so I'm going to briefly hype cryptography cryptography is really pretty pretty neat um because it allows us to have trustless assumptions that don't need to be like second guessed well you have

mass and it also lets us make great memes on Twitter about the unsecured ports that we use above 8000 we should only use primes above 8000 because cryptography it's a joke um so today we're going to learn what the heck is a TSS a threshold signature and we're going to run through a couple of them ecdsa kind of hard mode snore less hard mode BLS a doge with a hat so a TSS is three algorithms um well abstracted it is a distributed key generation step where you and a bunch of other people are going to

arrive at some secret shares which go together into a you can think of a private key yes being composed of those secret shares a signing step and a verification step like I said we're going to basically skip over the dkg step except for just a quick bit um so slowing down here like bitcoin's block time um the dkg step is kind of the um shared step between the three signature schemes that we're going to talk about so um it's kind of useful to understand mentally and it's really pretty simple it's just combining a Schnur secret sharing or sorry a Shamir sneaker sharing and you get to a dkg so not TSS if we have kind of a

multi-signature model we want Alice and Bob to be able to produce two signatures and that kind of sucks the verifier says Nah because he has to verify two signatures he'd rather verify one signature and he says yeah better for him so how does he do that well we need distributed key generation so we could say let the shared secret this is kind of analogous to our private key before be the sum of S1 and S2 which are Alice's share and Bob share and then maybe we want more than two parties maybe we want several parties well we

let Carol end and so maybe we say we want T secret shares and we just add them all together and this basically is like the concept of so if s is the private K and we want to reconstruct the private key in some way then we want to do some operation over everyone's secret shares such that we get the private key back but no one gets to hold on to the private key because they never saw it in the first place um and so this scheme kind of sucks because we have to have all T of those uh s's but if we did it better we would have only T of like a broader set of like n essays so that you only needed like some

threshold out of the total number which is basically what you do with a multi-signature so you want to get actually S Plus some other things sorry s equals S1 up to St you want to recombine those into a share using dkgs and streamer secret sharing which is what the blog post is about onto distributed key generation when we get that we've got our T of n signing and we've got our we want to move on to signatures creation which I'm going to present three different ways that we can construct signatures after we assume that everyone has their own secret shares additive secret shares so now we hit ecdsa

so ecdsa is kind of hard mode the algorithm for ecdsa uh uh basically looks like that you sign you get a message you got a secret key you verify you got a message you get a public key and you do that and I'm kind of short on time so otherwise I would let you look at that and maybe talk about it a bit more but bye um the best of Best in Class recent ecdsa stuff is GG or cgg mp21 but really the only like actually not trash threshold signature scheme ever to first first to be ever was like gg-18 on ecdsa which is like pretty recent

cryptography that's like oh that was recent um and it lets us do uh this stuff this is the other I'm going to brush over a point in my stock because ecdsa threshold stuff is kind of a lot uh I'd have to kind of go through all that to get there so instead of that I'm going to compare it to Schnur or EDSA and BLS and try to get you there if you want to hit up more about what ecdsa is about definitely check out that talk or that paper or talk to me afterwards so I've copped out onto schnoor so Schnur is actually simpler this slide

is simpler you can tell by my face that the slide is simpler um and the reason it's simpler is in particular because of the way we are constructing s so the neat thing about Schnur compared to ecdsa Schnur and e d DSA are the same thing is that we have linear coefficients and we can actually fairly easily split up the Schnur coefficients of s into additive shares that everyone holds a piece of that's why the difference between the ecdsa threshold signature takes four pre-signing steps with this EDD or Ed

DSA signature takes one pre-signing step and the pre-signing step is mostly due to we want to get everyone these uh these linear components there'll be I'll publish the slides to Twitter also so if you want to catch up on that later you can do that but the Best in Class um old world like signature where we're going to get to BLS which is kind of like new world signature um the best we can kind of do with like the old signature techniques is like frost which is the Ed DSA paper published in 2020 which has one round of pre-signing and one round of signing compared to cgmp which has somewhere between four

and seven rounds of pre-signing and one round of signing depending on the protocol you implement and so Schnur signing basically looks like this we need to take everyone's private keys in a sort of sneaky way where no one else gets to learn what everyone else's private keys are and each player does the following they retrieve some random information that they did they got in their pre-signing round which I'm going to kind of brush over they get some random information and they compute uh the group the the compute what their adjustment for the group they are so they could actually be out of a group of n they

could be any T players in a group of fans the lambdas there are the adjustments for the fact that there are any T players and they broadcast z i and z i is the sort of partial of the total signature and at the very end the signature is just the sum of all of their partial signatures and this is pretty elegant because we kind of get to say hey everyone all we need to do is agree on some random nonsense beforehand in our pre-signing round take one round be great and then we have an O of n operation to get to a final signature a threshold signature something that we needed to be verified because at the end of the day a

transaction is just a signature I'm not lying the transaction is really a signature yes I'm slightly lying um schnurse signature process is a bit more than I've described because there's also a requirement on some zero knowledge proofs to say each of the players in that scheme needs to get into the others that they did the right thing because if they don't know who screwed the pooch then everyone's looking at each other like who's evil out of us and then you've got like a pointing guns Mexican standoff so we get two BLS I should have convinced you that Schnur is maybe slightly less hard than ecdsa but now we're going to get to BLS which is even

slightly less hard than mature so the question we ask with BLS is what if we got to modify verification in the two schemes beforehand we basically stuck to an already existing scheme which is here's some format for creating a single signature not a threshold signature a single signature what if we got to change our verifier to say I'm going to accept an entirely new type of signature and I'm going to invent some elliptic curve cryptography sounds like fun um so the type of elliptic curve cryptography we're talking about is pairing cryptography and it specifically means one thing we want e we want a function e

that says okay so here's an element in group one an element in group two I want to buy linear pairing between an element in group one an element in group two you could think of when I say an element in group one and an element group two is like there are numbers between one and some prime um that's it and we want to be be able to exponentiate X or Y or all of it and say it's all the same because it gives us a really neat cryptography and there's been a way to do this since the 1940s invented by a guy named Andrew whale so with our new fancy math tool in hand we're going to create some secret sauce

we do a new even simpler signature scheme and we say sign a message hash it and exponentiate it send it and the verifier just says okay so does this pairing equal that pairing and this is there this is really easy because it makes for a really easy aggregatable signature we just say hey everyone multiply your public keys and we'll aggregate them all and have a signature because multiplication in the base

is addition in the exponent I've lied that was that was a lie when I said multiplication in the vase is addition in the exponent I wasn't lying about that but I was lying that this is a secure scheme because we've just combined everyone's public keys and said we got a secure signature and that was a lie because we actually want multiplication in the base to be exponentiation in the base because then we actually have to use our private keys and that's that's kind of important um so with a very simple modification we

say okay everyone needs to choose a secret chair A1 through a t and then we need to pair them and we output a valid signature and that's pretty much it that's pretty elegant and that's why we're talking about using it in ethereum too um so one of the neat things about block validation is that you might like to have a couple validators or a couple hundred validators or a couple thousand validators one of the applications of this is that you can have as many validators as you want it's really easy check their signatures and compute them

so what learn I ask finally what's a TSS it's threshold signature but you knew that why is ecdsa hard because it's old and because Satoshi used it what's what's the deal with Schnur it's less hard but I didn't give you enough time to read the math why is PLS easy does the nice things Aggregates goes together like glue but good what happens when post content oh everything broken unfortunately these guys broken too

this came out last week a multi-billion dollar Quantum Computing company revealed that they were totally lying about everything they'd claimed to be able to do um so um Quantum Computing kind of scary but at least there is bad scammers there as there are here and that's my talk free blog post if anyone wants it and uh thanks for uh coming [Applause] I'm cryptographer on Twitter if anyone missed that last chance for the blog post I can show you later and I work at

a project called entropy we're using threshold signatures to do asset custodian stuff which is sort of like what your multi-signature does and sort of like what a central bank does but in a decentralized trustless way so if you're interested in that at all come talk to me afterward about entropy and uh that's me on Twitter all right see y'all [Music]