Secure Aggregation for Federated Learning: An ACM CCS 2017 Talk

[00:00:00]my name is Erin Siegel and this is don't work with my other collaborators at google and antonio machado ney at quenelle a since machine learning is in the title I'll start with the machine learning motivation for the problem and then I'll give the problem that we're trying to solve itself I'll explain the issues that other solutions to this problem have had and I'll describe our protocol and how it overcomes those issues and I'll address the security the robustness and the performance of our protocol and then I'll close with a few words about future directions the machine learning problem were interested in is federated learning this is the problem of training a global model that lives on a server with the help of a group or a federation of phones that have training data which they keep on the device so for example if we're interested in training our keyboard predict prediction service that will suggest the next word you mean to type it will try to learn by the words that people are typing on their phones but the information the actual training information should stay on the phones near the traditional cloud-hosted machine learning way to do this would be for the users to upload their logs of their training data to the cloud the cloud would collect it on the machine learning server and the machine learning server would train on that data but if the data is privacy sensitive then this is a loss of privacy because it has to be uploaded directly to the cloud what we're interested in federated learning works a bit different so start with the cloud the server is selecting a group of online devices so it's a thousand online devices and buy online device we mean a phone that is plugged in on a non muted connection and not in use and what the server is going to do is have the client the phones download the machine learning model and the phones our clients will run stochastic gradient descent updating the machine learning model with their own private data so they will each come up with an individualized updated model and these updates are sent back to the server and the server aggregates those updates into a new model and this process can repeat a few times until convergence is reached so that's the idea federated learning in a nutshell it's good because if the user data is sensitive that means we don't need to send that data directly to the server on the other hand the updates themselves might contain privacy sensitive data they're trained on privacy sensitive data and as we've heard in the keynote and other talks there are attacks on models so these updates themselves may not be worth revealing to the server so wouldn't it be great if we could have the server learn an aggregate of the updates from the clients but not be able to view individual updates themselves and that is the problem of secure aggregation that's the problem we're trying to solve so in a mathematical sense we have a number of clients in each client has an input and the goal is for the server to learn the sum of the inputs but not individual inputs what are we more precise we have some threshold value and the goal is for the server to learn the sum of at least threshold users inputs it should not learn individual users inputs or the sum of any fewer than threshold users inputs except these inputs are not scalar values they are vectors and since these vectors represent updates to machine learning models they could be easily a million elements long and we're trying to learn from phones here so previous solutions have one or two problems first of all a previous solutions to secure aggregation either transmit a lot of data and we're trying to keep the overhead here to double the amount of data we would be sending if we just sent these updates in the clear because again these updates are very long vectors or they will fail when users drop out which is a likely situation because we're dealing with mobile phones on a real network now the basic idea which we do share with other work is that each pair of users will come up with a masking vector and the or will come up with a pair of masking vectors that sum to zero so we'll every pair have a masking vector so that each client has one mask for each other client and every pair of these masking vectors that are generated pairwise sum to zero so when the clients send their inputs they will add all of the masking vectors that they've generated and since these masking vectors are sampled randomly the inputs will also look random but when added together these masks these masks cancel out which means that the sum of all of these values computed on the server is actually equal to the sum of the inputs without any masks so this is good this is basically what we want we want the updates to machine learning models to be aggregated without learning the individual models themselves we have that but remember there are two problems first of all these vectors are large so how do we do agree efficiently on them and second of all what do we do a few drops out so remember we have these pairwise masks that cancel out but suppose are some users don't send in any input that means that the pairwise masks other users generated with them will not cancel out with anything and the output will not be recoverable because it's still masked so that's something we have to deal with so I solve the first problem we'll use pairwise diffie-hellman key agreements this is fairly standard we have some public generator G and R prime modulus P each client comes up with a secret and this is going to be a new secret key for each one of the protocol each client comes up with a secret key and G to that pair of the secret key is a public key sequence will broadcast their public keys via the server and the server will reply with all other public keys from other clients and now each client can simply raise all of the public keys it got to the power of a secret key and this will give them one shared secret with every other client now these secrets are scalar values but we can use them as the seeds to a pseudo-random number generator and just run the pseudo-random number generator until we get million element long to however long we need vectors that we can use as masks so this is good because we don't have to transmit these giant vectors during this step it's efficient broadcasting via the server makes sense because mobile phones don't actually really support peer to peer communication anyway and as we'll see in a moment having fewer secrets on the phones will make it easier to recover in the case of dropouts so let's remember why dropouts are a problem we need to cancel out every mask and some masks are not present to be canceled out so how do we deal with this well use another well-known technique called key event threshold secret sharing in the way the idea of it is that you have n shares of a secret and any point possessing K of these tears can reconstruct the secret perfectly but any party can possessing fewer than K shares information theoretically learns nothing you standard way to do this the Shamir secret sharing method is to come up with a polynomial of degree k minus 1 such that the y-intercept is equal to the secret and then you come up with end points along that polynomial so that if you possess only one point or fewer than K points so for example here we had two of three secret sharing you don't know what the polynomial is and therefore you have no idea what the y-intercept is but if you have two points or K points and you can interpolate the polynomial through those points and recover the secret easily just by looking at the y-intercept so this is what we're gonna have all the clients do they'll do secret sharing they'll come up with a random polynomial and pick some random points along that polynomial and they will share these points with each other now this exchange is technically happening through the server but we have this is after the diffie-hellman key agreement step so this can be encrypted so each client at this point will have one secret share for each other client and now what we'll do if clients drop out after everyone else has sent input is we'll have the server ask the clients that are still online for shares of the dropped out clients secret key and remember the secret key is only to be used during one run of the protocol anyway so the clients will respond with the points on the polynomial the secret chairs the server will interpolate the polynomial and recover the secret key of clients who are not dropped out and now that it has that secret TV hum and key it can replay definite key agreement to regenerate the masking vectors so once we've regenerated all of the masking vectors that that client would have used had it been online we will have everything cancel out and we'll be able to recover the sum of the inputs of the users who are still online and remember our goal we want the server to learn the sum of the inputs as long as there are certain threshold of users online so this is good because if we have enough honest users and a high enough threshold that means that even a coalition of the server and some dishonest users cannot reconstruct the secret and I'll talk about that more later on but we do actually have a privacy issue here because we're dealing with mobile phones on a real network it's possible for a user to appear dropped out when really do the network delays their input is simply late and this is a privacy risk because even if the server is honest but curious it's already recovered the dropped out clients private key which means it can regenerate that clients masks and it can learn that clients input so here's what we'll do to solve that instead of just using these pairwise masks will also have an individual mask for each client now these individual masks don't cancel out with anything but will rely on the fact that the server should not be able to learn both the individual mask and the pairwise mask for any client so since they don't cancel out will actually during the secret sharing step have them make shares of two secrets the diffie-hellman key and the individual mask key will do as before we'll separate those keys into shares and swap those tears among other clients so now each client will have two shares for each other clients and in the protocol after users have sent input where some users have not because they dropped out what we'll do is we'll have the server request one share for each client for clients that are still online this will be a share of their individual key for clients that dropped offline this will be a share of their diffie-hellman key the clients will respond with the appropriate shares the clients will only send one of the two shares the one that was asked for for each client the server can reconstruct the keys it needs and start canceling things out for every client that dropped out as before the server can reconstruct its diffie-hellman key and compute the pairwise masks for each client that didn't drop out the server can reconstruct the individual key and eliminate individual masks and by eliminating both the end of it and while eliminating individual masks that don't cancel out and the pairwise masks that don't cancel out we get the sum of the users who are still on limes inputs now notice that this protects the privacy of the users who WestEd online because their pairwise masks are not revealed to the server and suppose now again that some offline users input arrives late their security their privacy is still protected because the server already reconstructed the diffie-hellman key but not their individual mask key and now that's already asked for one of those two shares it can't ask for the other so that's our protocol and now I'm going to say a few words about the security of this protocol the way I just went over it it is secure against honest but curious adversaries we talked about this in the paper um it can be made secure against malicious adversaries with a few extra steps only one extra round of communication and it can be made secure for a different settings of who is malicious or who is not if we suppose that the server is honest but curious and the clients may be malicious then what we can do is set the threshold to any value we want remember this is the fish hold where we say the server will not learn the sum of more than threshold users updates and that guarantee will hold and the cert the protocol will complete as long as more than that our n- threshold users do not drop out as long as fewer than 10 - official use drop out the protocol will complete in the case where the server it could be malicious and the clients are honest but curious we have to make one additional assumption that is that either there is some kind of private key infrastructure like setup where clients can recognize not each other's identities but know that there are real clients there not quite of a civil attack or we have to assume that the diffie-hellman step occurs honestly but with an assumption like that we can set the threshold high enough so that the server only adversary cannot attack privacy of users and the reason we need to set fire threshold is because there is an attack of server could do if the threshold is too low the server could split the users into two cohorts and Bay and tell all the users in cohort a that cohort be dropped out and all the users in cohort B that core had a drop down and it will recover both of the shares for each client in that case and if the threshold is less than one half the number of clients then it can reconstruct both of the keys for each client and that would reduce its privacy or that would allow that secret to be learned but if the fish hold is higher than one half the number of users then it cannot do this it will learn nothing and we have privacy and will be guaranteed that any sum the server computes is at least half or at least the threshold number of inputs and again were resilient in this case to at least hat to a most half of the users dropping out if we have a coalition of clients and use a clients on the server let's say a malicious server and up to a third of the clients is the limit then again we have just at the fish hold a bit higher because the server could make three cohorts a B and malicious it can have cohort a plus malicious send at one set of keys and B plus malicious set send the other set of keys and it will have two-thirds of the keys for two-thirds of both keys for each client but as long as the threshold is greater than two-thirds then it learns nothing and we still have privacy now there InBev inputs the server will learn in this case of a sum of inputs it will learn the sum of threshold inputs except that the clients who are corrupt could always set their inputs to zero so it will in threshold - the corrupt number of clients honest input some together and and we'd still be secured against a third of it would still be robust against the third of the clients dropping out so to sum all that up we're provably secure against a wide range of honest but curious and active adversaries for example we could also have an adversary that's honest but curious but a server that's honest but curious but also controlled by but an adversary can also control up to a third of the clients we're still secure in that case and we're robust against dropouts so even if a third of the clients drop out the protocol was to run to completion and no matter how many clients drop out privacy is not compromised and we're also communication deficient remember our goal earlier on was to increase the bandwidth used by each client by no more than 2x so we don't want to do any more than double the bandwidth over sending these updates in the clear well we achieve that if we have a million element long vector and a thousand users then we increase the bandwidth by 1.73 73% so that's good and even if we have 16 million element long vectors and sixteen thousand clients we still only increase the bandwidth by one point nine eight which is still less than that double that we were looking for now we did implement this on individual computer and a wide area network and I'll just give a few highlights of our performance the running time for the clients is basically linear in the number of clients and in the size of a data vector when we ran this with a thousand clients it took 23 point five seconds per client of running time the bandwidth as I mentioned is less than 2x the bandwidth of simply sending the inputs in the clear and again when we ran this with a thousand clients each clients been with was 1.15 megabytes um the graph on the right shows the expansion factor as long as we have more than 200 thousands elements in the vector which we do expect to have then we have less than that 2x expansion and the actual data use is linear in the number of clients and more importantly linear in the size of the input which is what we expect the performance on the server side when we ran this on a wide area network with no dropouts or almost no dropouts took 27.9 seconds the performance of the server is about linear says they did a vector but the expensive part of the server's job is running the pseudo-random number generator for every clients that dropped out paired with every client that's the lamb lion so that means that the overall performance based on the most expensive part is quadratic and the number of dropped out clients for the server however this is also massively parallelism right we have the server reconstructing vectors by using a pseudo-random number generator but it can construct more than one vector at a time it can even construct more than one place in the vector at a time so from a server perspective the performance is quite reasonable getting towards into the talk I'll just talk about some future directions here um we're interested in validating client inputs remember we're counting on these user masks to cancel out with each other but it's possible for a malicious client not to compromise privacy but to send random data that was not masks that cancel out and in that case the output will also look garbled now realistically since we're planning on using this for machine learning we'll be able to we should expect to be able to tell if the output is pseudo-random instead of a machine up the an aggregation of machine learning updates but we'd like to be able to detect this cryptographically and that's something we're working on we're also interested in weakening the PKI assumptions I mentioned if we have a malicious server we don't need the full power of a PKI but we need some way to tell the difference between real clients and civil clients so we're interested in trying to figure out how what is the minimum number of assumptions we need to do that and lastly it's on the slide but we're interested in reducing the communications even further than 2x we may not necessarily need to sins to have every single pair of users generate a mask together and we're looking at things in that direction so to wrap up we're doing sakura Gatien for federated learning and we have come up with a protocol that does not transmit more than twice the amount of data that we would normally transmit without any privacy preserving computation and we do not fail when users drop out we can tolerate up to a third dropouts in our stringent security case and that's the end of my talk I'm really take any questions [Applause] just to clarify the protocol so each client's and these shares to all other clients or J's select a subset of users and just send to them if I have a million users they will send million shares to million other users yeah we expected to have fewer than a million users more like a thousand users but yes yes a thousand shares and you'll send one shared each other user I had the other questions well I I do have a question I wonder how you guys thought about applying this technique to any of the Google products in the future that's something that's still in planning we've been testing implementations of this and we're planning to apply this in the future thank you I did you know for no sister so I know this is a work of like in the federated training is Google planning to make this open source or like analyzer as a public tool tool for ads to use um I can't say what exactly we are going to do um it would be nice if we could open source it I'm not sure exactly what the plan is okay thank you