Threshold ECDSA in 3 rounds with Abhi Shelat | a16z crypto research talks

Transcript

it's my pleasure to introduce Abby shalat Abby is a professor at Northeastern University he's also works at Google right now he is an author of many exciting works very relevant to our space including RSA setup ceremonies and most recently ecdsa signatures in a threshold setting which are kind of the fastest right now for multibody cases so a lot of um companies are trying to deploy them and use them in production and ab is going to talk about that today thank you thank you lar for inviting me here it's been great week here um also you didn't mention I'm a budding standup comedian so I hope to share some of my

comedy about ecdsa with you today um and this is Joint work with uh my three students Jack Yash and Issa which have been just fantastic uh many of you have asked about academic careers and I think that's like the best finding great students you can continue to work on for with years the drive view that's uh that's really great and these slides are a combination of work that was done by these three people that I have just edited and added my stand-up comedy to so yesterday uh Chelsea mention or two days ago Chelsea mentioned uh why schnor uh hasn't taken off even though it is uh cryptographically elegant construction and so forth I found the reason it's uh it's this that uh this patent right here

in 1991 uh the patent as if you look just look at the first pages in The diagrams they sort of talk about like this snor sty proof in in the discrete log group but right there at the bottom like claim nine essentially also claims doing all of those methods in any elliptic curve group uh so this was 91 well before elliptic curve cryptography had taken uh taken over but uh but still he was smart enough to patent that so that is what has messed up I think all of the cryptography of the last 40 years uh 30 33 years as a result Scott vanstone came up with this ecdsa or DSA and I guess ecdsa to overcome those issues and this uh this has a number of

problems that are very hard to model cryptographically so the first problem is although this equation looks pretty tame it's doing a lot when you write it like this you sort of uh Eli all of the group structure and so R right here is an elliptic curve uh point right so it's an X comma y it's like a point like that right there and now you use the x coordinate of that R inside this equation and this equation again is a different field than this elliptic curve field so this right here is in the the field this right here is in the order of the group this number is between zero and the Order of the group and this number right here is between zero and another finite field which is not

related to the base of the elliptic curve group does that make sense to everybody with uh so essentially it'd be like you're taking so this right here is a very very uh crazy operation because although it just looks like a multiply you're casting a number from this range into a number to this range and and you're just sort of like and that's very hard to go ahead but that's I mean this is something that I always have a hard time wrapping my head around this is not ecdsa specific problem right this is DSA problem because even when in the original DSA problem they were mapping the guy from the group to the guy from mod P mode Q right yeah and

so it is I agree with you a crazy operation to do but it's it's not specific to the elliptic curve right it's just this mapping from the curve to the field well no the elliptic curve thing is in in the DSA at least you're talking about scalar values here now you're talking about you're talking about one of two scalar values I mean okay I it's to I I I don't see why it's EC DSA INT in my mind ecdsa does not introduce any things that DSA they're not present in sure but I don't know but okay fine but then DSA still has this problem no no no no no that's I'm not

questioning that that part okay and of course if you remember the equation from schnor from uh Chelsea's talk uh the other big problem here is that K appears in the denominator so it's an there's a multiplicative inverse so these are really the two difficulties these three values of K have to be consistent throughout this equation that's what makes creating a threshold version of this function very difficult unfortunately so when you're faced with things that are a little bit of a hack you could choose to ignore them and you can't here because this is pretty widely used all of these companies all of these protocols and so forth and I did a little bit more research I was intrigued by this so for example these two curves

which which have been used in crypto for quite a while now for signatures and so forth you can't actually let's encrypt doesn't issue certificates with curve 2559 or curve 448 in other words not only is like ecdsa wired in but also the curves for ecdsa are wired in you can't even use it on different curves you can't use different signature schemes that are you know that have more uh that have more better security proofs and the reason so for example Ed right here see this person who's on lesson cryp staff explains why even though there's a lot of analysis behind this curve uh it's not a prime order curve and there's some crazy stuff and this curves have this and like as a result I don't want to do it and I'm I work for let en cryp so I

make the decisions so there's another thing called the cab forum and these people basically give recommendations on how websites should run how like big websites should run and in their you know recommendation Baseline recommendations for TLS security for big companies they have this thing where they say essentially you can only use RSA or ecdsa and and if you use ecdsa you can only use these versions of this so uh the world has been locked down and I don't philosophically I don't know how to react to that is that a good thing that you know they're only four options and uh we're stuck with that or you know I don't know so we come back we

