Multiparty Homomorphic Encryption from Ring-Learning-with-Errors | Devcon SEA

uh yeah back to the slides now everything appears uh yes so you want two things you want output functionality so you ensure that you you get Y and also input privacy so you do not learn more than what you could learn from the inputs and the outputs and we consider a set of end parties and up to n minus one adversaries which are public and Statics which means they follow the protocols and try to learn much as possible and in fact uh you can instantiate MPC with FH by adding an access structure on top of FH this is man meaning that your restrict who is able to decrypt what and this is done with um a key generation protocol like Jay introduced to you where you secret share the key among the participants you gener some public evaluation key and public Keys then you have an evaluation phase and finally you interact again to decrypt so I will uh introduce now the ring learning f problem which is the base construction on which all these schemes are are based and so you have we work in a polinomial ring of the N minus one modu q and we need free distribution we need a uniform distribution over this ring a small error distribution and a tary distribution and that's it and essentially the ring learning error uh problem is distribution is defined as um a small secret polinomial time a public uniform polinomial plus a eror and you have two hard problem on this ltis watch which is a sear problem essentially you need to either find e or s or the distinguishing problem which askas you to distinguish a ring a valid ring learning for sample from a uniform distribution and from this you can bu build homop encryption and this works because all operation are aine operation of the secret Keys meaning that if you apply an operation on a CER text then it outut a saer text on which the secret V same operation applied on the secret key and it essentially preserve the structure of the safer text so before and after the evolation all you need to do is have a secret key and multiply back the two component of the saer text to recover your message and because all of these are find of secret key sorry yeah there is one more thing to introduce which is Gadget so sorry um to encrypto saer text you simply sample a ring INF sample and you add the message on top of it but sometime you also want to multiply with a message and for this you need another type of uh cyer text which is called Gadget regular the same as before except you decompose your message with a base and what this allows you to do is to do multiplication where the noise is independent of the message and since all operation are aines of a secret key then the setup phase which generates the public encryption Keys is also a f of the secret keys so all the elements in blue they are linear operation of the secret Keys uh as well as a decryption and re encryption which is simply changing the secret keys so these are all linear equations and yeah there's one issue with s square but we will deal with it after and this is great because now you can inst at your protocols as public agreable transcript so since everything is a fine function of a secret key then everything is additive so each party can sample its own secret key locally and then you do some protocol with public transcript which output a sum of all the transcript which correspond to a new transcript that's is encrypted under the collective SEC key which is unknown by anyone but it each one knows a part of the secret key so this is great because with that you can Sun a onetime setup and it has a low round complexity compared to traditional NPC you have two round for the setup uh one of the two rounds is because of this retion key which has an S Square which is not linear in s then the valuation f is completely non- interactive this is why you have a overall low cost of communication and you again need to interact for the decryption and what this allows is uh completely Del delegated delegated public share aggregation and overall it has a sublinear complexity multi party competation so these kind of schemes are implemented in the laal library and it enables N Out of N and T out of n pressure schemes so this is the library that provides all the stateof the art F schemes and it's also widely used for example for the adash privacy and security Workshop where resar is was used by the two um first place competitors but simply implementing these protocols is not enough because you run into a lot of issues when you try to depr them in practice so Latigo has the construction and deployment of the B protocol but when you run them in practice then you run into some security issue and Cent issue for example you need to make sure you have a reusable setup and that everything can be parallelizable but the share for the key which can be quite large in practice can be uh supported by a cent so you need to share the shares you need to support a predefined h circuit evaluation and also you need to ensure that if a client drops for example during the setup or during the OR at the decryption you have some uh robustness but so but it's still secure uh even if you have these kinds of unexpected events and for this um helium was developed by Christ mus and this solved all these issues so alium is bit on top ofo and it provides a framework to be able to do FH based MPC and deploy practical Solutions so we have seen that we have a two setup uh basically you need one round to generate a public key and then one round to encrypt and generate the Elation Keys um but it would be great if we could have a one round setup because if would this would enable much more many applications so essentially why do we have a two round setup is because when we generate one of the public key key this key enables CER text compactness so when you multiply to cyer Tex together they do not grow in size it depends on the public key which itself depends on the previous protocol so it would be great if we could reduce this to a single round and the ideal framework would be that we have a set of predetermined parties and each of these parties will send a single public aggregable transcript to a server and then a server can choose any subset of these parties Aggregates this the part Associated to these parties to generate the corresponding Evolution keys and saer text he can run an arbitary circuit and then it only requires the collaboration of this subset of party for decryption so back to the issue that prevents a two round protoc a one round protocol this is this interaction public key which is an encryption of a square the secret key it's both important for seex multiplication but also for expanding some overc seex which are used for the few boot strappings which is the scheme that is for example used as the back end in Phantom Zone so if we look more at the structure of this key then we see that it's gadet ler text of encryption of the secret key time the sum of all the secret keys so it would be great if we could have a run round protocol that is able to produce um this kind of key dependent message for both LW and grw saer text and well how can we achieve that it's possible with some home operation basically we generate three uh yeah from two R Cypher text and one GW cyer text you can hopefully generate this kind of key dependent message text and here both all the message the F SEC Q the error the the secret Etc they are all um aine so we are all ad which means each party can generate locally interactively and at the end you can aggregate everything and get uh this encryption of of message time secret and this is great because now you have a solution to have this one R protocol and so we are back to our diagram and now we solved the the this was a previous instance where we have one R for the public key generation one R for the encryption and the re resion key generation and this solves and changes it to one R for key setup and one R for the encryption this is already great um but allocating one just for encryption is fine if you want to have Dynamic and flexib on the secet inputs but if the input circuit is fixed for example if you have a starting State like for a game like frog zone or bank account maybe you want to have everything to one round and this is easily solvable basically um the party that wants to encrypt a message encrypts it under its secret and the all other party they have to generate encryption zero under their own secret and you can aggregate everything and this is equivalent to encrypting under the secret the public key of the adal secret key the only issue is that it requires a o communication per seex per party meaning that for each Seer Tex that a party wants to generate all the other parties also need to generate a corresponding encryption of zero and yeah at the end you could have a full one round non interactive setup with encryption if if you want um so these uh Protocols are not in the base library but they are in the my Fork of Library Latigo it's a for C of Latigo that has over 30,000 change it has new function protocols Etc like these non interactive protocols and there are also uh the back end of Phantom Zone which is a r based MPC Focus Library which can evaluate arbitrary functions over a set of private or public inputs and it has a high level abstraction which is focused for resuse developers and uh yeah if you do not know it it's the back end of The Game phom Zone that is uh downstairs and um yeah well I questions yeah I have to for the so we do have some live questions uh you can say here so here we have one on the screen is this a best method than ZK proves um I would say it doesn't solve a same problem it tries to ensure privacy Z proof do not provide privacy so FH and ZK proof are complementary you would use uh ZK proof to for example right now the server you have to trust him that he will evaluate the correct circuit and so what you get is a surer text which looks like ROM noise uh how can you be sure that it's not a malicious Seer text which when you decrete it will leak some information so you use proof uh to have a proof of the server did evaluate the circuit it was asked to evaluate all right uh we do have some extra time for QA so let's wait for a few seconds to see if there are any other questions popping up oh we have another one what are the main differences between this library and the pre-existing ones like concrete uh concrete primarily focus on TF and theend stack is build on this scheme um these Library they are more generic they I would say more low level also they are not in the same language so I would say first uh if you want to use the rest then uh use concrete um but this Lao for example Pro provides support for bgvs which are scheme that enables vectorize arithmetic over complex number of finite fields and if it is more like single gate arithmetic awesome and can can you give some concrete use cases where one round protocol unlocks yes so basically what it solve is um liveness um now you can just send your share and forget and go offline you don't have to wait on the other parties um to have some interaction to generate a setup and sa text all right uh can you share any insights or number on the performance versus other libraries or protocols uh so okay so multi party F what is essentially solved is the setup the evolation phase is the same as single party F and the setup remains in most of the case um negligible to the evolution of the circuit so there isn't like um concrete difference in practice all right are there examples to use your fortical with the features you mentioned in this presentation yes uh Fork has a folder with examples and there is an example uh that show how to do a full one round protocol for all the use key that will be used in practice uh what resources would you recommend to learn about multi-party homomorphic encryption um I would recommend to join the Discord of a.org they have a lot of it's a great community and there are channels to learn and to discover to ask questions and um there's always someone online and they will point you uh toward the correct references if you have a specific questions all right I guess the next question is also kind of uh related to the previous one are there any posts or Publications where we can learn about these protocols so yeah unfortunately right now no it's only in the library but we will um submit something for the f.org conference which will happen in March uh the thing is that these are very simple and small protocols even if a s a problem that was not soled before um for question of time we do not have the resource to produce something but it will be there in a few months uh one last question what are the challenges in this space we should look into um right now the I see two challenges that people fac in practice uh we have a lot of people that complain that the setup is heavy like few hundred megabytes to few gigabytes depending what you want to do and depending the circuit you want to run the overhead can be quite large so a lot of people say that if has a million to billion time of override but it's not really true it depends really on the circuit you want to run some f circuits are as fast as PL Tech circuit but they are very shallow um so it's use case basis uh personally it I look forward to have GPU or Hardware acceleration for f it would make things a lot more practical but I've also we had collaboration with um people in um the medical sector and they said they did not care if it would take three weeks for the competition to finish because it took them two years to get the data so it was nothing for them all right so that's all the questions thank you guys so much for coming and let's give another round of applause to thank you