Ryan Henry: Faster 2- and (2+1)-party computation via DPFs

[Music]

[Music] thank you all for coming uh this talk is gonna be a little different than most of the talks at this conference so i'm ryan i'm a assistant professor at the university of calgary i spend my days uh scribbling on whiteboards and coding away doing various um fairly low level cryptographic stuff and what i'm going to talk about today is actually some brand new low-level cryptographic stuff but because i realize this is not a crypto conference and most of the people in attendance um are not necessarily interested in the very low level details of crypto i'm going to keep the the presentation relatively light and in fact have a little bit of a tutorial feel to

it so i'll spend quite a bit of time showing how the basic sausage is made to motivate what new ingredient we've added to the sausage and towards the end we'll get to the new ingredient so the title of the talk is faster 2 and two plus one party computation via dps that's a bit of a mouthful i'll explain what exactly this all means uh as we go through the talk you can contact me if you have um interest in this or follow-up questions or whatever at myfirstname.lastname at youcalgary.ca okay so let's start by motivating things with a classic problem called the millionaires problem so here we have alice and we've got bob and alice and bob just so happen to be

exceedingly wealthy the thing is they're also both very privacy conscious and neither one of them really wants to disclose their wealth and yet at the same time they want to figure out which one of them happens to be wealthier so that's the question which of us is wealthier the predicament is that neither one of them actually wants to disclose just how wealthy they are and so when a cryptographer sees a problem like this usually the first thing we will do is we will try to formalize precisely what the goals are in terms of something that we often call it ideal functionality so this is a magical black box doesn't exist in the real world it's just a thought

experiment but this magical black box implements the functionality that we want to actually somehow securely realize with cryptography so in this case the functionality that we want has alice reporting her net worth to it bob reports his net worth to it and then it just tells them which of the two is richer without leaking any extra information so here alice knows what her net worth was she learned she knows what she reported over here and she knows that the answer came out that she's richer than bob so what she can infer from this is precisely what you would expect that whatever bob reported as a net worth must be smaller than hers but nothing more and we just assume as

part of this thought experiment that no matter how clever or sneaky alice is there's nothing that she could possibly do to try to coax more information out of that box this answer is all she gets and likewise bob learns his own net worth he knew and he learns that alice is richer so all he can infer is that whatever amount alice was worth must be more than him but he learns nothing at all about say the scale of the difference and so the goal here is to recreate this ideal functionality with the same properties it's impenetrable it doesn't leak any information beyond the final answer etc but without resorting to magical thought experiments with magical boxes that

can't possibly exist in the real world and so this classic problem was first proposed by a guy named andy yao who also proposed the first solution to it his first solution to it was great at the time in retrospect it's not a great solution it was actually a couple years later he proposed a second solution which still to this day is is used to solve all kinds of problems and that's called garbled circuits the idea is we want to decide what that box should do how do we phrase that in terms of a digital logic circuit so here is not the right circuit for comparison it's just a random circuit but an example of a digital

logic circuit and the way the technique works is that both alice and bob agree okay we have a digital logic circuit that if you were to put my net worth and your net worth both into this circuit it would correctly do the computation to tell us which of the two of us is richer and then we go through a fancy process called garbling to actually use this circuit to answer the question without leaking any information and so the way this works is we designate one of the two parties in this case bob to be what's called a garbler i'll explain this in a bit more detail as we go along but basically what he's doing is he's

taking this circuit that they both know and he is choosing some random things in an attempt to make it so that alice can evaluate the circuit but she can't really understand what's going on when she does it so she can't actually specify inputs to the circuit because they've all been replaced with random stuff she doesn't really know what's happening inside of the gates she can evaluate them but she's sort of oblivious as to what the actual inputs or outputs were at every step of this computation and she can't interpret the outputs and then what happens next is alice and bob engage in something called oblivious transfer which is a very fundamental cryptographic protocol that allows alice to get from bob the correct

inputs to put into this circuit because remember it's garbled she doesn't actually know how to input things to it only bob does so this allows her to get the correct inputs and only the correct inputs without bob learning anything about which of the two inputs she got for each input where so each wire can take on the value zero or one it's a digital circuit alice is able to learn either how do i input 0 or how do i input 1 but not both and bob does not figure out whether she learned how to input 0 or 1 for each wire and then alice evaluates the circuit and eventually what pops out is a final

answer that alice can't make sense of so she sends it to bob to be interpreted bob knows the mapping from the answers to what they mean and then he discloses dallas it says you're richer but all the while because he has no idea what inputs were given to the circuit or what any of the intermediate states of the circuit were all he learns is the final answer and because she really had no idea what was going on the whole time she again only learns the final answer from bob so if we look inside of one of these gates the idea is actually kind of slick it's not what i'm going to use for the rest of the talk but it's cool enough

and i just thought people would enjoy it so i'll explain how it works inside of each of these gates this one right here happens to be an and gate there's a truth table that describes precisely what this gate is supposed to do so i'm sure you're all familiar with this concept but just to be thorough i'll say it anyways so if the input wire labeled a takes on the value zero and the input wire labeled b takes on the value zero then the output wire a and b will be zero of course likewise if we have a and one we get or sorry zero and one we get zero one and zero gives us zero it's only if we happen to have both