Face the difficulty here because ecdsa is so widely deployed and so uh you know ingrained in the way that people are going to operate for at least the next few years then we should tackle the problem the difficult problem of how to make a threshold protocol which I I've skipped I've assumed that you remember everything from Chelsea and and you and other people's talk about what the model of threshold crypto phography is ETC for people online who are just seeing this you'll have to go see their talk first and then you can watch this one anyway so I want to get to the point I I have a few points technical ones that I want to get into so that's that what is the difficulty there's no simple linear uh decomposition of these things so you have to use some more advanced protocol whenever you encounter something messy

sometimes you have to look at the uh master of tackling big messes and uh so I I kind of like this one the best very very messy situation with all those impediments and boy just curves it but the other 11 examples are also uh of the similar ilk so whenever you're faced with that sort of complexity maybe you could find a sort of a play that would be worthy of uh of dealing how the the Maestro of messiness deals with other things so that's what my plan is today to basically if you look at this there are many many prior works here that have handled ecdsa threshold ecdsa and many

techniques and so forth and I want to try to build a framework for reasoning about all of them and I think uh there are only three different type of ideas for how to tackle the messiness of threshold ecdsa which I hope to basically abstract and then all of the other differences between these 20 Works they all basically are what I consider to be lower level choices so the choices of how you implement a multiplier the choices of how you implement the consistency check so with those three things I think you can basically characterize all of these prior approaches how you handle the messiness of ecdsa and that we consider how you algebraically rewrite the equation how you handle

multiplication for uh these things and how you handle a consistency check so that's that's if you if you you can pull out exact components and you can then basically see that this right here is just like a ad hoc exploration of that tensor product everybody's basically found different little things and like written a paper and so there once you do that uh you can try to put together the best pieces and uh and then that is what I think the three-run protocol that we've written about that's what I feel that's how you should that's how I look at that work so uh of course there are many different settings here the honest majority setting where you can assume that uh more than half of the parties are honest that's a different setting

we're not going to talk about that today but there are many works and techniques in that that that I will bring up and then there are two- party cases and multi-party cases uh and then their generic techniques versus like more specific uh but I hope to try to explain all of this prior work in along those three dimensions right there so let's let's start with that and of course the First Dimension that I mentioned this common pattern is that uh you know unlike schnor which is just linear combination here cdsa has to compute this K inverse okay and uh you can't do it as an Ari arithmetic circuit over you can't represent it as an arithmetic circuit it's too expensive or Boolean circuit for example uh so everybody all the all these efficient protocols have basically come up with special ways of

doing that and I think there are only three ways that uh and even once you look at this you can try to think of other ways I don't think they I don't think there's much space there but of course this is where there would be some improvement if someone comes up with some better way to do this um so as I mentioned the recipe is figure out how to rewrite this to deal with this inverse figure out how to do multiplications that you can do with a variety of ways you can use P or additive homomorphic encryption or you can use sort of OT based multipliers or you can use class groups or you can use other techniques PCGS you can use number of techniques to do that uh and then of course consistency check so the first approach I want to give you an example

of what it means to do that first rewriting of ecdsa and uh this first approach was like Langford 95 and also Rosario and his co-authors in '96 they were working in this different model of honest majority but uh they actually uh this technique of inverted nonre writing is how we call it is uh is due to them and so here here's the observation so what you can do is instead of instead of having K inverse in the second equation and K up there at the top you can of course flip that that's this equivalent way of rewriting that right and now right so so that right there has changed s now from this inverse into just a secure multiplication with the problem

being pushed to this uh creation of the value r with that particular structure and for that they used this barlon Beaver trick or BB trick uh that many including our results use this trick and I'll just give you a short uh example of how that works so what you do is you this this a very nice trick and we talked about it on the board yesterday uh you know I think it has uses for all sorts of um credentials very simple trick you pick you sample another you secret share with this bracket notation is the standard notation in this field for secret sharing it's like a compact way of saying that you secret sharify then you reveal the multiplicate you do

