# Threshold Factoring from Factoring - Abhi Shelat

- Channel: [Devcon](https://streameth.org/devcon)
- Date: 2019-10-09
- Duration: 49:20
- Topics: blockchain, smart contracts, distributed ledger, Science & Technology
- Watch: https://streameth.org/watch/yt-RwrJXO_ecRI
- YouTube: https://www.youtube.com/watch?v=RwrJXO_ecRI

## Transcript

so thank you for inviting me to give this talk so I'll mention this is a project for my academic group so it involves my students Jack ISA Schuler Josh and condi sorry Megan yes Megan and it also involves a collaboration with Muthu and car meet and they are from their company lahir oh okay so the goal of this is threshold factoring from factoring so we'd like to create an RSA modulus n and the only assumptions we'd like to use our factoring assumptions and let's say symmetric primitives like shower 256 that's kind of a doctrinal question that's driving this but we're not really tied to it the main reason I want to phrase it that way is that we are trying to see how well we can do with this approach without using something like lwe so there are some nice approaches with even just additive homomorphic encryption that will substantially improve one factor of this construction but at the cost of some other factors so in particular for this application it's not clear that if you want to use a vdf for for consensus that that you want this sort of assumption Ellucian you want extra assumptions that that that make there were in there and that then you have to make analysis about what l-dub you parameters are etc so this is how good can we do just using sort of factoring assumptions the other caveat is that we would like to achieve n plus n minus 1 security and this is this is again for the application but also at hid it handles for example questions like Joseph's question about civil attacks Mootoo made a nice point which is that if when you have n minus 1 security all you really sort of need is one honest participant so even if they're a bunch of symbols that are controlling several accounts and so forth as long as you have one honest participant then the privacy of the company computation is secure and of course Diogenes spent the whole lifetime looking for that one on this part discipline and certainly they didn't look in any aetherium for him and find them there so it's not clear if you could find an honest person but but but we can hope so this talk is going to discuss the semi honest version of this construction I'm just going to highlight this is a work in progress we don't I thought we'd have a better paper at this point we don't have a paper we can post a print and our and our implementation is like modular but not glued together yet so this is a semi honest argument or what we're planning to do and what the performance of our semi honest approach is is working but our target is of course malicious so the part that I'm not going to talk about is how every choice it was kind of made here really helps us build a malicious version of this protocol with very little overhead so other approaches have have basically user knowledge as sort of a heavy hammer and that requires a pretty large sur knowledge statement about what you're doing what we're planning to do is actually it's it's it's it's it's it's surgical as I'd like to think and built on our work from our ECDSA we have a nice way of getting malicious security for multipliers in that case so what are the big wins so here's really how we improve over this I'll present some of the prior work but at the high level we we're using more efficient primitives in particular the multiplier and that allow and in in combination with this other observation that allows us to have fewer candidate trials so when you're producing RSA just like when you do on your SSH key gen your computer is basically picking a random number and testing whether it's prime doing it again multiplying in and then producing that results so this process inherently requires sampling so so we have to do a bunch of candidates and then we have to try and check if they work and when you do them in the plain text like ssh-keygen and none of these things that we're doing makes sense but when you're thinking about a secure computation for the same thing actually using a different algorithm for the same process is is it generally always wins when it's something like this that has a lot of algebraic structure so we have some observations that allow far fewer candidate trials and and finally we're basically attempting to achieve less communication per trial so the three of those things are basically what get us improvements over what the status quo work is and the major idea come from two basic very simple observations which nobody seems to have used but we are using them aggressively the first is the Chinese remainder theorem so for our multiplier we use the Chinese remainder theorem I'll show you exactly how that works but it gives you a pretty good factor improvement even our own ECDSA we had a threshold ECDSA a series of works there we didn't use this observation and that immediately gives you a factor for improvement in communication which is quite big so now given that the moduli are much those are 256-bit moduli now that the moduli are our thousand bits two thousand bits then this thing gives you like a factor of 16 the second thing is more constructive so you can look at civic as one way or the other you can either looking at is building up a candidate that satisfies all your constraints or you can look at it sort of like the the way politics are you put something out there and everybody tries to tear it down and so we're trying to be constructive in our approach and it turns out that that actually helps and I'll explain that sort of later on but that's the high-level idea if you want to keep that around as we go through this so this is so this is a very popular topic starting from Binet Franklin and Frankel I forget the M but the Y is young starting from the like right around the early late 90s a lot of work basically on on how to do this these last few right here they are actually closer to implement implementable in fact this one and this one both have implementations of their approaches and so again like we're making quite a bit of progress I will basically start from what I want to do is start from this right here the Binet Franklin approach they lay out a protocol for doing this and it's it's kind of the protocol that everybody is kind of building upon and there are a few different ideas but this is the basic idea there's the protocol is in like sort of three phases we're gonna sieve do some sort of civic and different people use different approaches for that in order to get some candidate P and a candidate Q we're going to multiply so that sitting can be very generic in fact you don't have to do you can just pick a random P that could be you know null saving but you can do some sort of trial divisions to sort of speed things up then you're going to multiply them again this is a secure computation so at the end of this we'll have shares of n and then we'll finally reconstruct N and finally we'll do some by primality testing right here we'll run this n through sort of some tests using like this notation right here bracket P and bracket Q means share so all of the participants of the protocol have shares of P and shares of Q they'll use their shares of P and shares of Q in order to test the buy primality of N and that test results in a zero or one and if it's a one then it's a good candidate so that's the that's the approach we take we build on this approach and many of the implementations all build on this type of approach but just to be sure I wanted to I wanted to highlight some of the other approaches that might be floating around your head why can't we do it this way why can't we do it that way what's wrong with this approach so for example dam guard Mickelson they have a they of course also follow this same kind of approach here they're going to create a few candidates they're going to do some prime ality tests and then they're going to what I didn't mention here after at the end here is basically ZK proof to basically prove that the result once you have a really good result a good end then you can basically prove that that the run of that instantiation was correct and if you do their work commitments if you commit your inputs in the head of time then this approach is the best way to get malicious security in our opinion so it's again the same the same the same sort of rough rough sketch the observation they make which is a very interesting one and if we can this is an open challenge I like the approach that the previous speaker did about here's a challenge if we can get something like this to approach to work then we can get a factor of left for 820 improvement over what we have so generally we have some shares of P and some shares of Q and we multiply them to get P Q and we can do by prime allottee when we have this type of thing but of course when you do this on the plain text what you actually do is some sort of Rabin Miller test on this P and so why can't we do that in a secure computation in fact that's a question that was answered by the ACS paper a combination trooper the cns forgotten the eighth Alzheimer yes but nd m10 is an improvement of that approach and here's the reason why that's tough is because this rabin miller requires you to do a computation of this form a to the P minus 1 mod p and the thing is P is basically in a sort of shared State so AC s was basically proposing using a circuit and in fact one of our very first papers on militias two-party secure computation we basically implemented modular exponentiation this type of thing and it's it's it's billions and billions of gates if you do it using just boolean circuit so you have to do something better if you one need to do this you know is this is something you have to do several times and so forth once maybe you could do it three thousand times it's not so not so clear so they had a very nice observation on how you can do this type of thing using an approximate multiply an approximate base right no no if this is it's so bullion circuits are super super fast now like in 2011 we took like maybe an hour or two or something like that so today they're much I mean it's it's faster so it could be done in a few in tens of minutes maybe but the point is we have to do this Rabin test several thousand times in parallel so I mean the parallelism helps but yeah right right I'm actually like XKR is the best approach to that like we could actually do something like this this would be a brute-force approach but I'm an argue it's dominated by what we're doing and it's and you'll see it's dominated by this particular approach is also dominated so the whole approach was how to try to test P by itself and then Q by itself and then combine a P and Q and they had a very nice approach using this like a pro you can basically do modular reductions mod P with some approximate you could do an approximation that gets you into a factor of plus or minus four times P okay and so if you're familiar with the paper this will make sense but it'll get you it gets you an approximate version of what this number is and so you only have to check let's say roughly 16 possibilities okay so that's a great improvement but it's still a degree 16 polynomial that you need to evaluate as an arithmetic circuit okay so essentially one test requires roughly 16 multiplications multiparty multiplications to compute and you have to run that one test when you do the rape and Miller test with a very nice clean analysis by M guard and a previous author they showed that just one test basically shows that if it passes then its prime with it for in the average case for the size of Prime's that we care about its its prime with probability 2 to the minus 38 which is awesome you don't have to do a repetition of something like the the Ben Franklin test so they the thing is to get to like the security parameter that we need you kinda have to repeat it like twice or three times and so still you get into several multiplications just to check 1p and you'll see that so already if you do the math remember the number 16 times 3 is roughly 48 to check 1p then you have to check another Q right there so that's kind of like 96 multiplications keep that number in mind 96 we're gonna have a number lower than that for our approach and you'll see why this is dominated currently so that's not to say this is what i when when very enthusiastic number theory like math students come into my office and ask for some problems I tell them to read this paper I say there's room here probably you can like Whittle these things down if you can get it down to like from four possibilities plus or minus four to like maybe two or three if you have a tighter analysis this might become a winner so so there's there's approach here I'm putting it out as as a possible approach currently as it stated we've taken a different one for these for these calculations no no no so in your primary so they do an analysis the specific test they do with the other tests they show that on average right so you're right maybe what you're saying is on average it could be something similar it doesn't because so in the UH now in their particular analysis they require this divisibility property of P minus 1 not being divisible so they requires us they have a specific divisibility criteria and they specifically point out it doesn't work for by primality tests you know okay okay yeah so it's like P minus 1 is a might yeah I'll follow up with you it with the exact claim they make I haven't verified I've just taken their word for it so yeah that's that's that would certainly help us okay yeah so has I at all they have another approach to this and I just want to outline it so what they are basically exploiting is additive homomorphic encryption they are really taking that and sort of and getting great multiplications as a result they require in their implementation they require the Paille assumption so this is kind of doctrinally different than ours you need to make a stronger assumption to get this also PI a is is not especially efficient so in one particular so the way their protocol works is before these are the three basic steps right they have to do this key setup this distributed key setup this is so they use PI a as well as elgamal let's put that down there as well so they have to do a distributed key setup that's kind of it's like a messy thing of course it's currently feasible if it was like if this was definitely a winning approach this this could be a this could be overcome but so they're using essentially everybody creates their own their own PI a key and then they kind of luck threshold PI oh sorry not threshold it's like um and everybody creates their own and and they do pairwise so basically to do multiplications they are using this additive homomorphism so if boy if P and Q is you know a plus B times a plus a1 plus a2 times b1 plus b2 they convey I can basically encrypt my share give it to you you can raise it and do some summations and that could basically work out that's what they do and I guess that's all I really need to say is that they're using PI a to do multipliers and and they also have a very careful malicious security argument based on having el-gamal ciphertext that sort of parallel that got to run in parallel to the entire computation and then they prove equality between these two so I just wanted to put it out there I think lwe will now be a better mechanism for this so it'll be dominated by whatever approach uses lwe but as I said in slide 2 I basically put that put that concern aside so yeah so finally this is the latest approach this is from last year and this is what sort of initiated our look into this this is flop and they basically do again candidate they do exactly the same you can look through their protocol and now basically parse it into these into these basic into bit into basic blocks like so generation construction division and prime allottee testing and their big observation is to go back to a paper by Gilboa in the late 90s who also considered the problem of threshold r of RS a generation and he created an integer multiplier from from basic OT building blocks so here is what the primitive is you have an A and a B and you want to multiply so party one party has a one party SB you want to multiply them so and share results so that essentially the two two parties have additive shares of the product that's the building block and what what you Bo is going to do is to build this out of 1 out of 2 ot so remember oblivious transfer of essentially one party basically has two inputs here the other party has a single bit right here and essentially if I put 0 I get the 0 input if I put 1 as my input I get 1 as the input and the standard standard security properties you only get one and the other party doesn't know which one you picked so with something like this the way you can build a multiplier is you can basically have one of the parties here basically put either RI or B plus RI and this RI is basically a different RI every time so that would be r1 this is r2 b plus r2 this would be like RL and b plus RL so that's what one party puts as the inputs to the OT and the other party just uses their they take their input and break it down into a bit decomposition and just use each bit as the input to the OT okay so the output we're going to get from this OT let's call that s1 s2 all the way up to SL didn't I do that did I we're good okay so oblivious transfer this is a two party protocol one party basically has two inputs a zero input and a one input and they put strings there they can put whatever they want there and then the other party just has a single bit input it's a 0 or a 1 here and essentially the receiver party they get basically the they get essentially if their input was 0 they get the 0 and put if their input was 1 they get the 1 input and the sender doesn't know which input the receiver got and the receiver only gets one input ok it's a multiplexer yes exactly secure multiplexer okay so so what I want to say here is that what's what's very cool is if we run it like this essentially this party is going to basically take our I times 2 to the I that's going to be their share so this is going to equal C 2 and C 1 is just going to be the sum of si times 2 to the I so this is basically the multiplier you run L copies of 1 out of 2 OT with these as inputs and these as outputs and these are your basic shares to see why that basically works so imagine so I have a here and if my a I was 0 then I'm basically going to get RI and if my a 1 if I my a I is one that I'm basically going to get B plus RI so this is what si is equal to so if I take the sum here of Si times 2 to the I and just break that out you basically see that so in the case that AI is 0 then I basically just get these RI times 2 to the I terms and when it's 1 I basically get right here I basically get AI times bi plus RI plus RI times 2 to the I okay so over here basically if you when you sum all of this up this party basically gets a times B plus RI times 2 to the I for all I and the 0 case you get this term in the one case you get this other term and over here remember this person share was basically RI times 2 to the I so when you add them essentially these two terms cancel out and the product is a B does that make sense ok so the 1 and this is the critical point here why the CRT helps so to do a K bit multiply so we are working that a is in 2 to the K here but we can we can work in in in bigger ring sets and that's fine and we can work in such a big large ring that the inputs won't want to wrap around so the important point is that if the inputs are K bits then we have to do kayo T's okay and of course we're not going to use oblivious transfer we're just going to use this other very clever primitive called oblivious transfer extension which allows you to do a small seed number of oh T's and then extend them using Oh they symmetric primitives so we basically only need you know 200 basic OTS and then we can extend these using just something like a es or sha so the the downside of using OTE is that each call to this primitive basically requires either K bits or Kappa bits the minimum of those two right here so for example if we wanted to do thousand and twenty four bit multiplications right here if these numbers are a thousand and 24 then then the product is going to basically be so essentially we then need to do we base so k right here is basically going to be a thousand twenty-four it's actually gonna be 2048 if we want to keep the answer if we want to keep the answer we're gonna have to do 2048 but forget that point right here where as Kappa the symmetric key security primitive with something like a AES is simply something like 128 bits so in other words to do very large multiplications with this type of technique we unfortunately have to use these these OT strings have to be very big if you just use them as Gilboa basically states so now you can sort of see where the first sort of real nice idea happens so just to just to put that into perspective essentially we need ko T's of size K bits and so that's roughly K squared bits of communication for multiplication and for one K bit multiplication here so here's our first big idea or small idea it's just that you know if you want to do a multiplication in this ring you can also do several multiplications in these smaller rings and so just just as a if you follow along what's the right size to set this particular parameter how big should this ni be what yeah roughly 128 bits here okay and so if we want to if we basically want to do a multiplication like this we can just do smaller multiplications like this this does not help you in the plain next model it's not like an improvement like carrot Suba or anything like this this only helps because we're doing secure computation multiplications so just a so as as Riyadh said this should basically be a hundred and twenty eight bits okay so then T should be roughly K over Kappa bits okay and and so then we basically need to do T multiplications each of size each is sorry yeah we need to do two multiplications each of which are like Kappa squared bits of communication and so since T is K over Kappa we basically get K over Kappa bits of communication and so we basically saved a factor of like over K squared we've basically Fett we've saved a factor of K over Kappa okay so in this case K is like to 2048 and capped by 128 so there we go we've saved a factor of 16 there and and that's that's why this this approach wins but it gets better it's not only this candidate trial division so all proper approaches here what they want to do is before spending the the effort of multiplying a very large modulus with another very large modulus we want to basically quickly sieve out the multiples of 3 5 7 11 13 etc all the small Prime's who want to do some sort of trial division for okay and now how do our previous approaches basically do this so this paper right here they use PI a encryption and so what they do is they basically take their number mod let's say the small prime encrypt it and then send it out to everybody they add all of them together they multiply that by a random number and then open that random number now what should the answer be if if the number is not a multiple of 3 let's say it should be random right because I've taken a nonzero value and multiplied it by random number so I haven't really broken security I've basically opened a random number if in fact this number was this distributed additive share is divisible by three then you know when we sum up all of our residual all of our residues mod three would get something zero when you multiply that by a random number you get zero you open the zero and you know that your prime is basically broken now the unfortunate thing is that requires one encryption okay and decryption per Prime and that needs to be communicated okay so think about that communication flop they use something better they use one out of k ot okay and so this is kind of how they do it they their paper is in the two party model and so again another question is how they extend it to multi-party is it's not exactly clear but one one could do with that that wouldn't be the bottleneck but but there's no reason to so let me explain so P is basically p1 plus p2 and let's say we want to check divisibility by 7 what they like they what they also use and the sort of the magic sauce of making these things efficient is to try to use ot extension when you can because of AES and so Alice is going to compute her residue mod 7 Bob is gonna pick his residue mod mod 7 and Bob is gonna know here let's call these inputs 0 1 2 3 4 5 & 6 so let's just say Bob Bob's residue was 4 okay so Bob would know that if Alice's residue was 3 that would be bad okay so he's gonna put a bad string there and he's gonna put good strings everywhere else and now the protocol is basically Alice does a 1 out of ko T on her residue and if she recovers bad she sends it back to Bob and say this is bad if it's good well all she's learned is that it's good hasn't learned anything else about what Bob's residue was and sends that but it does some sort of confirmation that that was a good thing so the problem with this is one out of Coyote basically requires K times Kappa bits of communication okay so that's one problem the other problem is just the structure of this so their trial division is going to work something like this they're going to pick some share of P they're going to do one out of three ot or one out of five ot a one I have seven ot one out of 11 ot and then one out of let's say let's say the largest prime is a thousand it's not something roughly like that they're gonna do all of those Oh T s and then if they all succeed then the candidate can basically go ahead go ahead and time and the problem is okay let's say for example your first one succeeds your second one succeeds your third one succeeds and now your fourth one basically fails right here so this means essentially all of the work that you've basically done in vetting this prime this one big P that you've chosen for this particular approach all of the work that you've gotten that you've done to that particular point is basically tossed away and question you mean under malicious adversary so I'm gonna talk so the pit the hole this hole is basically about semi honest approaches and and yes what one can basically get around these type of so we have a strategy for malicious but I don't wanna get into that it's kind of a more complicated thing mmm yeah the point that the point is just work saving in the semi on this case that's what we're talking about here and in this case the observation is that when you pick your part Prime and start testing on that P okay you could end up wasting a lot of you end up wasting a lot of intermediate work now of course these intermediate stops right here like one out of 40 forty seven let's say right that's gonna succeed with 46 out of forty seven percent of the chance right but on that roughly two percent of the of the leftover you're wasting all of that previous work so you kind of you kind of see how this this work basically adds up in this one plus two plus three plus etc kind of kind of way a better approach is again to think about 'can't so again this was the destructive thing pick a P and tear it down instead another approach is a constructive approach so the idea is that in fact you know that you need something that is a you need an large number that is a non zero residue mod 3 so we can basically toss some coins and pick something mod 3 and test mod 3 right so we could go through some process to pick just some number in Z 3 that is a non zero sum mod 3 right so this is some process and it's going to do a lot of work because for example one third of the times that we do this it's going to fail right but any case whatever succeeds we basically put into our piggy bank right here and then we have a slightly smaller process 4 5 we put that into our piggy bank and a slightly smaller process for seven and a really small process for the piggy bank that's 1031 so let's construct these numbers separately and then use our CRT representation so if we want to basically get a number right here we just extract one candidate from each of these particular piggy banks and now we have a P okay and so now there's basically no wasted test so if you recall over here right one third of the tests are going to fail just on that first level right but a lot of the work that you do here is going to fail because you failed on the second level or the third level or the fourth level or fifth level etc all of that tail the tail weight of wasted work basically we avoid so that's why it's better to do constructive type of sitting like this okay and now if you put the first thing I said with the second thing I said so here we are using the CRT but let's apply the CRT again so if we want to find a prime mod three what are we going to have to be using ot extensions and ot extensions are not very efficient with small Prime's so we should do some sort of extra packing and so instead of using the small Prime's we should again use these small and these ends which are basically small products of primes we should basically pick residues that are like pick numbers that are nonzero like that are not smooth in n1 and n2 at 3 etc and then pull them all together and one can basically write a small you can try to be optimal but you could also just take a shortcut and make a greedy algorithm that tries to balance these things and so these are basically the these are basically the small ends you see three kind of one you want to put with a bunch of larger ones and 19 you can sort of like balance some of the smaller particular values here so there are nine candidates right here and I'm I'm almost done with this first set right here the last observation I want to make is that in order to pick a number that's not 0 mod mod these end ones here generally the approach just like this PI a encryption has been select a random P i okay that's we share it then we select a random R and multiply the two together and then open it just like we did with the pi a thing if it's 0 mod any of the small Prime's because now we're working in n1 which is a product of small primes then reject that number and throw it away ok if it's good keep that P right there then do the same thing with Q pick a Q pick another n damar open it and see if it works and if it is now we have a P and a Q we can multiply the P and Q so there's an obvious optimization right here that we don't need the R right here and the other random R right here the better approach is to select our nmp select a random Q since we have to multiply them anyway multiply them and since we're going to reveal n anyway go ahead and reveal them and if it's 0 then you basically exclude that slot otherwise you keep that slot did that make sense right so we basically get rid of that approach right there so all in all I told you we basically picked nine of these type of things and remember we're going to basically the algorithm what we're going to do is this is going to be the first piggy bank we're gonna basically this defines a ring based on these Prime's right here we're gonna basically randomly sample in this one until we get nonzero values then we're going to randomly sample here here and here in fact we're going to do them all in parallel and we're gonna fill our piggy bank switch in with enough candidates ok some of these things are going to take more iterations than others but we're gonna fill each piggy bank with let's say 50 candidates and then we're going to extract them and take that first Prime in etc in fact in this case we're gonna actually be able to extract the first n ok and so all in all we do the analysis the number of F multiple 128 bit ot extension based multiplications to produce a candidate P and Q is basically 14 ok and so far what we've done we've taken P's and Q's and we've actually also produced the prefix of a product ok of P and Q so we've used our multiplications sort of in two reasons one to test for divisibility by small Prime's and we've used the multiplication we sort of given it double duty we've also used it to compute the eventual final product 14 for this is for 1024 for to 1024 numbers that multiply to a 2048 number yeah so we still have to do a little bit more work that's the next slide right here share extensions so when we have a number that's like this big and when we multiplied of course the product is going to be bigger and in the CRT representation we have to extend and make those numbers as well I basically said here's another set of crimes that we basically do that with and so the the overall the overall work right here is we basically do 14 operations for this nine operations for here this this is 9:00 instead of 8:00 because in fact we also check for divisibility by this set of primes and that so that that actually helps us a little bit and so the expected number of multiplications we needed to do produce a candidate that is a that okay sorry there's one extra step right here after after we do this Civic there's an 82 percent chance that the number is is a prime and and so so this second set of saving of course gets rid of a few candidates and so overall I think yeah this is we haven't computed the public end yet we've only computed the first half mod the small ring so what what I was basic what I wanted to skip over this is this step right here we take our original shares extend them like locally extend them sorry what locally reconstruct them and then take the modular the take the modulo the second set of primes and then do multiplications on those now if something fails in those we basically have to throw the whole thing away okay but and that happens with this 82% so so overall this is the number I wanted to get to it takes 14 numbers to produce a candidate then it takes once we have that we know that these these numbers are not divisible by the first hundred and thirty one primes that's pretty good right there then we multiply them again and some fraction of them pass and so if you combine all three of these essentially we need 27.5 expected number of F moles per deuce a candidate n and this is an end that has been saved already and right now that it's further now that it's public we can also locally start multiplying the first million Prime's the point is we've already invested all of this work there so doing all of that basically saves the work of by primality testing and and that actually turns that your protocol turns out to be even though people complain about how you have to do this many repetitions it turns out to be not the bottleneck of this at all and and so let me just let me just get into that right there it's this this will just be the last slide the last few slides so our protocol basically consists of F mod gen which together does all of those things which is saving and candidate generation and then by prime which is roughly the same idea that you had there and mod gen only reply only relies on FM oh that's our optimal multiplier and F prime basically runs on relies on two things this is the sort of group multiplier that that's that's that's pretty cheap so in terms of deployability and sort of like part of this is to build something that's really easy to understand and also like easy to audit and we only basically require one cryptographic primitive that requires a lot of care to look at the rest of it is all gluing together and now here's some here's some performance numbers we don't have all of the parts glued together because we're still optimizing certain parts of this but we did take the current protocol I just I just did and and we express them in terms of these operations to get a sense of how much time would actually take and so we ran like 500 runs and we basically for each run to foot fine each run basically says how much it runs until it actually outputs a value that that succeeds and we counted how many Majin operations we basically need and that red line is basically the average and I think this is somewhere in the 3,500 so we basically have to generate about 3,500 candidates that is that lines up on average that lines up perfectly with our analytical analysis when we do all of the civic analysis we get a prime with roughly 1 over 60 and so doing that twice is roughly 1 over 3600 and this is where the DM approach this is the open problem the DM approach if we could basically sieve one prime and then another prime multiply them together then of course we'd only have to do about 120 of these mod generations so that's where I said there's a factor of 20 improvement we suffer from this square problem of Square and square and there are some approaches there like classic simple approaches to try to get around it but just in the simple version well DM if you if you can basically so here again the problem is we require the mutual coincidence of once that both of these things are prime that so we get squared if we could do some sort of prime if we could basically like here's one putative thing that doesn't exactly work maybe put 10 moduli together ok ten of these like shots and then if they're 10 choose 2 ways for us to win now because if any to win the whole modulus is secure possibly we could use that whole modulus and the DM approach to check the primal attea and it doesn't that proach doesn't work out for what I explained there but it's it's not it's not clear that would be the right way because then we basically do one big multiplication and then get a any choose two type of operation to help us help us win but even this right here I think is in the land of feasible let me show you so mod Jen is this many by prime is this many I think the average was around eleven eighty number of operations but I again this is not the this is not the bottleneck by any means and Gmail was that other thing here is the real FMO FML is the OT extension this characterizes how much work essentially ignoring FML in those g/mol and those other things how much work each party has to do and here you can sort of see the average which is roughly around 75,000 so this is the number of ot extensions that each said this is a number of calls to FML and if you think about end parties each party has to do basically a counter has to do note to extension on each of these F moles so this is roughly the amount of work that each party has to do seventy-five thousand ot extensions that's highly highly feasible yeah your accounting number of bits of communication I'm saying yes yes sorry you're right you're right right right times 128 well I mean aside from aside from multiplying this out so we haven't so these are again just simulations right here this is like so we haven't I haven't measured the network communication yep this is just right so I'll do it right now 75,000 is let's just call that a hundred thousand right so that's like two to the seventeen okay and we have to do two to the 7o T's okay and each ot is 2 to the 7 so that's 14 plus 17 which is 2 to the 31 bits of communication so that's less than 4 gigabytes right of per party yeah well times n this is this is a number of F mall operations and each FML operation requires each party to do that much communication per extra party so it's yeah it's like let's say it's okay so for a thousand parties it would basically this is bits so if we do this by if we divide again into bytes this is two to the twenty eight bytes per party so what is that that's two to the 30s billion so this is 256 megabytes per party so if you multiply by a thousand we're in the era of 256 gigabytes so that's a lot of communication but that's not like that's if we're at if we're using clouds layer that's not like Google measures it in petabytes per day so this is feasible you have to do this in order to prove why lwe so good right so I'm taking one for the team yeah of course yeah so in a hundred parties like if divide that by 100 and now it's 2 gigabytes per person for 120 30 parties and well I'll give you a better sense of it right this is how about is one well this is somehow this is Apple trying to help me here so this is a 256 built multiplication so to nifer - it's two of them actually because the this is from our this is a pristine like run from our so this is this is the amount of time with extra stuff being added so this is an upper bound on what it takes for 256 bit multiplication without any of our optimizations and so forth so it's roughly 300 milliseconds and right you cannot get it by this n-squared business if you want n minus one okay so all I'm hoping is I left you with an optimistic feeling for how this might work and a few problems so we're checking that P and Q are both three mod four is that not sufficient this is for your strong No right right yes yes yeah well that you as you said you just comes for free right oh well when you open them you just make sure in each slot that it yeah you can just avoid zero and minus one no each P and Q should be that way so that would just to increase the rejection rate so it takes a little bit more work but one that's a good idea for us to look into that what is the tangible benefit though like how does it get better when you have oh is that and you want to check for how big do you want to check to okay I see I see yes they don't exist yeah [Applause]