input wires take on the value one that the output should be one and so during the garbling process what happens is bob the garbler chooses completely random unpredictable things to you to play the role as tendons for the zeros and ones in that truth table so on the a wire if the value happens to be zero then in the garbled circuit it's going to use this thing a0 and a0 you should think of as a big long like cryptographically long random string that by looking at it doesn't say anything about zero there's no way to infer from the string that it means zero and then he chooses a different string a1 to as a stand in for

one in the truth table and then he chooses uh likewise b0 and b1 as stand-ins for zero and one on the b wire and c0 and c1 as standards for 0 and 1 on the output wire and so of course so far we've done nothing useful all we've done is replaced 0 with a big long string that means 0 and one with a big long string that means one but then the next step is kind of clever so what we're going to do is we're going to actually hide the mapping from a0 to a1 or a a0 b0 into c0 and a0 b1 into c0 and so on using encryption with a0 a1 b0 b1

being the keys that we use in the encryption so in particular we're going to do a two layers of encryption on each of these the first row here uses b0 and a0 as the encryption keys so if you know a0 and b0 you can decrypt this value but if you don't know a0 or you don't know b0 then you're going to be unable to decrypt this and it's just a basically a random blob that means nothing to you and then the next row for the zero one we use a0 and b1 as the uh keys for this encryption but we're encrypting the same thing and these zeros i'll explain what the zero to the end thing is in a moment

and so you can see all we've really done is taken that last column and encrypted it using the values from the first two columns in each case and we still have the only one is in the last row and the zeros are in the other rows the reason that we add the zero to the n thing is because alice doesn't actually know which of these rows she's dealing with so she doesn't know which of these ciphertexts she can decrypt and because c0 and c1 are both random she doesn't actually have any good way to distinguish between the decryption failed and i got random garbage versus the decryption succeeded and the random garbage i got was the random garbage bob

intended for me to get so we add the zeros as a way for her to recognize the difference between truly random garbage and the correct random garbage if you get random garbage followed by n zeros this is the right random garbage if you get just random garbage this is the wrong random garbage and so now to evaluate the circuit all alice has to do is try to decrypt each one of the cypher texts and one and only one of them is going to come out with the zeros and then she knows okay that's the output the part that came before the zeros is the output of this and she can feed that into subsequent gates and then of course

there's also another step here we need to um change the order of these in a random way so she can't just look at which cipher text in in the ordered list decrypted to infer what the inputs and output must be and we also don't actually tell her a0 and a1 and b0 and b1 when we give her this truth table we only give her the ciphertext so now her only choice is to try to decrypt them all and see which one of them succeeds but she has no idea at this point what exactly she has done she just knows she's evaluated the gate but she doesn't know the inputs nor the outputs and then we string these together implement

arbitrary digital logic circuits and and this is what what i refer to as garbled circuits and so another strategy for doing this sort of thing is using something called additive secret sharing which is the direction that this talk is going to go from this point on so secret sharing is a very foundational technique in cryptography we're using potentially or i guess the very simplest form of secret sharing i mean there's depends how you look at it but this is certainly one of the various very very simple uh most naive ways you could do this so we have a secret in this case the secret is the number a and we share it by just expressing it as

the sum of two things so we call the first one share zero and the second one share one one of these we choose completely at random so it means nothing and then the other one we compute to satisfy the expression here when we when we add them together it will give us a and of course this is all happening in some ring or finite field or mod something so that we get perfect hiding when we do this so now the idea is alice is going to get a 0 and bob is going to get a1 and so neither one of them learns a but between the two of them they have a and a nice property that this scheme

has is that it's what's what we call linear if we have two different sharings of two different numbers you can just add the shares together and everything works out nicely so that we end up with shares of the sum of the original secrets so if i have a share of a and i add it to a share of b and the guy who holds the matching shares of a and b does the same we now suddenly have shares of a plus b and we can also do scalar multiplications and turn this into a way to do arbitrary linear combinations so lots of lots of interesting computations can be done just with linear combinations and this lets you do them

very efficiently while ensuring that neither party learns the inputs or the intermediate values and they can only reconstruct the final answer at the end using this the summation formula so this this lets you solve lots of questions there are lots of problems but of course in order to be super useful we need to be able to solve basically everything which necessitates having the ability to not only add but also multiply secrets together so what about that can we do that um and it turns out the answer is yes otherwise i probably wouldn't be asking the question so how does this work this is actually one of the most elegant uh constructions i can think of so first

we're going to look at what would it take to actually compute a times b from the the shares themselves so that's pretty simple we just take a 0 and add it to a1 and that gives us back a we multiply that by b0 times b1 that gives us back b and then we would share the result of course if you did it this way we would reveal a and b and the product a times b as part of the intermediate values in this computation but it would work so the next step from here the next step from here is actually to take the regular formula the foil formula we all learned back in uh junior high and