a multiplication between these two values and reveal that publicly so you reveal the public value there you also at the same time reveal fi uh time the scalar product of group element G and fi and that's kind of like what UDA was talking about yesterday that's kind of the bread and butter uh there's several commit and reveal type of protocols for that uh and then now since this product the first product has been revealed you can kind of compute the inverse in the clear everybody can basically compute that inverse and then raise it to this value fi and if you do do the math right this is uh this will Bas uh these these FES will cancel out and you'll get basically get uh uh K inverse times G yeah everybody see that I try to make

the equation simple enough so you'll remember how this barlon Beaver trick works okay great so that as you can sort of see the nons is is K that sort of thing and you've basically inverted the nons that's why we call this the inverted nons technique and no matter if you try to look at those 20 papers it might be hard to extract what they're doing because again they're going to focus on exactly what they use for the multiply or what ZK technique they use or how they avoided a ZK step from a previous technique and so forth but ultimately it's it's very hard to extract this but all of these works right now what I want to do now is basically walk through all of these particular papers and kind of explain what technique they're using uh and

where these ideas came from and then then I think you can basically select the best of all of these and then you'll end up with the protocol that's uh that I think we've ended up with okay so that's the inverted nons technique so the second form of rewriting I'm going to talk about is the multiplicative form of rewriting okay that's essentially doing something like this um and so essentially what you want to do is set up multiplicative shares of SK and multiplicative shares of K what is multiplicative share mean so out of share normally you know that I have A1 and you have A2 and then the product the share is actually A1 Plus A2 multiplicative shares means that uh the the thing that we're sharing is the product of our our of our shares and when you have multiplicative shares if you look at this equation just to keep

you all with me here what does that help you do if you have multiplicative shares of K how does it hope you solve this equation you take inverse and then multip yes right so if I have K1 and you have K2 uh then we can locally compute the inverse of K1 and the local of K2 and then we can actually uh basically have multiplicative share of K inverse and then of course then we can multiply it by a and then basically have uh you know multiplicative shares of a and multiplicative shares of this term right here and now you need a protocol that go from like multiplicative to additive shares and that's the protocol so everything you do locally you do one protocol which turns multiplicative to additive shares

and now you have additive shares of s and now you continue to do the Reconstruction as you as you prefer um and so this idea we first find in this McKenzie ryer paper then Rosario and his co-authors uh they came up with a version of this uh using threshold p and that had a certain number of rounds maybe eight rounds and then the banet uh paper basically reduced the round complexity if I'm correct correct roughly like this one problem with these things is that they relied on this threshold version of P which immediately so during a setup you are required to have a threshold share of a P key and that's a very hard object to create because essentially a threshold Keys like RSA modulus uh for which Nobody

Knows the um the the secret Keys you have threshold versions of the secret Keys p and Q and you know as as Larry mentioned I've worked on that problem in we've implemented a version of that protocol which has been run but is a complicated protocol it's something that if you can avoid it's it's better and in fact UDA in 2017 he does avoid this he does avoid the threshold but only because in this case he his protocol only works for two parties so in that case one party can actually have the the threshold key H and and that's that's how they avoid it so all of these Protocols are basically different variations of this multi and then of course our protocol from 2018 and 2019 we essentially replace the PA part with

an OT um and we also have a different consistency check and together we can make that more efficient but um we were basically using this rewriting mechanism for uh for that uh for that technique for two parties this is great this multiplicative sharing is very easy to do uh when we in our 19 paper when we do this for many parties we get um like a increase in number of rounds the the version of our paper that we published had like long t uh plus six rounds and then we were able to reduce that to five rounds but still this sharing was very hard to deal with when you're dealing with multiplicative shares in terms of History then uh Rosario and goldfeder they were able to go back to their their

18 and 20 papers I view as going back to the inverted nons you can object to this but this is how I look at your work they going back to the inverted nons technique and as a result they can uh get rid of the threshold p version of uh the Assumption right here so see the Machinery all you need is P for this and uh their first version of their protocol I think again has like eight rounds and uh and then cgg MP is able to reduce that basically so the first three rounds of uh of GG of both ggs basically are the first three rounds of the original inverted nons the GJ KR paper that's how I look at it and then the last five rounds of GG are essentially the

