Threshold ECDSA and MPC for Cryptocurrency Custody | Yehuda Lindell

[00:00:03][Music] you will have a hotel full cryptocurrency custody solution based on MPC and fiscal visit did you say thank you very much I won't say the B word in my talk though this is a joint work with Ariel Northland from bar-ilan University and Samuel Vernon Lucci from unbound tech the motivation is very clear a lot of people have invested real money in digital currency in cryptocurrencies and that money that they've had they're very invested or pudding is actually at a great risk it's not a theoretical risk if you do a quick Google search you'll see a large amount of theft of money from exchangers from wallets over time getting worse and worse and it's a real problem that we have to solve and if we want to solve this solution there are actually three different scenarios that with that we need to address and and we'd like to build a platform when we have built a platform which actually addresses all of those three in terms of its flexibility the first is exchanges so exchanges are a way of enabling you to buy crypto currencies so crypto currencies in exchange also between different currencies as a way of I guess managing your portfolio there's a relatively high turnover there's a necessity to be able to transfer funds at a high frequency and they actually have a real need to speed up their transaction rates the problem is that because of the threat of theft most of these exchangers have different size vaults and they have a small amount of currency in small vaults that are connected and you can transfer funds relatively easily but they have the larger vaults completely disconnected from the network and then when you want to transfer large amount of funds they have to transfer from the larger vault to a medium or smaller vault and that takes time in fact the largest exchanges can take days and actually sometimes only promise you two weeks to get your money back which is a very big pain point obviously and so you like to improve that and for this you need to have a separation of bolts of different levels of security and of usability of speed around that a second scenario that's of great interest is that of custody large financial organizations and banks manage or provide custody solutions for general assets and they're interested in providing also custody for crypto assets and here we're talking a very small turnover so the situation is I have a billion dollars that I want to invest in cryptocurrency and what I want is I want this bank or financial organization to give very very strong protection so they won't get stolen I don't need to transfer lots of funds in and out very often however I do need to get my money back reasonably fast because if the whole market is crashing and it takes two weeks to get your friends back then it's already much much too late and this is a solution that's offered to a high end customers and the final scenario is that of a wallet this is something that holds a small amount of currency typically used by individual people and possibly is used actually for carrying out transactions although that how much that will happen is yet to be safe so what are the requirements in such a platform the most obvious is that of security but I want to stress something that's often missed in this space when we think about security so we all know that the what protects cryptocurrency is a signing king and so you think about the possibility of stealing someone's signing key but in this setting that we're talking about that actually isn't really the threat the thread is actually fraudulent key usage if I can use your key once then I can generate a signature that transfers all of your funds and I'm done so I don't need to steal the key if I can use it so if I give you the most the strongest Hardware that protects your key but I can access that Hardware and generate a signature then I actually haven't solved the problem at all so of course we want to prevent key theft but primarily the problem is that a foreign on key usage there's also issues of backup and disaster recovery from putting a billion dollars into a crypto-currency custody solution I want to make sure that the key is not lost even with very small probability because a very small probability on a very very large amount of money equals quite a high expectation of loss and we all know of stories of people losing their keys and losing the cryptocurrency but a bank cannot take that risk likewise in exchange and therefore we need to make sure that's built in there also needs to be flexibility find chile usability or speed of transaction with security as in the exchange example of different vaults of different sizes needs to support different coins and systems different signing algorithms different standards like bid 30 to 44 for key derivation and all that needs to be provided in order to have a really a full platform to secure these assets so the cryptographic core of our solution is a threshold signing protocol which is a suite of threshold signing protocols so we support ECDSA EDD SI and snore easy descend snore I won't talk about today because they're actually relatively easy in the sense that they're MPC or we call em PC friendly signing algorithms it's a linear computation which can be made very efficient with NPC ECDSA on the other hand is much more difficult our protocol support distributed key generation because you don't want to have the key present at any specific time and if you think in your mind okay but I only generated key once anyway so maybe it's not such a problem I'll do it disconnected in this space it's not true very often you're generating keys all the time and a lot of people essentially the best that the common practice is to generate a new key for every transaction essentially but even if not it makes it much more difficult to really have a disconnected secure platform so we need to chip you the key generation it achieves also proactive security which what I heard people call here in previous talks post compromised security so even if some of the machines holding shares of the key are compromised we want to make sure that we recover from that so that an attacker has to breach a full quorum of signing parties in a single period in order to be able to attack anything we support rich access structures so that means that you can have a different number of sets of parties with different thresholds in each sets and and and or between them why would you want that think of a crypto custody solution offered by a bank then the bank would want to say that I need both parties at the customer and at the bank to carry out the signing transaction in particular the bank would like to be able to go to a court of law and have a cryptographer come and testify that there's no way the bank by themselves could have transferred the money out and and then I would also like to say that at the customer you'll have three out of five priorities from one business unit and two out of four from the management to carry this transaction that the bank will be also possible different subsets that can approve the transaction we also support two two types of parties and this is a quite unique to our solution we have both online signing parties and offline authorization parties online signing parties are what you would think of in a threshold signing scenario you have set the set of parties and they have to participate in the computation or to carry out the tip to generate the signature the offline parties are only only authorized the computation only authorized the signature but don't actually participate actively in the protocol and the reason we want that is because you can imagine a case where you have a number of offline power and other parties you have to authorize the operation they want to do it from their mobile wherever they are and they won't necessarily be online all at the same time so it's like an asynchronous authorization that the signature can take place and forcing all of them to be on at the same time can be difficult and what we do is we definitely have shares of the secret key also at these offline parties who reshare them to the online parties and the security model that you get is that during signing an attacker has to corrupt a full quorum of signing parties in order to cheat but not during signing operations even if you corrupt all of the online parties you still can't learn anything because the shares are also the offline part is you have to corrupt also a quorum so that's the property that we would get from that so this is just an example of maybe you have a custody setting you have a service provider you have a even a additional third-party trustee you have the customer they will hold shares of the key and they have to participate in order to generate any signature and this is what gives you the strong protection against fraudulent key usage okay there's no because you need so many different parties from different places and you have strong separation between them I need them all to participate in generating the signature it's not possible to for example breach the machine that's connected to secure hardware and generated signature because it just isn't any single place like that I'll come back to the protocol later on in the talk but what I want to stress now is that there's a difference between a protocol and a platform the threshold cryptography the threshold signing protocol that we have at the core is of course central to the solution but there are many other elements that are needed and I'm talking about about cryptographic elements and not just obviously these systems and engineering elements which are which are important but not relate to what I'll talk about so the things that I mentioned beforehand like secure backup and disaster recovery supporting standard key derivation like this fifth key derivation that's done from a master key proactive security party administration all of these things have to be done in a way that connect up to the threshold signing protocols I found deriving a key via sha-512 onto the Sun onto them a master key with some path string then the result of that NPC to do that operation has to be shares that will then feed into the threshold signing protocol and if I'm doing backup then I have I don't not doing backup of a key that I hold which is what were used to doing I'm doing backup of shares of keys and I'll show in a moment why that's actually not so trivial and all of that is needed on to get this platform let's talk for a moment about this about the backup in typically you think of so what's what's the probably one oh so we want to make sure that the bank or the exchange will always be able to get back the Hey and there won't be any danger that it's lost so the scenario we're thinking of is you have some standard key like an RSA key pair and the private keys at an HSM sitting in a bunker somewhere deep below the earth that requires five people to come and open the safe and also to him to input physically some passwords no to open it and if you think I'm talking about something imaginary I'm actually not banks do have such systems for other uses and they're interested in using that also for this scenario so that's not an imaginary think that's actually actually what they want to do and what you would think is I take the private key in and and encrypted with the this RSA key and then you store that replicated many places and and you're done the problem is that we don't hold the key we only hold shares of the key so that's fine it's very easy each party will just encrypt their share of the key and that's all that you need to do the problem is that what happens if one of the parties is corrupted and encrypts an incorrect share that's not something that you can detect because you just get an RSA encryption and now your entire disaster recovery and backup is made completely useless and since we talked about protecting millions and possibly billions of dollars of assets that's not something which we can afford to have and therefore we need to have some zero knowledge proof that each party will prepare to show that they've actually backed up the correct share and only after we verified these backups are we willing to actually transfer funds into the system okay that's the idea and what we do is we have a cut and choose type zero knowledge proof where essentially you encrypt either a random value or the difference between a random value and your share and then you open one of them and you and you verified these values all match up it's not difficult to do it's just something which is crucial by applying Faramir you get a non-interactive proof that's publicly verifiable so each party after key generation of the ECDSA or whatever the threshold protocol you're doing will generate an encryption of its share this will all be verified and only then will the key be declared as one that can be used another component that we need is key derivations so there are standards called beep 32 and 44 for those of you don't know the idea is that in many cases especially when you have wallets you have a master key that you want to backup and you will derive all the keys in the future from that master key by applying sha derivation to some path and the master key in a case like a custody solution or exchange solution you don't mind generating backup every time we generate a key but in like a wallet scenario that's not something that's viable now in a similar problem arises here like beforehand what happens if when we want to do this derivation which we're doing an npc so because obviously we're not going to hold in the key in any place so we're doing some NPC very garbled circuit or something else in order to generate this and generate the derived key the result of that is shares that are then input by the parties into the ECDSA protocol now you have to make sure that the parties input the correct results from that NPC into the protocol otherwise again you're getting something which will not be a valid key more more importantly or more interestingly you have to make sure the parties input the correct share of the master key because if they don't then what will happen is will generate a valid ECDSA key and everything will be fine but if you want to reconstruct that private key from the mastic you won't be able to because one of the parties input an incorrect value and the crucial point you have to understand is an npc protects the process of computation but not that you input the correct value NPC doesn't say anything about using correct values but only that from you that the only thing that's learned is the output if I input some incorrect value that's not inside the scope of MPC so we have an NPC protocol that actually enables you to do this in a verified way I won't go into details but the idea is that you generate shares of the new key and of the old key and the parties don't know which shares that they've got and therefore they're unable to cheat and you can verify that the shares of the old key indeed of the old key and then the new key is the one that is actually used afterwards as I mentioned we also have proactive or post compromised security and this is achieved by essentially adding a random polynomial if you using shimmy or sharing a random polynomial with a zero constant term and we also have party administration I want to note that one of the important aspects that you get here the junket with multi sync type solutions beyond the fact that multisig is much more limited and doesn't exist on all platforms is that if a custom if if an employee leaves the company then you need to make their share of the key B being valid otherwise they walk around with a valid share and I shouldn't have that okay really really capability anymore in multisig you would actually have to transfer the funds now because there's no way of invalidating that key but here it's easy you can re share and then that that share becomes completely invalid okay now back to the threshold ECDSA which is the core of our solution so it's actually been a long-standing problem to simultaneously achieve the following two properties first what we call full threshold and that means that you need a quorum to sign and and anything below that form any subset below that core means are unable to generate any signature or cheat in any way and to get that simultaneously with a fish efficient heat generation in the multi-party case has been a long-standing open problem so for the two-party case we have solutions very recently have very efficient solutions and for the multi-party case there was work going back to the late 90s of general thailand who go who's he who's here and but they don't get full threshold and for any number of corrupted so with full threshold doesn't work for by gennaro al from 2016 but that protocol requires the parties to generate in a distributed way a month a pyar ki a shared pyre key there's no practical way of doing that we can do this practically with two parties the best result to encrypt our last year takes 40 seconds for two parties so it's an expensive operation for amount for multi parties we don't even have any protocol that's been implemented there are theoretical protocols it's unclear at all that this is practical so we presented a new protocol for ECDSA at CCS last year relies on the hardness of pyre and EDH and in parallel general golfer also presented a protocol that has similar performance but works in a different way to explain our protocol list the high-level idea behind it this just review briefly what ECDSA signatures are so we have G which is a generator of an EC group we have the message m to be signed and we have to generate this equation where X here is the private key K is a random value and R is generated by computing K times G you get a point and then you take the X part of that point modular Q and then the signature is our an S now what makes ECDSA annoying for MPC people is this K inverse and our over here which is derived from care you have to get generate this capital R and this K inverse in a distributed way and that's a nonlinear operation that's actually difficult to do in MPC ok and that's what makes it different different from snore EDD si that don't have this inverse type thing and therefore they're much easier much more friendly to MPC than ECDSA s so that's the main challenge and the solution that Gennaro it I'll provide in 2016 to do this is as follows the parties generate shares random shares ki and row I ki is the shares of that K value I mentioned Andrew I are random shares of a random mask and then they use we use additive sharing so we just define K to be the sum and Rhoda be the sum of those values and then H pal you can send ki times G so the carrier there is protected because of the discrete log assumption and they send an encryption of Rho I I'm just added to the hormone fake encryption and this also requires zero knowledge proof to make sure you're doing everything correctly that's actually difficult and expensive but I won't go into the details of that after the parties get these values they can add all the K ice ki x G together to get capital R and they can use the additive homomorphism to get an encryption of Rho so receiving an additive your home morphic encryption scheme so we just add those and get Rho and then each party can multiply their scalar ki into the ciphertext to get ki times Rho and once again we send that to everyone you add them all together and what you what you actually have now is K times Rho so you have an encryption of K times Rho and note that Rho is random and perfectly masks K I want to stress that an easy do you say if you learn K you can get the secret key out okay so we have to make sure that K is not revealed but it's K times Rho and once we have that you can just run distributed decryption to get that value and when you have K times Rho and the clear you can invert it and now you have K inverse times Rho inverse and that's actually enough to complete the other process I won't go into details of the rest but that's really the main difficulty in doing what we're doing and as I mentioned genera tile used pi air which is the only additively or morphic encryption scheme that we have and that's why they get stuck because it means you have to have distributed key generation of that and we don't have that efficiently so what we do is something different we use what's called additive ehome Orphic elgamal and the exponent what what is this encryption scheme encryption scheme is exactly like elgamal except that instead of adding a here you add a times G okay so you're you're encrypting a by adding a times G and this is added to the homomorphic because if I give you two encryptions UV and XY then you have an encryption of eight times G here and B times G here and if you just add all these points together then everything comes out to be a valid encryption of a plus B time times G so it's an encryption of a plus B that's true Billy added to the whole morphic you can also multiply this by a scalar in a similarly simple way and this has fantastic advantages first the encryption that we're using now is in the same group as the signature we're generating now didn't go to the details of what's difficult here but in when you're working in PI air and in some some smaller group then you have lots of problems of leakage because of different group sizes and possible cheating because the modular are not the same and we this is all solved by working in the same group secondly zero knowledge proof SAR now all really efficient they're all the standard differing Hellman discrete log signal protocols that we know and love they're all simple and key generation is highly efficient simple and also distributed accretion there's only one small problem you can't decrypt this is not a valid encryption scheme because exactly I know it's funny that will solve the problem it's not that we're leaving it at that so you can't decrypt it if you run the general decryption what you'll get back is to a times G but a times G requires you to solve the discrete log problem to get a now if you use these on small values which was the original use of this scheme then you can you can actually solve the screen load but in our setting what we're going to get is this signal encryption of the signature that's what we get at the end and let's study that signature is essentially that s value is like or is a random element in the group so you're unable to decrypt and so our entire idea seemingly falls apart the the solution to this is actually a general idea that I think can be used elsewhere to enable the use of helder valin the exponent when you want additively homomorphic encryption in an interactive scenario the idea is that in parallel to working in el-gamal the parties hold additive shares of the values and use direct addition and multiplication protocols to generate shares of the results but in a not necessarily correct way so if we have additive shares you want to add them that's easy we just locally add if you want to multiply there are pair wise multiplication protocols that are reasonably efficient are in fact quite efficient but are they don't guarantee correctness they don't guarantee that anniversary cannot cheat and correctness here is a problem because if you cheat and do something incorrect you can actually cause a breach of privacy so what we do is we run in parallel everything inside I'll govern the exponent we prove correctness and and we run this private multiplication protocol and private operations without any correctness and at the end we have a or whatever value of might be an encryption of eight times gene we just have to check that there that they match and that's easy to do because proving things inside these groups is very easy and if they match then you can reveal and we're finished and you can instantiate these private multiplications either using pi err or using oblivious trends we're oblivious transfer is very very efficient there are very efficient private multiplications but it's a lot of bandwidth and since we're thinking of scenarios where you might have a mobile or a very different types of machines all over the world we wanted to make sure we have low bandwidth and so we're using a PI air based multiplication that's more expensive computationally but has very low bandwidth but I want to stress that each party has their own local PI Araki and so you don't actually have to do distributed key generation we ran experiments on the on this protocol in AWS with very basic nor powerful machines we ran between two and twenty parties we use the PI air based private multiplication the oblivious transference it is much faster and we have open conjectures on making the PI year protocol faster but currently these are the times that we have for key generation it's between 10 seconds and 30 seconds but actually the majority that time is each party generating safe Prime's so when you want to generate multiple T multiple keys you only have to do that once in the second and third and fourth and hundreds of keys are actually very very fast in terms of signing it's a few hundred milliseconds for a few parties up to about five seconds for twenty parties it's not as fast as we'd like in many scenarios but let's think about what we took no it's only a crypto custody scenario a large number of signers will only be used for these very large amounts when the rate is low and therefore this actually solves all the problems that we need for our application so in summary presented a new threshold ECG safe protocol it supports practical key generation signing proactive security there's a new paradigm therefore using additive the homework encryption NPC which may be interesting elsewhere and it's a full platform that provides the functionality you need for exchanges or wallets or custodian solutions it's also suitable for other scenarios where you where fraudulent key usage is very problematic like for example a root CA such a system might also be very useful there and includes things like backup key derivation and this online offline separation and the security is based on a model of separation which is which basically means as long as you can have enough parties in separate environments and different with different defenses that it's hard or almost impossible to get to them all then you're guaranteed security so thank you very much I just want to note that the two party solution for wallets is actually open source and you can have a look at it there thank you [Applause] so we have time for one or two questions yeah take it okay so so usually in the cryptocurrency setting they use multi signatures to solve similar problems so there's clear advantages in doing this but also disadvantages so I guess maybe will be worth saying a few words about you can always use a multi seek and have some of those multi stick signatures generated using such a system not e-cig has this has the disadvantages of you can't replace parties in and out it's not supported by all of the currencies many kinds that you don't support them and even though they do support them there is a cost for using it transaction costs and also limit to the generic access structure you can get so this is a much more powerful solution Neera near the beginning of the talk you mentioned doing like 32 derivations in like a garbled circuit or something but a bit 32 derivation is like on the order of a million gates or something that's quite non-trivial no NPC is really come a long way it's not a million gates by the way it's a 512 which if I remember correctly is about 50,000 gates yeah but then you've got to do of an HTML at each stage I said hmx it's actually it's about a hundred thousand yeah till 100 thousand times a number of levels you know you don't need to do what you do is that for each each time you derive you store you store the shares of of each node that you derive so you only need to go down the path what I see can you give them like a slag of what your performance looks like for that it's in the open so you can play around with it but it's things are the round of a hundred thousand gates is in like the hundreds of milliseconds not more than that I think less than that even ten tens to hundreds of milliseconds yeah thanks I was curious for for a lot of these institutions something that's really important is proving ongoing possession of the keys and that the thing that's like that for audit purposes is there a further leveraging of zkp that you could use for that in an ongoing way or is that open for the moment I think that the the backup is what you have to make sure that you can't ever lose what you have in general with these subs if you don't want to check that we actually have the key shares you can always ask us as the sign on some special audit message and if we can sign them we obviously have the shares so that would be easier to solve in that way on an application at the application layer rather than the crypto there thank you thank you again thank you very much [Applause] [Music]