express that product in terms of uh something that does not involve reconstructing the secret so we get a 0 times b 0 plus a 0 times b 1 plus a 1 times b plus a1 times b1 and this will give us the same answer and one thing we may notice here is that alice can actually compute this part all by herself and bob can compute this part all by himself so we can actually already compute part of this without doing anything clever right alice holds a0 and b0 she can just compute that and likewise for both what we need to figure out is how to deal with these pesky terms here that involves something alice knows and

something bob knows so of course we can't just send both of these values to the same place because if we send say b1 over to alice well she already knows b0 so then she would learn b and we can't send a0 over to bob because he already knows a1 and so again he would learn a so we need to do something a little more clever so what do we do we do what cryptographers love to do we throw some randomness at it so alice is holding a0 bob is holding b1 i'm just going to show how you do this one this one obviously is handled totally symmetrically and so what we do is we have alice

choose a random number we'll call it r and bob choose a random number which we'll call s and then alice sends her share plus r and bob sends his share plus s and just keep in mind that i'm assuming everything happens in a field or a ring or something where um adding a random number to a value perfectly hides that value so in this case now we've in some sense sent a0 to bob so that he can just compute a0 times b1 but we've thrown this extra r in the mix so that bob doesn't learn a zero and likewise we've done the same thing with sending b1 over to alice and so they're going to actually

do the computation using these values actually not quite but something kind of like that so alice is going to compute a0 times b1 plus s and bob is going to compute the negative of s times my parentheses are in the wrong place by a 0 plus r and if you look at what happens when you add these two things together you can see here that it basically gives us what we're looking for but with this one extra term that we still don't know how to deal with so these two cancel out we're left with exactly what we wanted minus r times s which seems like the same problem we started with right only alice knows r

only bob knows ass we can't send r over to bob because that would reveal a zero because he just learned a0 plus r we can't send s over to alice because that would reveal b1 um after we had sent b1 plus s to alice so we seem like we're kind of stuck until we take a step back and realize that unlike a0 and b1 which were actually shares of sensitive information r and s are really just random stuff that we don't really care about you know it doesn't really matter who learns them as long as it's not alice and bob who learned them and so now the idea there's several ways you can complete this

the traditional way actually uses that same oblivious transfer thing that i described in the previous when i was talking about garbled circuits in order to compute this product it's a little bit uh a little bit messy to describe but the idea is you know pretty natural you're basically doing school book multiplication but every time you need to do a multiply you you're doing it bit by bit and every time you need to multiply you just go to the other guy and you fetch the answer to what if we were to multiply your bit by zero or what if we were to multiply your bit by one and you fetch one or the other depending on what

your bit is and then yeah we we just add them all up and everything works instead the approach that i'm going to describe here involves a third party who exists purely to help us and so this party is something that we call a server in this literature uh or in the the case of the two plus one party computation on the slide this is the plus one so we distinguish the plus one from alice and bob because the plus one is special his role is that he takes no inputs produces no outputs and does not keep any state the only thing he does is chooses some random numbers and then does some simple computations on those random numbers and

then tells some stuff to alice and some stuff to bob uh based on the random numbers it shows and the reason that we were very interested in protocols with this very special type of third party is because we can actually implement this third party as a two-party computation between alice and bob that happens offline before they actually want to do their calculations so that they can do the online costs as if they have a third party helping them which makes things more efficient at the expense of having done something expensive previously if we instead had a true three-party computation then you're forced to actually have all three parties online when you're computing it and you can't simulate one of the

parties using the other two so for now i'll just assume this party exists but keep in mind that this party doesn't actually need to exist this party can be replaced with precomputation okay so now how does this change so in addition to send danger to choosing rns this party is going to choose a another value t and then he's going to send r and r times s plus t over to alice so now alice learns r like she before she chose it now she's being told what it is and she's also being told the product of r and s but with this extra t added to make sure she doesn't actually learn anything about s from this value and then bob is

learning the s value that he knew previously plus the t that was used to prevent alice from learning r times s so neither one of them has learned anything useful that they didn't know before or at least they they're not learning any information they didn't know before they actually are learning something that will prove to be useful um and then what happens next is the exact same protocol we had before except we just add in these extra terms to make the cancellation that didn't work out before workout suddenly so before we didn't have this extra minus rs plus t or this extra t and we were left with precisely what we wanted plus rs and so now we are subtracting rs

and t and then adding back the t which cancels out the two t's and the r s cancels the one that we wanted to get rid of before and lo and behold what we end up with is precisely the product we were looking for and then by doing this also with the other term that we didn't have we've now successfully computed shares of the product a times b without alice learning a or bob learning b and so why is this useful it turns out that much like uh digital logic circuits you can actually compute anything using what are called arithmetic circuits where the only two gates you have available are addition and multiplication we already

established that addition is super easy in this style of computation and we just showed that you can also do multiplication it's more costly it involves rounds of interaction between alice and bob they have to send some messages back and forth which is annoying but it's totally doable and so now that the trick is to basically try to come up with circuits for doing interesting things that don't involve too many multiplications because the multiplications are annoyingly costly okay and then in theory as i i just sort of alluded to anything a computer can compute at all this these both digital and arithmetic circuits both the garbled circuit approach or the additive secret sharing approach can compute the same thing