consistency check this like masking technique that's used for checking for consistency and cgmp the conned at all paper they basically reduce this now from eight rounds to four rounds or four or five rounds I can't remember but essentially they do this by replacing the consistency check with the generic ZK check so it's a very expensive ZK check uh but it reduces round complexity this is how I interpret this work and this is now towards the final end of the work in this area so uh Yuda and Ariel knoff they they first wrote a paper in 18 and then it later got the journal version of it included ifak and uh and Samuel both this paper as well as the next paper the

Abram at all paper they both used this new rewriting called this ecdsa tupple I'm going to work through it in a second but uh essentially uses this barlon Beaver trick twice um and that rewriting that has a very very simple algebraic structure for the rewriting and that I think is actually great now now uh UDA and uh so Ln was P based and then uh they later replaced it with an OT multiplier uh but the P based version of Ln still required these like Zer knowledge range check proofs and uh a complicated consistency check and um

same with uh with this this paper uh this paper basically express it they they require so this is why they needed to come up with a very simple rewriting because they're they're trying to use these um pseudo random correlation generators to get a very very low bandwidth protocol so it's like on the order of 100 bytes sent to do this uh threshold signature however the computation is like really quite big and uh the implementation the setup for this PCG is something that um it maybe it's too complicated to implement so the later is a multi-party two-party yes the this uh this anos paper is multiparty and the hlnr paper is also multiparty and there are other generic techniques

uh so in particular Nigel and this dkss paper uh both of them basically observe that you can use speeds generically uh and you can basically do these Mac checks in uh you know you can do speeds with Mac checks in the exponent and that is a way for uh basically implementing any threshold thing but they have their disadvantage uh in particular um the bandwidth and the complexity of their protocol basically is uh um their consistency check is too expensive so let let me try to summarize all of these techniques this is essentially how I view all of the prior work you look at how they've Rewritten and there are three ways to do it you look at whether they're using OT based multipliers or P based multipliers

or other techniques for multiplication and you look at how they do the consistency check and you can use uh for example generic ZK proofs you can use some sort of check relations in the exponent like we've done you can use generic Macs from secure MPC uh you can use any sort of Mac all of these things basically uh go to the efficiency and what I'd like to do is show you that in our paper these are the basically the negative downsides of each of these particular approaches uh and what I'd like to basically show is that what we can do in our work is we use this ecdsa tupple rewriting which I'm going to work through we you can use any two-party multiplier as long as it's secure multiplier not a leaky multiplier and we Implement that using OT because we think

that's a great uh decision however you can apply you can Implement our protocol with any multiplier so for example you could use a secure P multiplier that secure P multiplier would still need to use these ZK proofs for the range checks and so forth but if it did a secure multiplication per like some ideal functionality that would work and then our verification I'm going to show you this like statistical check and the basic idea is this we are going to exploit the fact that that you basically have commitments the public key is a commitment to a secret key and the non is a commit like the public nons R is a commitment to R uh to the to K and since you have these public commitments of these values that are already ready for you because of the problem definition

we're going to exploit those and we're going to create a very simple mac that we can use to check consistency of all of these equations uh that's a statistical check and that basically requires no extra like very little extra work to actually Implement now that's the high level if you actually look at our security proof there are three small modifications to what I've said to deal with very small technical uh issues which are not worth uh so it's not ex our protocol is not exactly as I've said in this way but um uh close enough okay great so let me talk about this uh ecdsa Tuple rewriting so that was this our original equation you see and uh so here is this uh double barlon Beaver trick so what you're going to do is as many

just like the first uh inverted nons writing you're going to sample this five value and that's going to be an extra secret share and the trick here is to multiply this s equation by one in the form of five over five the secondary trick is that if you have a way of computing this Alpha and then you have a way of computing this beta you can just do alpha divided by Beta then you can basically compute the uh signature of course uh this is uniform beta is uniform you can reveal it publicly because of course it's massed by F and then Alpha is basically fixed by what the signature value is so it's just a slight difference from the original inverted nons technique and uh the main point here is that now uh

essentially you have a multiplication of K * 5 and SK * 5 yeah um are those two different secret sharings of f no well that's uh so in our implementation yeah that's uh that's right the uh it is the same it is exactly the same secret sharing of F and then I think your follow-up question might be then don't you have a problem of maintaining the consistency of the mult of the value fi in both of those multipliers and yes you do and there's a pretty simple way to get around that which I'll get to in a few slides yeah and secrecy if it's like a onetime pad type of yeah so you're only going to re you're

