ZK7: Dancing in the Dark - Thor Kamphefner - Entropy

Transcript

[Music] so yeah um uh maybe we just hang out and let people trickle in and give it like a good 30 seconds of hysteresis here um so we just don't hang out we're going to do a little dance while we wait um yeah so this is like my first real talk so a little nervous but hopefully i'll convince you of some things talk's going to be sort of at a reasonably higher level than the last talk um i'm going to sort of introduce you some primitives and i'm going to try to introduce you to a scheme to do distributed key generation which is based on chamira's secret

sharing um and the scheme comes out of the gennaro goldfitter 20 gg20 which is a scheme for threshold signatures or ecdsa threshold signatures so cool i'm going to kick off so yeah i'm thor i do cryptography stuff at entropy i've been working on implementing a scheme for entropy um for about the last month and i'm going to tell you about it so we're going to talk about ecdsa signatures we're going to kind of take it from like the base primitives sort of introduce them and get you to hopefully by the end of the talk understand sort of how dkg works so there is a blog post that i wrote

that you can follow along if you scan that qr code and so this talk is going to be like maybe two levels higher than the base paper that blog post is going to maybe like one level higher than the base paper and then if you really want to understand everything and it's sort of like gears level go read the paper so i'll leave that up for another couple seconds and there'll be another chance to scan it later if you didn't get the first time once we enter the math section of the talk at the end so um what you might ask come on in guys um yeah what you might ask is an ecdsa you probably this this room is probably cryptographically literate but just for

the sake of completeness i thought i would include um like just what are some primitives um and so what you might ask is an ec dsa it is a signature scheme with two protocols you got sign you're going to sign with your secret key and some message and produce a signature and you're going to verify you're going to verify the signature that you produced and get some boolean results so if alice goes and signs something and bob wants to say was it really alice if alice signed it with her private key then good news bob says yeah it was it was definitely alice and if not then of course we say no all right so the signing protocol alice brings her private key signs a message produces a

signature bob he verifies the signature it says yes dat alice or no that not alice and with that we unlocked the technology we unlocked multi-signatures um pretty much all multi-signature is it's a trusted verifier um like wells fargo um that says we trust you wells fargo please tell us if um say two out of the three people that we care about alice bob and carol if two out of three sign a message and send it to wells fargo or trusted verifier then yeah go do the thing send the transaction do the do the whatever and we trust wells fargo to do this but if we if we do one other thing like invent blockchains with smart contracts we can actually rip wells fargo out and

put a smart contract in there which i think is sort of the thing that most people in this room probably think about when they think about a multi signature um so the things that sort of like make sense um to use multi-signatures for things that are good about them so we got from ecdsa to t of n uh signing where like instead of just one person signing a thing we get t people signing a thing out of n so that's sort of some neat flexibility for if you wanted to share um custody with some other people or share like the right to some the ability to sign and if we take wells fargo out of the picture and put a smart contract in it's trustless um since we wrote the code and we know it's running on chain um we know that we

can basically it is trustless insofar as you are not trusting the code um or and it's really simple it's ridiculously simple you just say okay did enough people do the thing or did did enough people sign a transaction and submit it to the multi-signature if so do the thing and last and this is kind of a crucial feature that we're going to drop in a couple minutes it's offline meaning that alice and bob don't don't both need to be online when they're doing their uh signature submission um they can be like one day later or whatever what's lame about a multi-signature is it's space inefficient and it's verifier inefficient um every signature needs to be verified

of those t signatures that were submitted they all need to be stored on chain so um we're going to store a bunch of stuff on chain we're going to store t signatures for every signature that's produced um so how do we do better more cryptography always more cryptography the answer was always mark cryptography um so um alice uh bob and carol would ideally like to um produce only a single signature and then um we we only have to store and verify a single signature um to basically get all of the stuff that we cared about um and so that means that the chain only does one verification and

one signature story which um space on chain and verification on chain is sort of expensive so this is great if we can figure figure out what to put in that um question mark then we solve space inefficiency and verify inefficiency we have a new problem um we have a new problem and the new problem is that with a threshold signature um we basically have to lose our online property alice and bob need to be online at the same time i'm sort of going to introduce you to one part of the two new things that we need to build a threshold signature which is the key generation step so in the threshold signature scheme we