okay there's just there's caveats here but um at the end of the day if a computer can do it they can do it it's what's called they're both what are called universal gate sets or they implement a touring complete model of computation so if your computer can do it they can do it it'll be slower but they can do it

the problem of course comes from the fact that not all computations are linear or even anything remotely like linear so this is just some arbitrary curve i drew to illustrate a very non-linear function and the question is what do we do if we want to evaluate something that is very non-linear it turns out that there are many many many computations that we want to do on a daily basis that are mostly linear but then there are some critical steps that are highly non-linear and it turns out when you try to implement these with additive secret share you get a scheme that is almost super efficient except you have one or two little sub steps that are

so brutally costly that it basically renders the whole thing unusable and on the flip side when you try to use the garbled circuit approach we find that many many many natural computations contain lots and lots and lots of linear steps and a handful of nonlinear steps and the garbled circuit approach is actually very very ill suited to the linear steps it can do them it can do anything but the they're quite costly you can't do things like loops and you can't do conditional branching you have to take all branches to hide what's going on so at the end of the day it ends up being very inefficient to implement linear stuff in the garbled circuit approach

but it handles the non-linear steps about as efficiently as is possible and so there's been this major trend recently of coming up with efficient ways to map from linear secret sharing or from the additive secret sharing into garbled circuits and back so that throughout the course of the computation you can actually do everything using the linear the linear stuff using additive secret sharing and then right when you're about to do an expensive nonlinear computation you instead do a comparatively cheap although still annoyingly costly conversion into the garbled circuit format you evaluate the non-linear part with garbled circuits and then you do another mapping back into the linear space to continue doing all of your linear work

this works fine but we wanted to understand whether you could do something slightly better than this and so the approach that we take is relatively obvious conceptually but under the hood there's lots of interesting stuff going on so the first thing we do is we look at the curve that we want or the curve describing the function we want to evaluate and we try to approximate it using for example linear functions or low-degree polynomials linear is not important but if you can get away with truly linear functions it's the best so we we go along the curve and we just draw tangent lines all over the place and we try to space them out as far as

possible subject to some constraints on how accurate we want the predictions to be or the the approximations to be and then this gives us a way to effectively partition this nonlinear function into a whole bunch of linear or at least low-degree polynomial functions in sort of a piecewise fashion depending which value of x you want to evaluate it at you're going to choose a specific function from this list and evaluate that function instead and we know that as long as x in this particular case x lies between these two i can't really point directly at them i guess they can this way from here to here so we know that this one curve or this line

gives you a very good approximation in that narrow band so we've effectively reduced the problem of evaluating this function to the problem of figuring out which of these bands you are in so far nothing particularly surprising your fancy's going on the problem is that figuring out which of these bands you're in is itself a highly non-linear computation and in fact is a notoriously hard computation to do correctly and if you squint and stare at it the right way it might even occur to you that this is basically just a fancy version of that millionaires problem that i started with we have a bunch of boundaries between these intervals you know specifying the different pieces of this piecewise function and our goal

is to figure out which boundaries were between which is just a bunch of comparisons um using secret values and so this is actually one of the oldest i mean it actually really is the oldest multi-party computation problem considered and there have been papers published on this many times a year since at least the mid-80s and up to today there there's literally papers published on this weekly um by this point giving different approaches with different trade-offs for trying to solve this problem one thing that these approaches all have in common is that they are ridiculously costly and they require multiple rounds of interaction between the parties to do each comparison and so what that means is if we have a lot of regions that we

need to figure out which one we're in we're gonna have to do a lot of comparisons each comparison is going to involve an expensive computation and lots of rounds of interaction and each round of interaction incurs internet round trip latency so the whole computation is going to be quite slow and this might even be enough to discourage you from even in pursuing this uh this approach to computing these functions in favor of the approach that i've described before of just mapping to a garbled circuit where this sort of computation is more natural but we have a different trick up our sleeve for actually doing this so again the problem is to figure out which of

these regions we're in and what we're going to do is we're going to use a different representation so we're kind of going to use the trick that i just said hey we're going to try to do something better but rather than going between additive secret sharing and garbled circuits we're going to go between out of secret sharing and a different representation actually what would appear at first glance to be a very stupid representation to use because it seems like it's going to be very inefficient and that is the representation that takes every number and expresses it as a vector whose length is as long goes basically zero to the biggest possible number and it has zeros everywhere except for a

one in the location of the actual number we're talking about so if our number is x then the x one is going to be one and or the x position is going to be one and all the other ones are going to be zero but you should think of this this is a small lecture i drew here you should think of this as being say a vector over all 64-bit integers so there's actually two to the 64 entries in this vector it's so big we can't even write it down or store it in memory on a computer which is why it might seem at first glance like this is ludicrous but just bear with me for now let's just

