Fast Multiparty Threshold ECDSA with Trustless Setup

[00:00:05]thank you so this is joint work with Steven goldfeder at Cornell Tech so the motivation for this work is mostly from Twitter currencies but not exclusively as you most of you are aware spending bitcoins or any kind of cryptocurrencies is controlled by a digital signature and the security of your coins is really controlled by the security of the key that you use the sign and therefore the storage of your secret key is the single point of failure for your system so how do you avoid single point of failures well you take your key and you break it you split it into multiple devices and the standard way to do this is to use what we call threshold signatures where we split the Skee among n servers in a way that at least T plus one of them are can cooperate to produce a signature but T or less cannot sign and actually shouldn't have any information about the key at all so what are the advantages of splitting your keys there are several advantages and the one in the context of cryptocurrencies then the most important one is that a threshold signature once it's been issued looks exactly the same as a regular signature there's a public key there's the verifier and once the senior is produced how it was produced behind the scenes it's completely transparent so this is in particular the main difference that you have between threshold signature and multi signatures where this policy of t + 1 servers needing to cooperate is implemented by replicating and keys and producing t plus was you need to see T plus 1 signatures and apart from the efficiency a concerns that that this double replication creates there's also anonymity related to our the senior ship travel through the network so in this stop we're going to focus on the digital signature algorithm which for those of you who are not familiar it works as I described in the slide there's a group a cyclic group G of order Q a generator G that generates G this is a generic description about DSA works just plug in your favorite group the way bitcoins works is with a group of elliptic input points of an elliptic curve but what I'm gonna talk applies to any implementation of the DSA algorithm so your private key is a random element in Z Q is a random element between 1 and Q your public key is G to the axe which i think is missing from this light to sign up a message m you pick a random nonce which is another integer between 1 and Q and you raise G to the K and that produced the first part of the signature which is R and then the second part so R is a group element the second part of the signature is a scalar is an integer which is computed as K inverse time and plus XR so the secret key comes in the computation of ass and the nonce come in the computation of r ms and one important thing that needs to be stressed is that the value K has to be kept secret it's very important that it's secret because if you find out what K is then you'll find out what access from the second part of the signature okay only all you hear reveal is G to the K but not okay okay so if you ask me 20 plus years ago that I was still working on this problem I would had told you you were crazy I worked on this problem when I was a graduate student this was part of my doctoral thesis at that time the motivation was obviously not Bitcoin was certification authorities nuclear weapons control it was really fun but and yeah we brought this paper we published it 22 years ago I was in my teacher saw what I was done well that is in that paper there's there's an issue so if you share your key with the standard Shamir secret sharing that hopefully all of you are familiar with your shares are a point on a polynomial degree T the free term is your secret key X what happens is that the computational DSA requires a multiplication which is the multiplication of K and X K has to be secret so K is also shared among the parties that are computing the signature together when you have two polynomials that you multiply them you're gonna end up with a polynomial of degree 2 T and the problem is that now to reconstruct the signature you need to have 2 T plus 1 points on this polynomial so we're diverging from the definition that I gave you before where if T is your parameter T plus 1 people should be able to sign and now we had double that number so at that time I didn't think it was an issue turns out that Bitcoin companies were very concerned about the doubling of the server's means you need to really put a lot more servers on on this network also theoretically can we match can we do this threshold optimality and in particular you cannot do to that to other two right because if your threshold is one meaning one person shouldn't sign but two people should sign with my old paper you will need three people to sign so so we would like to have the threshold optimality or also called dishonest majority in which even if you have T people which are trying to forge a signature T plus one people should be able to to sign okay so how do we do that so for the two party case turns out that the problem with my original solution was already identified in the early 2000s a paper by McKenzie and Ryder and then more recently this paper was improved by user Linda and demmer and all in very recent papers again there's been a renaissance of research in this topic because of cryptocurrencies for the general case in which you have tea servers and and parties I Stephen and I and other callers have been working on this and these two papers were really a generalization of the McKenzie a writer approach from two parties to end parties and what so let me tell you a little bit more so okay so there's the secret key X which is a random number between 1 and Q how did we split it between n parties well if this is my key I can generate a polynomial random polynomial degree T put ax in the free term and give all of you a point on this polynomial in this case I'm acting as a dealer as a trusted dealer which is ok because this is my key but what if all of us in this room want to collectively generate this key X without any of us knowing the key acts to begin with then in that case you need to have a distributed key generation product oh and we're bad lots of work done on this in the past as well and there were several protocols which again didn't work for the particular case of DSA with honestly with this honest majority so in this previous work that appear in the last couple of years what we we changed the way we did this distributed key generation phase instead of thinking of acts as distributed we had the Shamir Sigma sharing with this repeated acts by encrypting it under a additively of morphic encryption schemes such as PI a and then distributing the decryption key ok so now the reason you have a share or this key is that you have a share of the decryption key that allows you to decrypt acts now you will never decrypt acts what are you going to do we're gonna use this encryption of X in sort of a domino using your morphic property of the encryption scheme and to end up with an encryption of the signature with an encryption of s and surprisingly the fact that the encryption is additively a morphic it's okay we don't need by adding communication rounds we don't need fully Memoriam captions so what okay so that basically summarized in a slide the previous work that we did the problem was that the one add the Phillie of a morphic encryption scheme that we know is 'piease encryption scheme where this distributed key generation where we all together come up with the RSA modulus and the generator of the PI a group and so on there's a paper you can read it the words there's protocol try to implement it in practice not so much so what we wanted to do was a threshold DSA in which the trusted setup was practical so we didn't want to use this distributed PI a key generation so let me take a step back and show you the crucial two of the we use in this in this paper which then I realize goes back to a very old paper by Nick Gilboa on generating distribute generated another say keys by the way so let's assume that Alice and Bob have two values a and B which are multiplicative shares of a secret us what does that mean that if you take a and B and multiply them together you get us my goal was to go from this representation on the synchronous to an additive representation of this particular so what I wanted op is with two number X & Y such that X plus y is equal to us and Alice knows act and Bob knows what so alice is going to encrypt her share or multiplicative share and that this Paille encryption scheme and sends it to Bob Bob picks around the number M and sits back to Alice an encryption a B+ M this is something that Bob can do because E is a additively homomorphic encryption scheme so you can multiply by a constant by a scalar which is B and you can add a scalar which is M so Bob sends this back Bob shares is gonna be - ham alice's share it's gonna be whatever she decrypt from Bob now a primary plan together is gonna be s right okay so remember that if this shares of the DSA signature key this numbers work modulo Q the encryption of the paiace scheme is another same modulus n so there is a mismatch between the modulus over which were doing your memorial position over pie-ya and the model is over which this shares have to operate so we were going to use we're going to use a very large n which will make sure that there is no wraparound and everything works over the integers in particular if we choose since our numbers are between 0 and Q it's enough to choose our end bigger than doing Q cube to guarantee that no wraparound is gonna happen everything happens over DT but this is only true if the parties aren't honestly if I have a number which between 1 and Q and I encrypt that number and Bob responds the same way then everything is all under Q square so we're fine the problem is that either Alice or Bob can input into this product call a number which is larger than the share and that will cause the protocol to fail now normally this boot a big issue because most likely most likely what's gonna happen is that the signature is going to fail at the end after we get the signature we check the signature fail we say oh well somebody's not honest here let's scrap everything and start from scratch but the problem is that the failure of the signature may be related and we don't have a way to prove it or disprove it to the actual inputs of the Onyx platters so by injecting a failure into the system the adversary may learn some information very limited amount of information about the secret key the secret shares of the honest players so we had two options here to fix this the first one is somewhat expensive and was to add a range proof to the ciphertext that can send into this problem meaning I'm gonna prove to you that what I'm inputting to this particle is small so I'm gonna do a zero knowledge proof that this thing is model and now we're back to numbers being small no backgrounds the faster solution we're not gonna use the proof and then we're gonna wrap you know cross our fingers and hope that whatever information is neat to the adversary will not help in to 14 years old and this is I believe is a reasonable assumption because at the end what you're gaining is one bit of information about this about this key because if something happens you stop do you erase everything start from scratch with a new key so but it is an assumption is not standard is a dog and we sort of hedging our bets here we're saying you you can do this or you can do that okay so now I'll show you how you can do to people going for multiple people additive well now you can do this with many people if we have a and B shared additively and we want to compute a sharing of the further they P what happens is that a times B is all the cross products right so what happens every pair of players is gonna invoke the protocol that I just told you on each fare AI BJ so if every pair AI BJ will be mapped into an additive share well then when you put together all the additive shares then you receive from this M square pair wise protocol you'll end up with a additive share of the product okay this value in the blue box is the share that each player will owe and if you sum all those shares those will be the product okay now what does it have to do with the SI Planitia so the key generation now we're going back to the Shamir secret sharing key generation every player generates a random value shares it among everybody else in this room we all add the shares that everybody sent us and now we have shares of a random value acts that nobody knows what it is because we each have contributed a random component to it then we also get elects by doing what's called interpolation yes phone and meaning we all will be on G to the X I and then you can apply a linear combination to compute you the decay is deftly the same way the problem is that network the monied came as one so you compute G to the K by the same way we computed Yanks everybody generates contributes around the volume we all put a big order we have to do we induct we share sub K minus 1 which we're gonna need in the computation of X we use what's called beaver strip which is we also generate another random number gamma and then we use this multiplication protocol to get added shares of K gamma will reconstruct gamma in the clear we invert it in the clear and if we multiply the inverse times our shares okay we end up with shares times of shares of down quién top we're not.we shares of K minus 1 right so now we have shares of K minus 1 and we have shares of X now we need to compute s we do the same thing again there's a product there between K minus 1 X we both the multiplication product all we end up with additive shares of the product M and our a constant you just put them into the computation as well well what you do review Si and I compute accent purply does well it's actually a little complicated in that again some dishonest players may contribute bad values may inject folks and once again were not able to prove that injecting faults will not reveal information about the honest players but say that one of the bad guys messed up one of the multiplication protocols before and that is going to eventually result in the signature not very fun but this solution are very fine may give you information about the value and the input of the book so you can just repeat aside and recompute the signature what you need to do something a little more complicated which I don't have time to get into but basically do a mini multi-party computation in which the parties check together do we have shares of about a signature or not and if they don't they abort if they do they're you so now seeing your ships are revealed only if they're bound we do that implementation it's funny you can look at the paper for the details we have dramatic improvement over the our previous work in terms of the key generation but also over the key general in the signature generation as well this is the on slide we we have an extension which uses this multiplication to add them instead of you additively of morphic encryption we use oblivious transfer the advantage of that is that you can probably the strands are based on D D H and therefore you're not going out of the document like assumptions and use for the SI you're not using extra assumptions the bad side of that is that ot will consume more bandwidth at the approach based on concurrent work common Thursday you die and we'll present a paper which is exactly the same result different techniques we found that while the papers would submit is very exciting but the techniques are very different one important difference between do two papers our definition of security is game based basically what I can guarantee you at the end is that the adversary will not be able to forge a signature there's their definition of security stronger they get guaranteed the diversity learn on knowledge at all at the end of the protocol the disadvantage to that is that they can do the little game that we did about making an extra conjecture and they had to use the Red Nosed Rangers there's another very recent paper they just got accepted about the high poly SNP they use ot for this idea multiplication to addition but somehow end up with a log round particles are and [Music] [Applause] [Music]