keep all of these properties we lose simple implementation and we solve space efficiency and and efficiency to create our signature and so we're going to do some secret sharing i'm going to kind of do a quick touch up on reminding you guys what a secret sharing scheme is for anyone who may not quite remember in the scheme uh we need alice who has some secret u maybe it's her private key or maybe it's like a group private key how can alice construct shares of her secret um so that this group can reconstruct the secret with say two out of four of the shares so you might think about this sort of question of like okay so what could we possibly do so that we could distribute information between

alice and her friends such that any of them can reconstruct the secret and a natural answer um is you let's use polynomials because we're mathematicians and we like polynomials they're great they go up they go down and if you have at least some points of your polynomial you can reconstruct the polynomial but if you have anything fewer than that number of points then um you come on in um if you have anything fewer of that number of points then you will not be able to reconstruct the polynomial and you convince yourself that that's true by saying let's take a degree one polynomial which is a line if you only have one point on the line you're not going to get the line

and so we're going to use this sort of neat mathematical fact to reconstruct secret sharing um and so how how is that going to work um well if you remember your linear algebra classes um or perhaps lagrange interpolation you might say well we're going to need any two points on this line to reconstruct that line and a third point won't tell you any more information about the line because you already got the line but less than two points you didn't get the line same thing's true for like a parabola you need three points on your degree two polynomial or parabola to reconstruct the parabola and the sort of robust formalization of how to do this for arbitrarily arbitrary degree

polynomials is called lagrange interpolation but it basically just means do this thing reconstruct the polynomial so we actually now have um unlocked shamir secret chart which basically says the thing that i just said if alice wants to do 204 secret sharing we're going to take a degree two polynomial which means that you need three points um there's a bit of a naming collision that happens here two of four means you need three parties um but it's a degree two polynomial so um be aware that there's like some argument about that naming process but um basically we now have the way for alice to say okay i've got my three

friends i'm gonna send them some points and uh my friends can now do uh shame your secret sharing and share the secret you um why does this suck for uh constructing private keys if we're gonna use the or constructing key shares if we're gonna use this eventually for like a multi-party signing scheme where like we ideally want all of these parties to like not be able to guess what the other secret shares are um it sucks because alice knows what everyone else's secret shares are which is great if we like think alice is the only person with anyone to lose but lame if we're like maybe maybe we could do a little better so alice knows everything that's that's no good

um [Music] so it's time to do distributed key generation which is sort of the whole point of this talk um so i kind of hopefully up to this point you've been convinced that distributed key generation is sort of the answer of like how do we get a bunch of parties to have secret shares without any one party being like able to like know what everyone else's secret shows are and we sort of have the elements that we're going to use to put together our dkj as it's constructed and in our golf letter twine and for the later rivals we have this wonderful qr code that you can use to scan for a blog post that i've written to accompany this talk that will explain the scheme at a slightly lower level than this talk and if you really want to understand the

scheme you should go to the paper so this is like talk is like two levels above blog is one level above blog post is or sorry paper is the paper so um it might help because we're about to go into math world and math world is good but hard to present through slides but we're gonna do our best i promised yeah okay so we're going to introduce a table because that's the best i can do uh communicating some stuff that's about to happen um because there's going to be a lot of parties so these are going to be players 1 through n

and players 1 through n we we want to arrive at a situation where players 1 through n have evaluations some points on a polynomial that they came together to construct as a group but if they just all say we're going to all pick the polynomial together they'll all know what the secret is so we lose we want them to all end up with a shared secret that none of them knows but everyone has evaluations of this polynomial form so they're all going to start by picking temporary shared secrets and these shared secrets um are going to be i don't think i quite explained how this thing works by reconstructing the line their shared secret is going to be wherever it intersects the y-axis so if we plug in f of 0 we just get u so