pretend that storing such a long vector in memory is no big deal so once we've done this then the problem is actually fairly simple we could have the server or third party send shares of such a vector to alice and bob and when i say shares of such a vector um i actually mean a vector like that but not necessarily with the one in the correct location so you can see here i use j as a subscript so what this what the server is going to do is it's going to choose j completely at random and then construct one of those vectors but with the one in the jth position okay so that's completely random and

then along with the vector it's also going to send them shares of where the one actually is because the one is in a random location that has nothing to do with where it needs to be that's not very useful unless they can somehow figure out where it is and do something with it so we're going to between the two of them they're going to know where it is but individually neither one of them is going to have any information about where jade is then from here it's actually fairly simple to complete the process so alice is going to subtract her share of j from her share of the x the input to the function we

want to evaluate bob is going to do the same and then they're going to exchange the they're going to send these things to one another given both of these values they can just sum them up and now they both know x minus j so x is the secret that no one was supposed to learn j was just a random thing so it's perfectly hiding x and they both know it and then we're going to do something kind of clever here so we have our vector e sub j it's been secret shared so alice doesn't actually know where the one is but she knows there's a one in here somewhere and she knows the location of the one

is somehow related to this blinded copy of the input she actually wants to evaluate the function at and so what she's going to do is she's going to cyclically shift all the entries in this vector by this amount right or rotate i guess you could think of it she's going to rotate to the vector and what this is going to do is the 1 started at position j and now she's moved it cyclically around by x minus j which means that it ends up now in position x so they suddenly have shares of the vector that puts the one in the right position neither one of them knows where the right position is but they have it in

this this representation and then from here it's a simple dot product they just take this vector they dot product it against the vector of what the polynomial should be for each of these points and the thing that pops out is secret shares of the polynomial or the line and the example i gave that they need to evaluate to get a good approximation to the original function at x and i guess one thing to keep in mind here is that these functions are constant within one of those regions so as i drew this it looks like there's many many many functions here there is many many many zeros and ones in here but in practice when we represent this

we really just keep track of one function per interval and then we implement this dot product in the sort of obvious way where every one of these values that corresponds to the interval gets multiplied by the same f and so on and in fact because these things are all known to be zero and one we can actually sum up or rather take the x or even of all the entries in a given interval and then just multiply that by f and so this dot product is actually much more efficient than it seems the problem we still have of course is um what about that vector what if it's like super long which it typically will be i mean typically

we're going to do this arithmetic just with the integers mod 2 to the 64 or something like that so that we get fast arithmetic on our computers which means that vector would have to be 2 to the 64 bits long which is ludicrous and so this is where dpf's come in so dps are a relatively new cryptographic primitive they actually are a solution to a very long-standing problem a very long-standing and ubiquitous problem in cryptography which is precisely the problem of how do you represent one of those really long vectors that has a zero everywhere except for one specific location without uh in a secret shared form without writing down something that is anywhere near as big as the vector

and so the the construction is kind of cute um for those of you that are familiar with the notion of pseudorandom generators the it's based purely on pseudo-random generators that you can implement using um say aes or something and then on modern hardware it's blazingly fast uh if you're not familiar with pseudo-random generators just think of this as a random number generator but a very fancy one that has very strong cryptographic uh guarantees as to how good the randomness is and so the way that we're going to represent one of these super long vectors is using a recursive construction that is deceptively simple i mean uh i mentioned this solves a long-standing problem it's kind of the way that i'm going to

describe it here will probably leave you wondering why it was a long-standing problem when it's so easily solved but this is you know hindsight is 20 20 you're standing on the shoulders of giants and uh this was not obvious at first so the idea is is quite elegant we choose these seeds seed zero and seed one as the first step in sharing the vector so c0 and seed one are just seeds they're completely random they've got nothing to do with the secrets that we're trying to share they're just random and then we apply a pseudorandom generator to them to produce something that looks totally random but is twice as long as the seed so w and x these two

children are each the same length as the seed likewise y and z are each the same length as the seed and they all look completely random now our goal is to coax one half of each of these outputs into being equal so in this case we're going to make w and y we're going to somehow force those two to be equal but we're going to leave the x and the z not equal and we want to do this in such a way that nobody who's evaluating this thing can actually figure out which side we force to be equal they know what we're doing they know how the construction works they know that this step they're about to do

forces one side to be equal but they can't figure out which side and the way that we do that is we hand over w xor y so w y we want to set these two equal and we have one of the two parties xor both of their outputs by that value so here the two w's cancel out we're left with the y here we just have x x or w x or y which is just some new random value which i'm going to call x tilde x itself was random so if we replace it with a different random value no harm right there all random values are the same but the left side we've replaced with the

same random value on the right side so these two things are now equal these two are still different with super high probability and then from here we recursively apply the same basic idea i guess there's no harm in sharing w x or y with this guy as well he doesn't need it but as we go on in the construction we'll see that as we apply this idea recursively both sides will need to know those values so i just wrote it there so then the next level of the recursion we do the exact same thing we apply the pseudorandom generator to each of these children to produce more values you can see here that because we have already