not going to ever reveal fi you're just going to reveal Alpha and beta at some point this right here is what we call this ecd say Tuple so SK of course is shared before during the setup phase and then K 5 K * 5 and SK x 5 that's the correlation that you basically want to uh create and that's the correlation you want to check the cons consistency of and it notice it has more redundancy than the other versions of uh of the re in and that redundancy lets you do these checks like for example our consistency check um uh in a uniform way Ln does not explicitly explain that they're doing this uh there are two-party protocol

with using PA to do threshold ecdsa I thought alen was multiparty yes uh yes so yes there yes it's you're right it's a multi-party protocol are they doing is the second one doing a the second one is using a PCG so the second paper uh their main goal is to uh explore the extreme version of like uh if you needed to only send a few hundred bytes uh could you achieve this and as a result there it's essentially that this big hammer of a PCG and they uh basically showing that you can apply it to create these type of correlations so

pseudo PCGS pseudo correlation generator and as a result they identify that this is the correlation that you need and if you have this correlation and so yes I would I would credit uh Abrams at all for writing down this as being the correct correlation that you need to do and then we observe that this is kind of also implicit in what these people are doing uh four years before so clearly there's like a subliminal influence in uh how this is working uh and we would like to explicitly credit them for that great idea here's how we do our uh three round protocol in the first two rounds you're going to use the standard technique that UDA talked about yesterday for in parallel establishing that value R and then also securely

Computing these two particular values K * 5 and SK x 5 we're going to set up the part of the verification of the consistency and then in round three after uh after those checks pass in the middle here you locally compute your local share of this Alpha and then you basically reveal these two to the party that's reconstructing the uh secret key and then given that you can output the signature like this we run this this standard protocol which everybody Could reconstruct from imagination this is the secure multiplication protocol uh and you'll see that the fact that we use five twice here helps you argue the helps you with the consistency so this is T out of n this is T out of n yeah then how do you sample the TP out of

hand shares of random values uh well so this is the signing part of it and so essentially SK has already been set up as a and then this you can you don't this is just T of T actually uh so you you know what you can apply your lrange coefficients like to get so all of this will just be added of shares at the end that's the floore that comes from their basic observation there are many methods to do the secure computation we're going to promote this OT based one which we've implemented very carefully that works extremely fast and has reasonable bandwidth and then this new consistency thing is uh the the the simple check that uh that we've contributed to this literature okay very

good this by the way so when it is a tea party thing of course uh you you uh you do these pawise multiplications and then sum them that's kind of what this equation is saying so essentially this protocol is what every party does with respect to every other party so it's pawise versions of this thing in parallel how do we do the multiplication so our abstraction is this two-party multiplier which uh Alice and Bob basically put their inputs A and B and they get output C and D such that c and plus d is equal to a * B so we're going to do one small extension to this but we'll treat this as kind of like a a basic maliciously secure building block that's what you have to basically provide to instantiate this framework we

can talk about how you implement this with OT as well so here's the one observation that uh our protocol requires you to securely compute k * 5 and SK * 5 uh and those are two multiplications where one party has the same input so diagrammatically uh this picture looks more like this and uh essentially one party has one input the other party has two inputs and each party get basically gets out of shares of the both right this is one of the benefits of this writing the correlation this way uh already lets you solve one of the consistency problems uh with this because uh we call this abstraction essentially uh we get this consistency for free if uh instead of a multiplier

we call it a vector multiplier right or vector oblivious linear evaluation volay is kind of the same thing and when you do this with an OT multiplier it's like almost comes uh it it comes very easily uh not for free because you're doing twice uh you're doing less than twice the work of one multiply in order to get two multiplies and you also get the fact that that by the structure of the protocol in the case of OT like uh if you use like random OT in for example then this B right here is like already by the protocol fixed to be consistent for both multiplications so that's a cheap idea if you just use Vector o as your primitive for this multiplier then uh

you're forcing one of the parties to use the same input for these two multiplications now I want to talk about our uh consistency mechanism as I mentioned in the sort of int C we're exploiting the fact that uh this this protocol this problem has a bunch of setup that already uh we that we get for free so first as you know since it's a threshold signing key the public key exists and everybody knows it and uh during key gen everybody's already basically everybody has a share of SK but we also have this Mac this like this commitment to essentially this uh this secret key sharing and of course uh part of the protocol relies requires us to basically share this R and that we also have as kind of a commitment to some