we hand out evaluations of this polynomial so person one gets f evaluated at one person two gets f evaluated at two and that's how we're going to go about it all right so everyone picks their secret their temporary secret u1 through un there's gonna be n players and we're going to have them commit to a hiding and i'm kind of going to skim over a bit about some of the checks in the scheme since i think they sort of distract from the scheme in general but if you'd like to know more you might check out either the blog post or the paper and then i'm going to introduce some notation we're going to do a secret secret sharing scheme which i'm going to denote ss of our secret this temporary secret we chose

and some evaluation index c we're going to denote our polynomial like this and each player is going to pick random coefficients for their polynomial and they can do that because we really only care about where the polynomial intersects the y axis which they already pecked so everyone's got in their head some polynomial with their secret and some random coefficients and they're going to evaluate it there are n players they're going each player is going to evaluate their polynomial end times we're going to evaluate a polynomial evaluated at 1 polynomial of 2 polynomial blah blah blah and they're going to denote that as lowercase s is the evaluation of their secret sharing scheme and they are going to send it to people

so they go say player one goes and talks to players two three four and so on and so now what everyone has they know their private secret they have their polynomial and they have the evaluation of everyone else's polynomial at their index so if i'm player one everyone else has a polynomial in their head and i have the evaluation of everyone else's polynomial at the point at the evaluation point one and we've actually we've gotten there um we now all have evaluations of a polynomial we have our secret sharing scheme we're

actually done now after we add all of these points together and assign that to our personal point and i'm now going to prove to you that we've actually we're done that's it so we're going to say person one is going to add all of the things that everyone else sent them and they now have the evaluation of our new polynomial at index one the way that works is x is the summation of everyone else's points at one which is actually the summation of everyone else's temporary secrets u1 through un plus the other stuff we're going to take the

randomly chosen coefficients times 1 to the 1 plus blah blah blah plus the other the teeth coefficient times 1 to the t that's true for for everyone so everyone actually has now arrived at a secret sharing polynomial for their uh for their shared secret but no one has the shared secret um which is the summation of all of their temporary share the temporary secrets um and if that clocked great and if it didn't clock there's a great write-up of it in the blog post that was shared at the top that's pretty much the talk so thanks for coming it was my first

time talking um [Applause] i think we have time for questions do you know anything about that yeah so the question was that um the paper was recently updated because alpha rays published by omar shlomoveds noted that several implementations of the scheme basically neglected to do one of the checks that the authors asserted

that they had stated but they stated it um i think in a footnote or in such a way that many of the implementers did not did not add the check into their scheme so a lot of these implementations would were in fact vulnerable um so that has to do with the check that i did not describe in this talk um but it involves a range check on one of the parameters such that there wasn't an overflow in something called the palier modulus which palier encryption is a neat thing that we kind of brush over in this talk but to understand this game in full you need to understand what's called an additively homomorphic encryption scheme using the pali a homomorphic encryption

scheme yeah yeah i was going to ask you so you use the pagia homework encryption scheme to actually build the signatures at the end yep what are the requirements or like for the network layer like assumptions like pki or broadcast and stuff and like are you using those and are you able to identify identifiable awards during the dkg phase as well yeah we are able to have identifiable boards um could you clarify what constraints in the network layer you quite mean uh like

for a reliable broadcast or like existing public key infrastructure so you can like sign messages between the parties yeah um so we haven't quite decided um on exactly what networking paradigm we're going to be working in but we've basically been evaluating two models um one in which we have like a sort of like person that is supposed to or some of the nodes in our system are going to be sort of like broadcast to nodes and the other is where the nodes just talk to each other individually but i don't think we're sort of the jury's still out yeah my question simply this title talking to but this um generation this would keep your

insurance yeah that is a fair criticism i i kind of realized in retrospect that there is no part of this that is actually ecdsa specifically uh you mentioned vls at the beginning uh i don't think i did but what's your question no i mean i then i was wondering what's your relationship if didn't uh what's my relation i know about it no what's the relation of the protocol i claim that i did not mention bls and i claim that i know that vls exists but could not explain it with any level of technical depth

of signing would be that's much easier than using yeah um ecdsa is sort of known to be kind of harder to do threshold signing then schnorr or eddsa um and i think bls is also reasonably easy if it's not also the same as one of those but i'm not entirely sure because now my knowledge is gone for one more question all right thanks for coming in i hope it was informative [Applause]