turned this value into this value that the children here are the same so this guy's got a and b as children these are just random values or pseudorandom values this guy also has the same a and b as his children because he applied the pseudo-random generator to the exact same seed whereas on the other side where the two seeds were different they've got different children so this guy's got c and d and this guy's got e and f and again our goal is to make one of these two children equal while leaving the other one unequal and not breaking the equalness that we had here because at each step we want it to be that

the xor of these things or rather the difference of these things if you're working in a in a larger field is going to be zero everywhere except at the one entry that we're trying to force the one to be in our inner vector and so to do this same basic trick we give d x or f to both parties but only one party actually xors it into their outputs and so here the e x or d x or f is going to do nothing except change e into a different random value but the f x or d x or f is going to return f into d so now suddenly we have a is equal

b is equal d is equal but this c and e tilled leaves are not equal and we can continue to apply this idea recursively what we ultimately end up with is one seed sized value for each level of this tree and each level of this tree doubles the number of leaves that we have so if we want to represent an n bit vector then we only need log n many of these values and each one of these each one of these values is relatively small so the whole representation of this entire vector is pretty small which means at least we can send it over the wire um we still have a bit of a problem if

we want to take this tree and actually reconstruct all of the leaves because we're still going to end up with a vector that's like 2 to the 64 bits but we've done something useful so we've basically figured out that we can take this massive length n vector and represent it using something proportional to log n bits which uh if you think of like n being 2 to the 64 that's a huge number but log of 2 to the 64 is only 64 which is small even after you multiply that by like the 16 bytes or something that each one of those seeds are it's still on the order of like a small fraction of a kilobyte

to send that entire enormous vector which is super cool um and so we came up with this idea for a paper that we that was recently published at the privacy enhancing technology symposium in that paper we were implementing collaborative filtering for a video streaming netflix-like service so that you could stream videos without the service provider ever learning what you were streaming but still get personalized recommendations based on how similar you are to other people and what those other people have watched all the while the service provider doesn't learn what anybody's ever watched ever but can still actually implement the exact same algorithm that netflix uses to make its recommendations in that setting we were dealing with our

integers were actually fixed point numbers and all of the entries in our vectors were bounded above by one which meant we really only needed to deal with the decimal portion of the numbers and we didn't need that much precision so we just worked with 16-bit integers which meant that going from this short representation log n bit representation to the vector of length n wasn't such a big deal because 2 to the 16 bits is nothing but then after using this technique to do something which seemed kind of magical we really started critically looking at it to see whether this can be extended to do more interesting things uh we were very fortunate that we were

able to deal with such small numbers and still do precisely what we wanted to do but often it's not the case and then recently uh we had a little bit of a breakthrough it's actually a very very simple observation surprising that no one else has made it but it appears to be a novel observation and that comes back to this way the dpfs are constructed so you may have wondered when i described this how do we decide which party xors this stuff in is it like alternating is it how does it work and wait a minute here they both didn't do it and here this guy did it we obviously can't tell this guy you do it but only here along the path

down to the the one because then we would be leaking where the one is and so the real answer to that is that we reserve a couple of least significant bits from the seed at each level and we use that to decide whether or not to xor in the value associated with that level of the tree so there's one of these values for each level of the tree because these values are random about half the time the value is going to say apply it half the time it's going to say don't apply it in the first step we just force the two to do the opposite thing but then thereafter they either both apply it or both don't

apply it if they both apply it it will cancel out if they don't both apply it then there's nothing to cancel out except along this path to the the node that we want to be different along that path we actually perturb these values in such a way that we guarantee that exactly one of them will apply it and the other one won't but it's random which one does and so what this means is that if you look at the flags that say they actually call them advice bits in the literature if you look at the advice bits that say who should apply the correction at this level what you will find is that along the path to the one

they always do the opposite and everywhere else whatever they do both sides do the exact same thing which means if you look at it the right way you can actually from this tree infer at any given node by looking at the advice bit on that node in the two matching trees whether or not the one is a descendant of that node if the advice bits match then definitely everything below them matches and so the one can't be there because whatever is below there is going to cancel out in the two trees and if the advice bits don't match then definitely the one is somewhere below them and that's that and so once you have that

we can actually uh very efficiently figure out for each boundary of each one of these intervals back from that diagram that i had showing the the function being broken into piecewise things we can go to each boundary of each interval and very very efficiently find out is the one between zero and here and then we could do this for each interval um using at most log n evaluations of the prg and our implementations it's usually aes used to construct the prg so you're looking at something like log n evaluations of aes which takes approximately zero nanoseconds on a modern cpu i think uh the last benchmarks we did we're looking like to do an actual useful computation

we're looking at two or three microseconds so each individual aes evaluation is taking on the order of two clock cycles because we're using a fixed key and we're doing one block so it's about two clock cycles or maybe a few more than two clock cycles to apply the uh aes um for each round of aes so you're looking at millions of these a second anyways okay so instead of sending that vector we send these dpf things that i just described we still send the shares of j these guys still do the um sending things back and forth so that they have both learnt the uh or sorry i i'm sorry i've confused myself yeah this