value of K we are going to no other protocol is exploiting these two values that's one of the big differences no other consistency check most of all of them use basically the generic Hammer of gmw style ZK or explicit Max and uh both of those are basically doing more work than necessary that's our main point is that we can use these two to get uh a simple check another way to look at is that we're basically going to interpret this value fee that we've sampled for this particular protocol as a distributed Mac on K andk that we're going to check in the exponent how do we exactly do that one other fact that we're going to need is like yesterday when you saw you this talk you saw that the standard way of uh reducing this R basically has everybody uh basically

publishing this value RI which is their local Ki to the uh to the G element and so this is an artifact of that um non creation protocol and we're going to exploit that as well so let's see just uh as a two-line reminder of you this's protocol everybody first commits to their value and then after receiving everybody's commitments you reveal the commitment and just to hammer this point why do we do this commit and release this is a test you saw you this talk yesterday why do you do this commit and release any of the students what was the thing that you were trying

to avoid what if we just release it this is a fundamental attack he was defending against so what if I just everybody sends your first message is send RI which is you know uh your local Ki times G you're supposed to publish that what goes wrong the Ross attack right not maybe maybe but there's uh a simpler a simpler attack simpler point that he was making conent making it zero like adversity can sample the key bias yes so essentially a rushing adversary can listen to everybody's thing and then

decide what they're going to send and you can cancel out people's shares and bias the key to anything you want in particular a key that you know exactly the thing to right so that's why you have to do this in two messages and his of course major trick yesterday was this evf to get rid of that by forcing the adversary included to essentially have already committed to what they're going to say now I thought about later on I'll show you in the protocol I thought about using this technique you'll see why it doesn't necessarily work in uh in our protocol or at least I don't yet see how to do it anyway here is the nutshell idea for how our consistency check works if we look at this version of uh where we are right now we know that at this point Bob has published this value RB

Bob is supposed to put this this is the multiplication between fi and K that we're doing we also have to do one between fi and SK which will work exactly like this remember our special um abstraction is that we're using this two-party multiplier so Bob puts in his share of KB Alice puts in her share of uh F A and they're supposed to get these two multiplicative products now let's just work out essentially what uh what um so if you plug those in essentially this is the equation that we get right now let's work out exactly what we know and what constraints must hold the invariant that must hold after this multiplication the first step is we just rewrite this so we know that essentially Bob's output right here

basically has to satisfy this constraint here everybody also knows essentially Bob's public key there okay so if we Define d here just as Bob's output to the uh to the G there I'm going to claim that it is okay for Bob to send this value D over to Alice so it's kind of like a one-way function this is like a scalar one-way function of uh of Bob's output and to claim that that's okay to send here is why that's okay remember I told you that everybody has RB which is just KB to the G right and Alice already has Alpha a uh f a right so if Alice takes RB and raises it to this F A right

that's basically G that's basically this product right here right gtimes this product and of course Alice also has C so if Alice basically subtracts from this product uh C * G let's call that t now what is the relationship between T and D they should be equal if if Bob hasn't cheated then uh then T should basically be equal to uh to D and so Bob sending over this value d essentially shouldn't give if Bob hasn't cheated doesn't give Alice any extra information about anything okay so that in fact is our consistency check uh

that's as I said there's uh two other tweaks that have to be applied to this for slight randomizations but this is the heart so you can't apply this directly but this is the heart of it so Alice is going to because this value is floating around already Alice is going to have a way to check so Bob is going to get an output Bob is going to compute a one-way function of his output and send it back and if Bob hasn't cheated then these two values have to be equal what happens if Bob does cheat all right so let me go through that this is exactly what I just basically said if Bob is honest then these two have to be equal Alice can compute the thing herself and so thus sending this doesn't leak anything else that's a perfectly safe uh safe check now what happens if Bob is malicious the

way you can model that malicious behavior right so I either Bob sent some value here that was uh Bob sent a value here that's not the input that he's using in this multiplier and the way that we're going to model that is to say that um this input right here we're going to call KB and this value is to where he cheated instead of sending this value he sended he sent some other elliptic curve with some offset Delta okay so uh what happens now when uh a essentially when Bob when when Alice now computes this Here's the the the Highlight when Alice now applies this function t uh when she computes this T