is not quite the same as the last diagram i'm now actually going right back to the millionaires problem that we started with so the goal is to figure out which one is richer this is how that particular computation looks here they they send their own net worth perturbed by these shares of js so this ends up giving you a minus b minus j the minus j still perfectly hides the difference a minus b and now we can adjudicate whether alice is richer than bob by looking at whether or not this is positive if this is positive alice is richer if this is zero they're equally rich and if this is negative bob is richer and so what what each party does i'm

just going to show alice's view but this is bob does the exact analogous thing is she takes her dpf together with this value and she runs the part finding algorithm i just described now i didn't actually give you like the full nitty gritty details of it it's simultaneously kind of obvious in that it's the sort of thing that it would be reasonable to assign in maybe like an honors upper year honors data structures class certainly a intro level grad uh data structures and algorithms class it's an algorithm simple enough that you could assign it as an assignment problem for people to figure out but complicated enough that if i put it on the slides you guys would

all just stop paying attention so you could probably figure out at least roughly how it goes um you're just doing sort of a breadth first search down the tree towards where you're looking for and then you reconstruct the secret from the two we don't actually reconstruct the secret from the true but rather alice gets her answer bob gets her answer and we know that if these answers are equal the ones not below that if they're not equal the one is below that so we use those answers in the previous in the previous thing that i had just described to multiply by our polynomials although in this case the polynomials are just zero or one if the number happened to be

positive the polynomial is a one if the number happens to be zero the polynomial is zero so we get one multiplication and what this ends up giving us at the end of the day is fewer rounds than previous work out of the last 35 years they've gotten this down from linear to logarithmic in the length of the number we have one single round of interaction the first constant round protocol for this we have lower communication cost that's gone from linear to logarithmic which is a very very substantial thing here we've got lower computation cost what used to take hundreds of milliseconds now takes less than 10 microseconds something like four to five microseconds on my laptop

which is actually a very under provisioned laptop of even less on a powerful computer and this approach has endless possibilities i just described how you would do the millionaires problem because that was our motivating example but we're actually in the process of replicating everything that you find in the the standard libraries math utilities so basically if there's a cpu instruction for evaluating it um on floating point or integers our goal is to have it in there in this library most of them are already in there if there is a function in the standard library's math header that evaluates it then our goal is to make sure that it is in there we also have gone through the literature on

activation functions for deep learning and different things that show up in context like graphics or various dynamical systems modeling etc just you know the trigonometric functions any sort of function that shows up in practice that people may have a reason to compute but it that is a pain to compute in this linear setting of additive secret sharing we want to have it so that is just in our library and can be evaluated almost for free so this library is mostly done we're in the process of you know implementing a few different more advanced things that are beyond what i talked about in this talk this was just the basic technique but if you want to do certain things we go a little

bit beyond what what i discussed here and we're still filling in the uh the instructions for how to use this technique to implement a whole bunch of interesting looking functions so stay tuned in the next couple of months that library will hit the scene and hopefully be a real game changer in what sort of multi-party computation protocols we see being deployed so that was the entirety of my talk hopefully inspired some interesting questions from people so let's hear it ah so i i was not looking at the chat but now i see this chat question so we can't just send the binary number indicating where the one is because that would leak the location of the one if

you try to secret share that binary representation the problem is that in order to actually expand the binary representation into the vector form using the naive approach you end up doing one multiplication per entry there are actually two multiplications per entry in the vector so you end up doing linear in n number of multiplications which is uh very much not okay if you're trying to get performance with very long vectors so this idea of using these distributed point functions is essentially your thought but after failing to make your thought work for about 25 years some very very very bright cryptographers the the same actually quite quite interestingly like these exact same cryptographers actually have been

working in the same area for about 35 years they are some of the brightest theoretical computer scientists in the field and they basically spent about 35 years doing precisely what you proposed before suddenly stumbling across this which is in in essence an instantiation of your idea but with all of the the things that go wrong when you try to do it naively uh not going wrong um yeah so the netflix example is clearly just a toy example there is some places where this stuff is actually being used already so i'm currently doing some work with the bank of canada where we are exploring the extent to which some of these very same techniques could be used

if canada were to roll out a purely digital version of the canadian dollar so the idea is to use this stuff to ensure that when you make financial transactions we can enforce laws like the anti-money laundering laws and the countering terrorist financing laws and ensure people are paying taxes and so on all the while hiding all details of how much money any given person has in their account or who they're transacting with or how much they're transacting at any given time so there the parties involved in this are basically bank of canada and various financial institutions who have some combination of confidentiality for proprietary reasons and confidentiality needs for legislative reasons to prevent them from

from just disclosing things or including with one another to break the privacy of the protocol [Music] there have been a handful of instances now in europe where these same sorts of techniques have been used to do interesting calculations that would have otherwise been illegal under european data protection laws and so there's uh there's lots of potential and in places like that where you have different government agencies that hold data sets but they're the legislation says you can't just combine these data sets because combining them reveals information that would have been unlawful to collect in the first place but you are allowed to answer specific questions about the join of the data sets if you can do so