using this particular equation there is going to be a component of this value T that Bob is going to be very unlikely to predict as a result this check is going to fail with very high probability essentially this is the fundamental inconsistency that everybody knows this value it's different than the actual value that's defined based on Bob's input to the multiplier so if Bob's dishonest this first value D is based on what Bob can compute right so Bob put some particular thing in we just we wrote rewrote this right here right we rewrote the equation D and we just substituted it right here the value that Alice computes is this value and so all I'm going to do is extend expand this second equation right here right using substituting this value of RB for this value of uh essentially

RB is this value right here right you can essentially this multiplic right here is basically going to uh take Delta and raise it to the f a power right here and so this offset right here Delta some unknown value that maybe Bob controls right is going to be raised to this particular scaler element and it's going to essentially be a random group element that is added to the rest of this equation and so for Bob to pass this check Bob has to send over essentially the the D that they was able to compute based on his view of the protocol plus this value right here and this is why we call this value a Mac it's a Mac in the

exponent because Bob's Bob has no it's information theoretically hidden from Bob's view if we treat multiplier as a ideal primitive then f is information theoretically hidden it's a Mac key essentially on this value and so his probability of succeeding with this is essentially the field size the size of the Mac this a statistical check as a result so no that's a pretty simple idea right it's not zero knowledge it's not a big hammer it's not anything it's just extracting the fact that uh uh when this when this term in the exponent basically is there for free you can basically check the mac and the exponent essentially for free and you can do

exactly the same check you can do exactly the same check for the 5 * SK multiplication and right you use a vector o le for that multiplication and essentially the same exact exact check this is ultimately what our protocol is now you can sort of see why this primitive from yesterday which helps reduce so U this primitive basically is a generic way of taking any protocol that has these two steps and squashing them into one step and so when we apply it to our protocol we can squash these two into one round right here but our multiplier still requires two two rounds and I don't know I don't know how you can basically predict how you can

uh commit to well this multiplier is not of the form I first commit to something and then I send something so I'm not sure how to apply his technique or how to um how to how to move that first multiplier message into some sort of pre-processing state to improve that so I don't think it improves our protocol from three rounds to two rounds however I do think our protocol can be pipelined in order to achieve the two- round thing which I'll talk about in in a second anyway this is the version of our protocol everything is quite cheap and quite simple and this pipelining idea there's nothing clever about this but uh the observation is that this message right here and this mult message right here

they can be produced without uh any knowledge of the message and so you can basically send that first message with the last message of round three what this requires every client to do is just keep the state of that message and then during the online phase then these two messages can basically be um exchange so this is how I think you'd get the same performance uh and because our protocol is UC secure one can basically agree that this type of composition is uh is okay last little detail here this this slide is about how you can realize the multiplication technique so so far I've said the rewriting technique you should

use is this ecdsa tupple idea the verif the consistency check is the one that I just explained it has no zero knowledge does not require uh you know simulation extractable Z knowledge or range checks or range proofs or any sort of uh cons consistency check other than what I described plus two small tweaks which uh add a at a few um operations but constant number of operations now you could basically pick what multiplier you want to use so PA has so if you want to implement this two-party Vector multiplier this volle uh essentially you have PA class groups these um PCGS and oblivious transfer and they have their pluses and their minuses all of them um

some require specific uh assumptions some require they require internally inside the multiplier for proving militia security you need like a ZK proof for the PA or class proof uh based schemes for PCGS you don't uh and for oblivious transfer you don't and you can build these from most public key assumptions but these other ones require specific assumptions and then it comes to Performance so essentially in terms of compute time right so I didn't there isn't a line here that basically says how much uh does the uh communication cost so PA has very small communication but still on the order of kilobytes for a multiplication uh class groups have a lot of communication I believe uh PCGS

are very inexpensive individually very cheap amortize but you have to amortize them in batches of 100,000 and a these transfer I'll give you some details about our performance and our implementation in a in a little bit so uh we we do these experiments where we put these nodes in like gcp uh data centers these are the ones we use for this experiment and these are the times that we were getting um some people say these are slow which I agree but I'm these are literally the times we measured so we might not have been on the right virtual Network or right instance type but that's what they what they are so we only compared our technique our new technique against our previous technique the one from 2019 and then we found an open source