without reconstructing it so there you could use these techniques to actually answer arbitrary questions about data without revealing anything but the answers to the question now let me just read this uh there was a talk earlier about homomorphic encryption i was wondering what's the benefit of garbled circuits encryption on homework yeah so homomorphic encryption is if you're talking fully homomorphic encryption also is a touring complete model of computation and in fact i mentioned that to do the uh without the the third the plus one in that uh multiplication protocol the standard approach is to use um oblivious transfer i should have been more precise there the actual standard approach is to use oblivious transfer plus additively homomorphic encryption

you can also use just fully homomorphic encryption and it's even easier but the the problem there is i said something to the effect of oblivious transfer is annoyingly expensive and the reason that we do it this way is because that's prohibitively expensive the reason that we use oblivious transfer plus additively homomorphic encryption is because it's still way cheaper than doing multiplicative homomorphisms in a fully homomorphic encryption scheme so basically this lets you do the exact same things but in terms of performance it's incomparable when we did our netflix paper i just talked about we showed how you could stream hd video from netflix and train the same algorithm netflix uses in their recommendation algorithm on every single video that anybody

watches on a system whose catalog is the same size as netflix's and whose user base is the same size as netflix's and whose users watch as much videos as the average netflix user does and we determined that the hardware costs of running our protocol would actually be less than what netflix charges per month right now so we're not taking into account um like licensing fees netflix probably pays a fortune for licensing and they spend a ton on developing original content and we weren't taking that into account but just operating expenses for our scheme would actually be enough that you wouldn't run out of money offering this at the same cost as netflix and people could still stream hd video when you try

to do a similar calculation with home morphic encryption you would find that your shortfall would probably be on the order of tens to hundreds of billions a year as opposed to making a small profit because the hardware costs of home fully homomorphic encryption are dramatically higher and this is basically a byproduct of not having multiple parties having multiple parties significantly simplifies the process of actually computing interesting things on on ciphertexts or on these aren't really ciphertexts but on non-public values um that's an interesting question quantum speedups i do not think there's much potential for quantum speedups here to be honest [Music] yeah so the short answer is no there is no known quantum speed ups as far as i am aware

the uh they're probably that this might be a byproduct of there not being a heck of a lot of research on the implications of quantum computing for this stuff because these techniques are information theoretically secure which means that there's zero potential for quantum computers to come along and suddenly break this there's caveats on that because it depends on what you mean by break this if you actually implement these protocols on a quantum computer they might be susceptible to quantum attacks because you may have things that are supposed to just be random or actually entangled with other things the attacker knows but if you're implementing these on classical computers and asking can a quantum computer do anything trouble and

the answer is definitely no information theory tells us they can't there's no computational assumptions here that we need to worry about explain the distributed point functions we actually use prg so that's not totally true but there's no troubling quantum algorithms for that and the main mpc protocols quantum can't do anything my intuition says probably there's no potential to leverage quantum computers to actually speed this stuff up but i would not be even remotely surprised to see that there is a way to use quantum states to represent distributed point functions even more compactly than they are represented in a classical sense yeah my my quantum information theory knowledge is rusty enough that i probably won't pursue that idea but

it's actually an interesting interesting thing to think about maybe i will propose this to somebody who does more quantum stuff than i do next time i am talking to someone who's a quantum expert see whether they they find it interesting

oh these are not seed homomorphic prgs see you can do this with seed homomorphic prgs um they they call those pictured prfs when you see homomorphic prgs they basically the the dpfs that i described only work with two parties and if you want to extend beyond two parties then the standard way to do that is to use seed homomorphic prgs they don't only use lattice-based crypto but one thing they do all have in common is that they are horrendously slow in comparison to the standard prgs that we're using um so where did this the typical thing you do when you want high speed here is you use fixed key aes together with something called the mmo transform which is just a

it's actually a generic construction for building compression functions for hash functions but you can also use it to build simple uh prgs from from block ciphers and if you use it with aes to build a prg then you can take advantage of the aes and i instructions in your cpu and things are ridiculously fast but yes when you switch over to seed homomorphic prgs you're looking at um maybe 10 to 100 000 fold slow down in the cost of actually using these things so it's quite a dramatic difference

but again you're right that the lattice-based constructions that many of them are based on are indeed believed to be immune to quantum attacks they're all operating uh in the wrong setting for stuff like shore's algorithm to have any implications but the the symmetric key encryption that we use is also effectively immune to quantum attacks the grover's algorithm gives you a square root times speed up although that square root time speed up comes at the cost of losing the ability to parallelize and the extent to which you parallelize you lose some of your you can't really parallelize and maintain the squared speed up so that's a little bit of an exaggeration but that's for like a brute force style

attack against um recovering keys because you're really just looking for fixed points there and it doesn't apply to the prg construction so as far as anyone can tell the prg is precisely as efficient or precisely as uh as secure in the presence of a quantum computer as it is not in the presence of a quantum computer thanks for coming guys all right well uh it's been fun i think i'm gonna hit the road