implementation of cgmp but it was by tourist group but we weren't able to get it to fully it wasn't networked so we weren't able to run Apples to Apples test we were I'll show you the test we were able to run but it should give you a sense of what the trade-offs are it's a big big table with lots of data that I copied and pasted from our paper but I'll highlight some of the points here so in terms of two three four party signing uh again we're like 4 milliseconds 6 milliseconds 8 milliseconds for the signing part with our newest signing approach this is faster than our prior approaches since our technique only takes three rounds as soon as you start testing on uh wide area networks the US like across across the country or across the world then

these numbers become like really quite big it's like 105 milliseconds to go cross country uh essentially for the three message um uh exchange and so you can even see that like when we're up to 256 parties we're still signing on the order of a second uh which which is reasonable and our setups are also um quite inexpensive and then we basically compare our bandwidth right here so for two and three parties it's like roughly it's about 50 3 kilobytes essentially per party uh as as you so that's kind of like the the Gap here um so it's it's about this it's way less than what people send on Snapchat to each other so

as a result I consider it reasonable and conceivable uh for the signing and then finally in this last Corner we um I'm know this isn't the best implementation but it's the one that we're able to find and we ran just um compute only so on the same machine and uh just for two four and eight participants and the signing and setup times are already like in the thousands of milliseconds or like in the seconds so it's a big gap between um essentially all coming from this uh from this particular framework as theory predicts you know for like essentially a six times improvement from our own signing from our 2019 paper based on the

fact that we're now constant number of rounds three rounds as opposed to uh we didn't we didn't Implement any of the pipelining in this experiment so I think that is all I want to say about this any questions sorry do you mind just saying like recapping intuition for why the multiplication needs two rounds it's based on OT extension and the the best you can do in OT extension well PCGS are way around this but like using standard OT extensions which we're doing they require two rounds okay so answer your question why is it two rounds is because that's a fundamental in limit that we get from OT extension that um the online OT extension is like uh you so we did we did a bunch of OTS

and we did a bunch of you know setup and so forth and now we need to extend those OTS and that's still takes one sender to receiver uh exchange um so that's where that and then that's all we need once we do that we can re der randomize the um OTS and then we can use them and interpret them in the right way as multiplier values so I don't see us getting around that uh the PCG technique gets around it that allows non-interactive OT extension right um but and and that data point shows you that it's uh that it's feasible however and this is from my memory um they so for example for the value of 80,000 which I picked out from

their paper because they're 880,000 seconds in a day um it takes them roughly 880,000 seconds to pre-process 80,000 OTS uh so essentially if they were to use that in production you'd basically on Monday be having to do all of this work in order to basically do one per second uh on Tuesday and so the online phase of their thing is very fast it's only like five or five milliseconds per multiply however the offline phase takes 1 second of computation per multiply so bridging that Gap would be the thing like right now we don't do anything offline it's all online and it's you know on the order of

milliseconds for the full for two multiplications with this driving application of ecdsa that everybody wants to be threshold uh do you think there are things that were helpful for NPC in general that just um appeared for ecdsa that can now improve generic NPC that's a great question uh so I think and I've I've posed this to uh my students this um exp this checking so how does our how does our approach differ from the Nigel smart at all that work so they also observe that they can just use speeds you can check the speeds exponents in the uh you can check the

speeds Mac in the exponent um however they spend essentially twice as much time in the pre-processing to set up what they need for their Max and then twice as much bandwidth during the online phase in order to send these extra Maxs and so our observation is that in this particular application I told you because we have these two values we don't have to do that and we get this automatic Mac check and so again a natural question is like can you create that artificial Mac check in the exponent for arbitrary circuits so that's an open question I've asked my students we haven't they're all busy now they don't listen to me so uh if anybody here has an idea I think that's a good problem to workout so exactly your question where does this help General

NPC and my take is that there's a new technique a compressive technique for checking speed style or bza style Max in the exponent that avoids the um straightforward way that is already known for speeds and bza which is just to create that extra thing and send it for each multiplication and then they had that batch checking but uh I think you can basically do that in the exponent more efficiently that's the hypothesis as for any other things no I mean like this is a basically low depth arithmetic circuit that we're trying to do MPC for and we're all trying to find bespoke techniques for it I think I don't I don't know where else these techniques help uh for other MPC

problems [Applause]