TFHE Deep Dive: Fully Homomorphic Encryption Explained

[00:00:01][Music] all right great everyone so uh once again for those of you who just joined welcome to this third homomorphic encryption meetup um you know we're just keeping things very friendly here you know this is not like an official conference or anything it's really just a space where people can talk about homomorphic encryption secure computation our first meet up uh pascal introduced the homomorphic encryption our second meet-up yehuda had introduced a multi-party computation and we felt that uh given the people attending it made sense this time to do a deep dive on one of the homomorphic encryption schemes called tfh of which elaria is the co-author so today is going to be more technical than the previous meetups so i hope you guys are going to be okay with that um but it's still going to be you know open for questions if you have questions oh near yes so it's going to be recorded everything is always recorded and posted on fhe.org uh sorry if the website is not really designed or anything we're just using it as a repository for the pictures of this meetup so as i was saying you can ask questions in the chats damian myself and some other people from zama will be moderating please do not unmute yourself and ask questions directly ilaria will be stopping at specific points to basically answer questions uh so don't worry you don't have to wait until the end of the presentation to ask your questions you can ask them as we go and when we see that some of them are relevant to what she's saying right now uh then we're gonna open up for questions um we're gonna try to keep things between an hour and an hour and a half um and that's pretty much it and uh yeah i guess sorry you know we still haven't found a way to do virtual beers afterwards uh so you know we'll we can hang out for those of you who want to stay here uh are we going to be doing deep in the mat or in the code or both uh well idaria i'll let you in it's a i'd surprise to introduce your talk all right great um so just a very quick word about zama so zama is a homomorphic encryption startup that we've created here in paris uh we have been working on a new version of tfhe that enables to do quite a lot of things uh i don't know if elia is going to talk about what we do at zama specifically or tfh in general but if you guys want to keep in touch we're very open we're very easy to find everything we do is open source uh everything we do is eventually published as well and we've been focusing exclusively on tfh uh ilaria floor is yours okay yeah i'm a muted thanks uh thanks from for the introduction and um yeah for asking me to talk here um so yeah i think you said that actually almost everything yeah so we're gonna have a deep dive in tfh so it's the first technical talk of the series uh it's technical because we're gonna enter into the details but i try to keep it as easy as possible by putting as much images as i could and by putting formulas whenever it's really necessary so i hope you will uh you will follow easily as ron said i will stop from time to time seeing the different sections and i will ask if there are any questions uh so we will take a few minutes to answer uh the most relevant questions and then we will move all the other questions at the beginning during at the end sorry during the q a um okay so um how is this uh presentation organized it's gonna be organized in five big sections uh i will start with a very very quick introduction on fourimmomorphic encryption uh just to recall uh refresh our minds on what foolimomorphic encryption is and then i will start the deep dive in tfh initially i will talk about the ciphertext that we use in tfh then i will start building what i call the building blocks which are in practice mixed operation between different type of ciphertext and then i will move to the bootstrapping so i will explain how we do bootstrapping and i will then finish by talking about implementation and just a few applications um okay so let's start with homomorphic encryption so um fhe fully demomorphic encryption i will call it a lot fhe um is a technology quite new i would say now it's starting uh to date um that allows you as every uh encryption scheme to do encryption of messages so in my in this case the message is x which is going to be the the plain text and the encryption is represented by the blue box with a lock on the bottom so whenever whenever i will use this blue box with the lock means that the message is encrypted so um fhe allows us to encrypt and decrypt mesa just so to put the key things in the box and to open the box uh but it also has additional functionalities so in particular those functionalities are the possibility to do operations over ciphertext so the easiest operation of course is the addition so if we have two ciphertexts of x and y uh we will add those ciphertext homomorphically which means that we are doing the operation on the ciphertext side and the result is going to be a new ciphertext encrypting the addition between x and y and in the same way we can we are able to do multiplication so we take the two ciphertexts of x and y we multiply them homomorphically and the result is going to be a new ciphertext encrypting their product so the first thing which is important is that i noted that the addition and multiplication in the ciphertext space in a different color compared to addition and the multi and the multiplication in the plaintext space and the reason is that uh in the ciphertext space uh very often the addition and the multiplication are performed in a slightly different way than a normal addition or a normal multiplication so we will see in the in the rest of the presentation how this is done in tfh um so fhe means fully homomorphic so potentially we want to be able to evaluate any possible function without any limitation uh composing conditional multiplication with something different uh we're going to be able to encrypt a bit integers real messages and we are able to do encryption by using secret keys or public keys so in this presentation i will just concentrate on the secret key version of the encryption schema but we will use some public keys for other uh for additional functionalities if necessary um okay now that we know what fhe is why fh is important why is so interesting and especially uh where could it be used in real life applications so um of course like in this era where we all have data on the cloud it's uh ophthalmology encryption can be a very very nice tool to protect our privacy so imagine that we have the two parties so us the users uh that are represented by this computer have some data that i will call emma in the slide and there is this cloud provider that is offering some sort of service it can store our data or we can perform computation on our data do just the search on our data so the idea is that we send our data to the cloud the cloud we store it we've performed this search so apply functions and it will send us back to the function f f of m the problem is that the data very often is uh is sensitive so imagine our medical data some genomic analysis or financial data and so on uh we don't want for a cloud provider that we potentially don't trust to see our our data our sensitive data and so in this case homomorphic encryption is very very nice because it allows us to add this nice layer of encryption so it protects with this green box our data and at the same time will allow the cloud to uh be able to perform the same operation that he did before so to ensure the same functionality that it provided before and to send us back the result is still encrypted so in the entire process the message and the result that are going to be encrypted and only the user which is the owner of the secret key will be able to open the the boxes to retrieve the information so in practice the cloud learns nothing about the client data there are no data breaches because even if somebody um breaks into the cloud it will find just encrypted data so it will not see what is the actual data inside and also the location of the server will be relevant so the server could be located everywhere in the world and whatever the privacy regulation in this state are we will not care much because in any case the data will be encrypted and so nobody could access this if not the owner of the secret key so just to give an example of a fun function that the cloud will evaluate imagine that you have your picture you want to encrypt it because you don't want the cloud to see a picture of yourself and imagine that the service you wanna you wanna ask for is to apply a um a funny filter uh in this case i will use the filter cowboy hat well the cloud will be able to apply the filter cowboy hat on your picture without seeing the picture so it will send you back the final result and the final result will be your picture with a nice cowboy hat in the end and the cloud was able to do this so without seeing the picture that you sent to him tweet um okay this looks actually very nice and very very good for privacy for the privacy of our data however it comes with the price and it comes with a certain cost and the cost is due to something that we will call noise in the rest of the of the talk so remember in few slides before i said that we can do additions and multiplication on ciphertext what i didn't say before is that at the first the first time we encrypt our cipher text in a memory encryption we add uh some uh amount of noise this knight is something that needs to be there for security reasons so it cannot be we cannot get rid of it at least right now um and i will measure this noise by using these little thermometers that i will put next to every ciphertext so at the beginning as i said the noise is very little the thermometer signals that the noise is slow but what happens when we do the operations so when we do the additions and the multiplication the noise will grow and especially when we do the multiplication the noise will grow a little bit more than the addition and this is actually a bit painful because if the noise reaches this red limit that i put in the thermometer then we could not anymore decrypt correctly so the noise will impact and the message and will compromise the message so if the noise passes this limit these red limits add correct decryption is not possible anymore so this problem was uh was an actual problem i was preventing to do homomorphic encryption before 2009 and in 2009 actually a researcher from ibm at the time craig gentry found a solution which is called bootstrapping so bootstrapping is used to deal with the noise and to reduce the noise when it starts growing too much so i will i will explain bootstrapping very very quickly the general idea of bootstrapping with images and then in later in my in my talk i will talk about the bootstrapping of tfh in detail so in there we're going to do a very deep dive in the bootstrapping so the bootstrapping idea is the following so you start with a ciphertext of x with an encryption of x and the noise has reached this maximal limit so this means that at this point we are not able to perform any other uh homomorphic operation so we need to stop uh or we need to reduce the noise so there is generally one simple way to reduce the noise which is just decrypting why because decryption means opening the box and if you open the box and take the message out well the noise will go away with the box unfortunately to the crypto or actually the reality is that to the crypto you need a secret key but you cannot give your secret key to the cloud to refresh the noise because otherwise what was the meaning of encrypted in the first place so the idea of gantry is a little bit more um it's it's very smart uh it tells you well let's bring that let's take this cipher text which has lots of noise and let's put it inside a green box so this green box again is a fourimonomorphic encryption schema and putting the blue box with the noise inside the grid box doesn't change anything in terms of the noise of the blue box however since this is a full memory encryption uh the green box will come with some little noise which is measured by this this thermometer next to the green box and now what we want to do is to open the grim the blue box inside the green one which means in practice decrypting the blue box as i said before to open the blue box we need a blue key and so gentry says okay let's give this blue key but encrypted inside the green box so we will call this encryption of the secret key up bootstrapping key and this is a public key it doesn't compromise security and now that we have the blue box inside a green one and the blue key inside of a green box we can perform homomorphically the decryption of the blue box and the result is going to be just an encryption in the green box of the plain text x and what is interesting is that the noise the measure of the output of course has increased a little bit compared to the original noise in the green box but if you if you see in here there is still a little bit of space to perform more homomorphic computation so in practice by using bootstrapping we can do homomorphic computations and bootstrap as soon as the noise grows we will have a little bit space we will do again computation and as soon as the noise reaches the limit we will go back to the bootstrapping so chaining um operations and bootstrapping allows us to evaluate potentially any possible circuit and not adding any limit in the number of operations that we can perform unfortunately bootstrapping even if it's a very very nice technique is the most costly technique in homomorphic encryption and so the question now is do we need to bootstrap all the time or or we can avoid bootstrapping from times two times well the answer is it depends on the circuit you wanna evaluate so if the circuit that you wanna evaluate is small and especially if it's known so you know many operations need to be performed inside then you will use what we call a leveled approach if instead the circuit is very deep so you have to do many many operations and or it's just unknown by the person that generates the secret key uh then you will use what we call a bootstrap approach so level the pro approach means that you will avoid the bootstrapping as much as you can so you will if you know the function you want to evaluate you will count how many operations do you have and you will fix the parameter in order to fit this number of operations inside the amount of noise that you're given of course you have to consider that the largest is the circuit the largest will be the crypto parameters and also the computation will be uh slowest so the more operations you have to do the more it's going to be costly not just because you do more operation but because the operations become more costly um and of course like the circuit must to be known in advance so if you have a as i said like a use case where your secret is small and you know it well level the level approach is uh is very nice however if you want to use a more flexible solution or your circuited depot then you will use bootstrapping so you have no limitations in the number of operations you can do and then you will need to bootstrap sometimes two times okay so what is user actually nowadays um do we use the one approach the other do we use both um well i i will try to explain by using this this timeline that is very very summarized so not all the papers appear in here but like the main ones i would say um so if we if we think about homomorphic encryption when we heard about homomorphic encryption for the first time it was in 1978 where three when three researchers called the rivest adleman industries start talking about privacy automorphisms unfortunately the problem was very hard to solve finding a solution was very hard and for 30 years nobody was able to find a foliomorphic encryption solution until 2009 when gentry proposed the bootstrapping so after gentry presented the bootstrapping research started producing a lot of very nice results so we start in 2010 with a result of by the ghb so the ghp is the name of the authors bandit gentry hallelujah in vancouver so the skin tghb is very very nice very easy to explain actually um and and it's a scheme that um does operations over the integers uh so this is not used in in applications today but it's uh i really love the scheme because it's to explain homomorphic encryption is the nicest scheme that you can find um then in 2011 there is a one scheme called bgb which is the first scheme based on on the problem lw the first full homomorphic encryption scheme based on the problem lwe so lw is a problem pro proposed by uh regev in 2005 if i remember correctly and uh the skin tfh is based on a w so we're going to talk about lwe in a bit later in the in the slides and then in 2012 we have another approach based on and true um which i think nowadays has some little um some bigger security issues but it was a very very nice solution and in 2014 we have another scheme that is based on lwa which is the gsw scheme so um we're gonna the schemes that are most studies now and studied nowadays are the ones based on lwh so the bgv branch i would say and the gsw branch so bgb cesar appearing another variant in 2012 which is called bfv while gsw sees another variant in 2014 so in 2014 we have few um which proposes a very fast bootstrapping for the gsw based on gsw um and so in practice now we see that we have two branches the first one the bjv branch that is using more a leveled approach because bootstrapping is extremely costly and the gsw branch that is using a fast bootstrapping that allows the bootstrapping to be used as much as we want so in the bgv branch we see also cks which is a very famous scheme used nowadays while in the gsw branch in uh in 2016 we see appearing at tfh so tfh is of course what we're gonna uh check today in detail so initially it starts as an improvement of the fuel bootstrapping and then tfh develops many other functionalities unfortunately today we will not have the time to see all the functionalities but we will see a little bit the most important basic functionalities okay so i will stop here for a minute if we have any any questions um so there are some questions about the bootstrapping gentry's bootstrapping maybe um we can go back to this slide and yeah sure more details about the the second box the green one so what is the question um so it how are we sure that the server doesn't have access to the data when we do this operation for instance oh because everything is encrypted like we never exit from a box so when when i represent a box it means that there is an encryption layer if your encryption scheme is secure the server is not supposed to break it and during decryption we never exit from a box so we always are we are always protected by a layer of encryption so we we are sure that the server is not able to see in any moment of the process the the data does this answer the question maybe i can ask yes it seems that when we start the bootstrapping we are having er eggs inside the blue box yes but end of the bootstrapping we have it's inside of a green box yes but in order to completely continue the computation we need it in a blue box again with less noise right we put it in a grid box with less noise yes but the computation is done inside the blue box not inside the green book it's done inside the green box actually so the the computation the the operation that we evaluate is the decryption which means opening the blue box but it's done always inside the green box so we never exited the green box right but but what i what i think what we wanted is to get an x inside the blue box and by the end of the boot thing we have we want to have again it's inside the blue box but we flash noise but we end up with inside the green box yes so this is not a problem when the green box means that there is encrypted with a different secret key um so uh the secret key actually can be the same the blue box and the green box might be the same encryption stream and we will see later that it's very easy to go back to the to the blue key even if we are in the green box so is uh going to the green is not a problem the green could be actually the same as the blue i just put it in color green to make the distinction between the the two boxes okay that's answer the questions thank you okay thanks for the question damien do we have another one or should i continue um someone asked about those two keys the blue and the green who do they belong to they both belong to the owner of the the data and are they different uh not necessary we can choose them differently or we choose the same in case we choose the same key we talk about circular security um which says that encrypting a secret key with um herself is not dangerous for um for security it's said very very um uh how can i say uh not formally this is the definition of circular security so yeah using the same key the the blue key equal to the green key is not a problem yeah and someone asked how is it not leveled uh so is there a way to go back to the blue blue key homomorphically yes we can do what we call a key switching and we will see it's a it's a very easy operation it adds a little bit of noise but that we can estimate so yeah we can go very easily back to the blue key but we need another public key that is called key switching key i think okay so i continue okay should i yeah i mean if you're going to talk about key switching later go ahead yeah yeah well i will talk about it later don't worry okay so let's now start the deep dive and we start by talking about tfh ciphertext so um in tfhe we use three type of ciphertext um the first one is called the lwe lw exactly as the problem lwa because in practice we're using the problem lwe to encrypt this to encrypt the message so what are lwe ciphertext uh they are ciphertext decrypting one single message that can be a bit a modular integer or a real in a fixed interval so um the ciphertext uses to be encrypted as secret key which is a little vector containing n elements and those elements are bits so they are random bits the fact of using bit is not mandatory we can use also different type of of secret keys we can use ternary we can use gaussian keys but for the for this presentation i will concentrate on binary keys so how do we build the decipher text so in practice how does the site decide how the ciphertext is built um so it's gonna be composed by uh n plus one elements the first n elements are called the a zero a n minus one and then there is this element b so the a elements are just random integers in z queue uh so numbers modulo q and the the last element b is billed as the product between the eight elements with the the elements of the secret key uh to which we add a small error and then the message multiplied by this delta which is a scaling factor so the error is um gaussian so it's chosen according to a gaussian distribution so again uh random elements a we multiply those random elements by the key and we add some error then the message and we obtain b um so how do we decrypt if we know the secret key of course we need the secret key to the we can just compute the b minus a times s this will result in delta m plus the error and then we will just do our rounding to obtain the message so um this rounding is a very very easy operation and we will try to understand how does it work in this slide so um let's try to to make this uh very visual uh this is just a toy example this is not using true uh real-world parameters but it's giving you a hint of what is going on so when we work modulo modules that in in that queue in practice it's like we're working on a discretized storage so the torus is this nice circle as you can see we have zero in the bottom then we start increasing one two three blah blah blah blah and then we arrive to 61 6263 so q is equal to 64. so as soon as we reach 64 in practice we go back to zero this is the idea of the reduction modulo q and in practice if we can encrypt if we can use if we use a q equal to 64 means that we have six bits of information that we can use um and then we choose p uh where p is the number of plain text that we want to encrypt in my toy example are gonna be four uh elements and uh in practice this means that we have two bits of information and delta is just a ratio between q and t um so to visualize those quantities uh p is the number of possible messages uh that we can uh we can encrypt so just one of those two messages can be encrypted in one cipher text but we have four possibilities for the message so in practice since we have four possibilities means that we have two uh bits of information that could be encrypted and we will encrypt it in the most significant bits of our uh ciphertext and delta just uh indicates the distance between one message in uh in zq and the next one so the messages will be separated by this quantity delta of elements uh so as we said before we want to compute the delta m plus the error so the error of course must be limited and is limited by delta over two so this means that in practice we put the error in the least significant bit of our cipher text and in the figure in the in the wheel let's say um the the red bars that you see in the middle tells you that like the error that you add to a certain plain text cannot pass the red the red boundary uh so maybe let's just do a very quick example let's say that we want to encrypt the message free so the message free will be encoded by delta m which is equal to 48 in our case so it's here in our torus and in practice it will appear that number three will appear in the most significant bit in the in the binary decomposition and then we will add some error as we said so the error must be smaller than eight in absolute value in this case we choose an error equal to five it will appear in the significant bits and so it will increase will be encrypted in a value 53 so 53 appears in here in the taurus so when you decrypt as in the slide before you compute b minus a s and you find this delta m plus e so knowing delta m plus e retrieving m is very easy why because you will just round the delta m plus e to the nearest message possible which is delta times m and then by knowing delta times m retrieving m is uh it's straightforward okay uh so as i said this is just a toy example in practice we will not gonna use the q equal to 64 but more q equal to 2 to the power of 32 or q to the power of 64.

[00:31:19]um so these are the the the parameters that we generally use with tfh okay so we're talking about homomorphic encryption so we are expecting uh some homomorphic operations uh so with lwe you can do uh additions so you can just add the two ciphertext together by simply adding the a parts and the parts and the result is going to be an addition between the message uh in the first one and the message in the second one and by extension you can also do a multiplication by a constant integer again by simply multiplying this the a part and the b part by this integer you will obtain a ciphertext encrypting the integer times your message um unfortunately we cannot do this easily on multiplication so to see a multiplication we will need to wait a little bit longer so uh the second side so the lw was the first type of ciphertext that we use the second ciphertext is ringwe so wrinklewe does not encrypt only one message it encrypts a polynomial containing n coefficients and every coefficient is a message as in lwe so it can be a bit an integer all so we encrypt a polynomial so we have space for n coefficients in the polynomial so again the secret keyword that we choose now is not a vector but is more a polynomial containing uh coefficients that are again extracted uh again binary this is not mandatory the coefficient could be also a ternary gaussian but in the rest of the slide i will concentrate on the binary distribution and the ciphertext is encrypted in a very is built in a very similar way as lwe so you have an a part and a b part a and b this time are polynomials a the a polynomial is a uniformly random so all of these coefficients are random integer modulus at q and the b part is billed in the same way as before so now we are multiplying polynomials so we will do again a times s you will add an error which is gaussian and you will add delta times your message so right now instead of before there were scholars now we're working with polynomials and again how do you decrypt in the same way as before if you know the secret key you compute the b minus a times s and this will give you an output delta m plus the error and you will round to obtain the message m so again as before knowing delta m plus the error allows you to easily retrieve the message m um in the same way as we did before so now instead of having just a single wheel you imagine that there is a will in every coefficient of your polynomial so if you understood how we found the message before well here you have to repeat just n times and again what are the optomorphic operations that we can do we can do addition and we can do multiplication this time times a constant integer polynomial and the operation is performed in the same way addition is done by adding the a elements and the b elements in your ciphertext and the multiplication is simply done by multiplying your integer polynomial by the a and the b part and this will give you now put a ciphertext encrypting uh gamma the polynomial times m and the last but not least the first type of ciphertext that we use in tfh is called the ring gsw uh so similarly to wrinkle we it encrypts a polynomial containing n coefficients and the secret key is the same as a wrinkle w is ciphertext so again a polynomial with binary coefficients but now the ciphertext is a little bit more complex so we will represent it as a three-dimensional matrix uh so the matrix is composed by let's say different layer in in the depth uh the number of layers is exactly l and in the front every single layer is composed by uh four polynomials uh two in the first line and two in the second one so those polynomials in each line every one of those polynomials of those pairs of polynomials is a ring lw encryption so the second type of cipher text that we saw before and what is the encrypting uh this ringgoldw encryption well in the first line we are encrypting the message mu times the secret key times this fixed quantity q over beta j for j that goes between one and l and in the second line we're encrypting the message times the q over b beta j again not the secret key in this time so mu times beta j in both but in the first one encrypted times minus the secret key [Music] yeah that's it uh so it looks more complex than the others but this nice this more complex structure allows us to do more operations than before so again we can do addition we can do multiplication by a constant polynomial the story is always the same you simply add the a terms and the b terms or you multiply the constant integer polynomials by the elements but now with ring just about you you can also do a multiplication which is different from the other two previous ciphertext so how the multiplication is performed i mean it's not that straightforward it's not hard but is not immediately seeable so again you have two cipher text one encrypting mu one encrypting mu prime and you wanna compute a new ciphertext encrypting the product this multiplication is going to be done in two steps the first one is called the decomposition so you will take the first cipher text only the first one and you will let's say let's concentrate on just one layer of the cipher text so one four times four two times two matrix let's not consider the the the other in depth and what you will do you will decompose every single polynomial in a certain amount of small polynomials in par in practice l small polynomials so aj here will be decomposing to l small polynomials in here dj in l small polynomials in here and so on so the decomposition is a very trivial operation it can be done very easily and it's quite fast and then we pass to the second step and the second step is a matrix dot product so you will take this decomposition and you will multiply it times right now the second cipher text and this multiplication is a matrix multiplication with a dot product in practice so you will sum uh the the polynomials that you multiply will give you an output four polynomials which represent one of the layers in the output cipher text so if you repeat this operations for all the layers in the first encryption you will obtain all the layers in the output matrix and this output matrix will uh encrypt the product between mu and mu prime so it looks like a very complex operation but it's actually very easy to to implement uh and uh edit works uh i will not give the proof of why it works uh you will have to trust me or i will give you some sources in the end so you can check by yourself if you don't if you don't believe this work um okay so this brings me to the last slide of this section which is a summary just to to have a visual overview of what we did until now so even if you did not understand all the details this is the information you have to record from this part of the talk so we have three type of ciphertext lwe wrinkle we and ring gsw the ciphertextlwe is composed by a vector and a little element b and we can perform additions and constant multiplications wrinkle w is composed by two polynomials we can do addition and constant multiplication ringgis w is more complex you have this three-dimensional matrix and you can do in this case additions constant multiplications and multiplication between ciphertexts uh okay i will stop for a second before proceeding to the next section if there are any questions um yeah there was a question about the noise if it's negative in the slide you know with the big experience yes more precisely with the bit representation yeah how does it work if the the [Music] the error is negative yes so if the error is negative of course it can be negative the important thing is that the the the absolute value is uh is smaller than delta over two in case it's negative you should see appearing a bit of sine in this uh in here instead of the zero and uh yeah it will still appear in the least significant bits so it will be still your you will be you will still be able to decrypt even if the noise is negative this is not a problem i don't know if this answered the question um okay go on okay i continue i go to the next session no i think someone was started to ask a question ah okay i'm sorry i didn't understand yes please go ahead hello hi okay so there is a question about rlwe is rlw simply repeating lwe over the coefficients if not is the harness assumption different than lwe not the hardness assumption is i mean you have the wrinkle w assumption uh which is very similar to lwe is in practice the same problem but on rings um so the the plain text you can see it's as a repetition of lwe plaintext but the ciphertext is way more compact so in lwe to be clear the ciphertext was n plus one scalars let's say those guys are elements uh in zq uh i think i i said it here yes so here you have like n plus one elements uh and you can encrypt a single message in ringlwe uh you have um two polynomials each of them with n coefficients so you have two n coefficients but instead of encrypting just let's say two messages you can encrypt n messages so it's uh it's let's say it's way more compact that than lwe you can factor you can pack more messages in a single in a single ciphertext oh yeah okay i might go on with the presentation if we have any other question i think we can take it at the end okay so um now we enter into maybe one of the most complex part of the presentation so brace yourself but don't be too scared i will try to keep it as easy as possible if possible so this part is building blocks so in the previous section we saw operations that we can perform in every single cipher text now we're gonna start mixing them together so we're gonna start making the different ciphertext to interact between each other so the first operation that we have is called the external product so it's very similar to the multiplication in ring jsw but is let's say easier than that one so the external product is that is a multiplication between a ring lwe and a ring gsw so two different ciphertexts are multiplied together the output is going to be a wrinkle wa again and it's going to encrypt the product between mu and m so how is it um perform this operation well it's very easy it's it's very similar to the product of ring gsw you will start with a decomposition of the first cipher text so the lw wrinkle w ciphertext sorry again you will decompose the a element into l small polynomials the b polynomial in l small polynomials and then you will perform this time a vector matrix dot product so instead of having a matrix product you will have a vector matrix product so it's way smaller and what you will obtain in output is two polynomials there are exactly the results you were looking for so instead of doing like the operation for all the layers as we did in ring jsw here you have just one operation to do like one decomposition and one vector matrix dot product so it's easier um it's faster and it gives you as well the product between the two messages but this time you can multiply two different ciphertext types so the external product is very important in tfh because it allows us to uh define another nice building block which is called the simux which stands for controlled views so the nukes gate it's a it's a clear text gate that is well known and it's represented in the slide by this uh this figure so it takes an input three elements b d0 and d1 and depending on the value of b that can be zero or one it selects one of the two so if b is equal to 0 the output is going to be 0. if b is equal to 1 the output is going to be d1 so this operation can be performing clear text by simply evaluating this literal equation if b is equal to zero this thermal will disappear and you remain with d zero which is what you were looking for if b is equal to one or you will remain with d one minus d zero plus zero which gives you d one as you wanted so now how can we evaluate this nice operation which is in practice is that if condition if you want um in homomorphic encryption uh well we will be easily uh we will be simply uh encrypting the values d0 and d1 by using wrinkle wv so the the line the two uh the two polynomials and we will encrypt the b the bit that will select one of the two outputs by using ring jsw and then we will perform this operation by just doing instead of the multiplication and external products and instead of the subtraction and the addition simply subtraction and addition between ciphertext as we saw in the previous slides and this will give us in output a an encryption of db which is d0 or d1 depending on the value of b encrypted as a ring lwe so this block is very nice and it's going to be used a lot in in tfh construction especially of the bootstrapping so keep this building block in mind because you will see it a lot in the rest of the slides okay so the first building block is the rotation and i will start building the rotation by uh increasing the difficulty little by little so let's start from everything in clear text so we want to imagine that we want to rotate a polynomial m of x of p positions so m is gonna be represented by this uh polynomial of course m zero and one times x to m n minus one x n minus one because we're working modular x n plus one and the what we want to extract is that the coefficient mp so we want to rotate this polynomial of p position in order to bring mp in the first position well the operation is very easy it's simply a multiplication between m of x uh times x to the power of minus p so what happens if we do this operation the coefficient mp will be brought in first position so it will be in the coefficient x to the power of 0 the other coefficients will follow in the order and the coefficient that were before mp will appear at the end with a minus sign in front because we are working modular x n plus one so it's a very easy operation it's just a multiplication with between a cipher text sorry between a polynomial and a monomial x to the power of minus p so now let's add a level of difficulty and let's try to rotate an encryption of m of x of p clear text position so m of x is encrypted p is unknown uh m of x is going to be encrypted with a wrinkle that would be so the orange cipher text composed by a and b and again the multiplication the rotation is very easily done it's sufficient to multiply each of the two uh elements a and b by x to the power of minus p and the result is going to be a an encryption a wrinkle w encryption of m rotated of x to the power of minus p so again very easy this operation doesn't add any noise and it's um yeah it can be easily performed but now let's add another layer layer of difficulty and let's not only encrypt the m but also p so we want that p the number of position that we want to use to rotate m is encrypted as well so let's try to easy to make the gain easier by uh supposing that we know the binary decomposition of p so we know p0 p1 p to the k and let's suppose that those this binary decomposition is provided as ring jsw ciphertext so now what to remember the p elements are unknown they are secret so encrypted while the 2 to the power of j is of course a constant and is well known so now what you want to compute again is m times x to the power of minus p to perform the rotations and n to the power of x m times x to the power of minus p can be developed in the way i wrote in the slides and in practice this is just equal to m times the single monomials x to the power of minus p 0 to the power of 0 blah blah blah x to the power of minus p k 2 to the power of k so let's concentrate on one of those powers in particular the power x p j 2 to the power of j so let's just perform the multiplication between m and this x to the power of minus p j 2 to the power of j so again m is encrypted p is encrypted so let's try to understand what we want to found in output so if p is equal to zero what happened in here uh here in the exponent you have zero x to the power of zero is equal to one and so the output is gonna be m so if pj is equal to zero you want m in output if instead pj is equal to one in the power of x you will have minus two to the power of j and so the result you're looking for is m x to the power of two j so maybe you you have already the intuition this is an if condition and how do we evaluate if conditions with one of the previous building blocks by simply doing that simuls so the simux in this case which is the if condition will take in the zero input a ciphertext of m in the input corresponding to one a ciphertext of m multiply times x to the power of 2j which is a clear text value so the operations can be easily done and it will take as a selector p to the j and the result the result sorry is going to be exactly m times x to the power of minus p j two to the power of j which which was what we were looking for so now if this step is clear you you can imagine that it's easy to um build the rest of the of the power to to obtain x to the power of n times x to the power of minus p it can be simply done by constructing a chain of c muxes one next to the other so you will start by p0 so you put in input m and x to the power of minus 1 2 to the power 0 is 1 you will obtain an output m0 which is m times x to the power of minus p0 and then you give m0 as an input to the following simulx which now is taking sorry there is a typo in here here is p1 you will obtain again m1 and you will continue until the end until pk to obtain exactly x to the power of n times x to the power of minus p so you were able to perform a blind rotation which is a rotation of an unknown polynomial by an unknown number of positions okay so this i think it was the the most complicated building block so if you survived until here congratulations uh keep this building block in mind because it's gonna be very useful um we will see another two building blocks but they are very very easy so the the the one we will see now is the sample extraction so it's uh it's a building block that takes an input a ring lwe encrypting a polynomial m of x the ways build you already saw it before and you would like to extract from this wrinkle we one of these coefficients homomorphically so you don't know m you want to extract one of its coefficients and you want to extract it as the lwe so in particular to give an example you want to extract the coefficient n0 to put it inside an lwa so to put it as a message in a lwe this operation is extremely easy it's uh it can be done by simply rearranging the coefficients of the input ciphertext the input wrinkle wb ciphertext in a very specific order uh and by setting the output key as the vector uh simply by copying the elements of the secret key of the wrinkle wwe uh so it's an operation that adds no noise and it's trivially performed by again rearranging the coefficients of the inputs into the output and of course not only the coefficient zero can be extracted all the coefficients could be extracted it's sufficient to rearrange in an appropriate way the output coefficients and then last building block but not least is called the key switching so i already cited key switching before so key switching is an operation that allows you to switch the key as the term says so imagine you have an input an encryption of m with respect to a secret key so very small is my slide in output you can obtain an encryption of m with a different secret key s prime so this operation requires a key switching key which is a public key that i will not detail always build but it's a public key very similar to the bootstrapping key actually and it doesn't only allow you to switch the key but also to change parameters so if you want to change the parameters this could be done with the key switching the key switching can be performed between lwe cipher text but also between wrinkle w cipher text in a very similar way but it can also be used to switch from an lwe to a wrinkle wwe meaning that if you have in practices a little bit the inverse operation if you want of the sample extraction in the sample extraction you extracted one coefficient of the wrinkle we into an lwe in the key switching you can take an lwe ciphertext and put its plain text into one of the coefficients of the polynomial and more generally you can pack many lwes into a single wrinkle we so you can put many many plain text of lws into the coefficients of a ring w thanks to the key switching the key switching has many other functionalities that i will not detail it allows you to evaluate a very regular function that can be public or private we call this technique functionality switching and unfortunately it increases the noise so at the output you will have a little bit more noise than before but sometimes this change of key or change of parameters or packing and moving to a different ciphertext space it's very important so this was our last building block again i have a slide to summarize everything that we saw if something some details before we're missing this is the information that you have to keep in mind to continue the presentation so you have uh we defined the external product which we defined also the cmux is an operation that makes an interaction between wrinkle w and ring jsw giving you in output a range lwe so part of the error is not extremely precise but it's just to give an idea of where the operation situates in the scenario uh we can do a rotation so we can rotate to ring a wb cipher text we can do sample extraction so extract one coefficient of the wrinkle wb into one lwe and we can go back by using key switching if needed so again this is the last slide of this section if there are any questions i will take them now damien yeah so people asked about cmuxes and stuff i think with pascal we answered but maybe there are some people with uh other questions and they can unmute themselves and sure ask directly [Music] okay otherwise we have a question here in concrete or tfh in general is it possible to also use key switching or another way to realize proxy re-encryption which means switching a cipher text to a different secret key using another party public key only okay so you wanna you wanna switch so you wanna move from a type of cipher text to another this can be done with key switching but by using another is public key so i if i understand correctly you're talking about a multi-key scenario and my understanding correctly uh yes so there's um kind of another party which also has a public key and the secret key yes and um you want to encrypt it to the secret key of the other party by only using it's possibility only the secret key of the other party yes so the ciphertext resulting should be encrypted under the secret key of the of the other party and we can use the public key for example from the other party okay but the problem is that in input you have a cipher text encrypting encrypted with the secret key of the first party let's say yes so i would say that if you don't allow interaction from the first party you cannot do this i mean um what you're trying to do is kind of decrypting with respect to the first party and re-encrypting with respect to the second one i suppose this will require interaction and in any case it's i would say it places itself in a multi-key setting so multi-key is possible in tfhe but is not yet implemented in in concrete okay thanks you're welcome thank you for the question any other question yeah someone asked about the external product um is the external product faster than multiplying two lwe ciphertexts uh well you cannot multiply we didn't see the lwe multiplication um so in the lwn multiplication when you say multiplying to lw ciphertext i suppose you're thinking about maybe a bfv bgv multiplication something like this uh so in case you want to do this multiplication you need to do re-linearization so it's gonna be different steps um it's a different uh operation um i'm not sure exactly which one is more costly uh i would say they are about the same cost because the uh the external product um uses the ring gsw doesn't have key switching keys really nearization key stories um i will not be able to tell you exactly which one is the fastest i would say the cost about the same of course it depends also on the parameters that you instantiate with one and the other like if they have the same parameters i would say the cost is very similar but i i will not be able to tell you which one is more faster than the other hope this answer the question what order of polynomials can tfhe handle in practice yeah so we use generally n equal to the the most known parameters i would say are 2 to the power of 10 and 2 to the power of 11 sometimes 2 to the power of 12.

[01:02:34]so 10 11 12 i would say 2 to the power of 10 to the power 11 2 to the power of 12 coefficients so big n is going to be equal to this i think we're good okay great uh so i see by my counter that we are 58 minutes already uh so we're starting passing the hour but this is the last um section and this is the i mean the last intense section then is gonna be very fast in the end so um again it's uh it's a very technical one but if you record that uh the majority of things that i presented before this should be easily to unders easy to understand so we're gonna start slowly so what is bootstrapping uh bootstrapping is the original goal as i explained in the beginning of the slides was to reduce the noise when it grow too much because the noise is compromising the messages so we need to reduce this noise when it grows too much uh in tfh especially we can bootstrap lw is ciphertext so we will bootstrap the first type of ciphertext that you see in here and how does it work the bootstrap well to bootstrap you need to evaluate the decryption circuit so remember open the blue box so in here we want to open this blue box to get rid of the noise homomorphically so we will never exit from a cipher text from us encryption layer let's say so how does it work the decryption in lwe as we saw before it works in two steps you start by computing b minus a s b minus a s gives you an output delta m plus e and then when you have delta m plus e you will round it pass me the abuse of notation to obtain the message m so bootstrapping wants to do this in order to have an output a ciphertext of the same type so lw is ciphertext with less noise so let's start by understanding how it's done uh from the second point so instead of starting from from point number one i will start from point number two and then i will go backwards okay so um i want to compute the delta the rounding of delta m plus e this is my goal so let's start by the the most easy approach imagine that i know the message m m as i said before at the beginning can be let's say p different values so between 0 and p minus 1.

[01:05:13]so imagine that those values are encoded in a in a polynomial that i'm here representing as a vector only with the coefficients so if i want to extract the message m uh imagine that is hidden here in the middle what can i do is simply rotating this polynomial by m position minus and position and this will bring the message m in here so i rotate on this side on the left and i will find the m in the first place so this is a very trivial operation very easily performed it's not what we're going to use it's just to build the idea okay so uh we don't have m we don't know m m is what we are looking for we know instead of delta m plus e let's suppose that we know to compute delta m plus e so delta m plus e is a value that is between 0 and q minus 1 as we saw in the encoding at the beginning so again if i have all the elements between 0 and this time q minus 1 in this nice vector and i want to extract that delta m plus e what i do is simply to multiply this vector times x to the power of minus delta m plus e which will bring this value that i also call the m prime in this first position again multiplication moves the rotation moves the coefficients on the left um okay so if i know the time plus e it's fine but i wanna i wanna starting from delta m plus c i wanna find the m so we're gonna um we're gonna change a little bit the vector in input to our rotation so instead of giving the elements 0 1 2 to q minus 1 we're going to apply some redundancy in our table so this means that we will do some repetitions in our table in practice we're gonna instead of adding 0 1 to q minus 1 we're going to repeat the value 0 delta times the value one delta times up to the value p minus one delta times because remember your message m is between zero and p so to to see it more again we have the q values in here and this is kind of a representation of the torus that we saw in the iconic part of tfhe so the q elements represented in the in the case all the all the cases the q cases represent all these little uh how can i call them teeth of the wheel each of them represent one of the elements in the wheel the repetitions will represent the slices of the torus which means that like if you are in zero uh all the elements in the slice corresponding to zero will be repeated to form this call it mega case all the elements corresponding to one will be repeated to um in a redundant way to f1 and so on and of course y delta repetitions because delta is the amount of elements in every slice so something that you might observe is that the zero case the zero mega case i didn't make it start from the beginning i separated it from uh one part in the beginning and one part in the end this is exactly to um to reflect what is appearing on the torus so um if we start uh the zero in here as we said before the mega case of zero is going on the positive way so it's going in the growing part let's say of the of the vector but some coefficients corresponding to zero also appear in minus one minus two etc so they will appear in the end the part of the of the of the vector so the mega case of zero will be split to one part in the beginning and one part in the end um and so what happens what happens if the if you don't have any error and you are in zero you will fall exactly in the first case in the in in the vector if you have a little bit of error if the error is positive you will fall in one of the following cases but again since there is repetition still containing a value of zero if the error is negative you will fall in one of the previous at the end but again since there is repetition is gonna be encoding the zero as well so i'm gonna call this um uh this well sorry again um uh so instead of doing the rotation as we did before by using the q different values we're going to just use the redundancy and again as i was saying if there is no error i will fall in the middle of the mega case encrypting m if there is a error i will move a little bit on the sides so i will fall in one of the subsequent or previous cases corresponding to m and so in this in this way we are evaluating the rounding of delta m plus e why because we give an input to delta m plus e but we are extracting an output or better making appear in the first coefficient something that encodes m which means so we are doing the rounding okay so i will call this uh vector containing the mega cases v so again it encodes the the different plain text representation of the all the possible messages and so the goal is going to be to compute v times x to the power of minus delta m plus e if we were able to compute the delta m plus e now something that we need to observe is that in here i'm supposing i'm able to use a few elements but q is a very big value in practice so it's generally equal to 2 to the power of 32 and 2 to the power of 64. so using polynomials because here what i'm representing is actually a polynomial of this size is very very impractical and in practice we want to use something smaller to make the computation faster more efficient in practice we're going to use polynomial of size n where n is as somebody asked right before a value that is way smaller than 2 to the power of 32 or 64 is generally 2 to the power of 10 11 12 not more than that uh so we're gonna need to encode the same information in something that is way smaller and this in practice what it means that will only we will only keep in our ciphertext the most significant bit which is where the information is stored and we will just throw away the last scenario bits this will make the noise grow a little bit but something that we can estimate so again we will use only the most significant bits of our ciphertext and this operation will be extremely fast okay so now that we understood how we compute a rounding let's try to go back to the first step which is computing delta m plus e um so how do we compute delta m plus e remember the delta m plus c is equal to b minus a times s so with a minus in front is minus b plus the product between a's and s which extend it is just minus b plus a zero s zero plus blah blah blah a n minus 1 s n minus 1.

[01:12:53]so we want to compute delta n plus e homomorphically the values b a are known because they are part of the ciphertext that value s the values s are unknown they are secret so we're going to provide them as bootstrapping keys encrypted with ring jsw so every single bit of the secret key is going to be encrypted by ring gsw again inside we have bits so the sis are just zeros and ones and so now we will see exactly how the bootstrapping of tfh is performed so we start by setting our vector v containing this redundant messages and we will start in the first step by computing a rotation of v of b positions so in practice in the computation we're taking care of the minus b part and then we will start a little by little adding in the exponents the a i's times s i's so since s i is an encrypted value doing this computation means making a choice if s is equal to zero we have uh zero in the exponent if s is equal to one we will have a zero in the exponent and we actually already saw this operation before and it was during the blind rotation so again we will use the blind rotation in the same way as we did before s0 is going to be the beat in input in the ring gsw is part so the selector and if s is equal to zero we will keep v zero if x is equal to one we will uh keep v zero times x to the power of a zero which is in practice if you if you want v zero times x to the power of a 0 s 0.

[01:14:42]so we took care of the second part we can iterate this process until the end until a n minus 1 s n minus 1 by simply doing a list of c mixes as we did in the blind rotation and so the final result is going to be exactly what we expected which is v the original vector that we set in here times x to the power of minus delta m plus e as we wanted to compute so this is what's the first step in practice so to summarize uh the bootstrapping is taking an input a ciphertext of m and lw ciphertext of m and is computing this blind rotation that rotates this input vector of delta m plus e position in order to bring the mega case corresponding to the cipher the plaintext m in the first position but now i mean if we go back for a second what we wanted in output we didn't want our wrinkle w encryption as you're seeing here we want a lw encryption so again how can we go from a wrinkle wv to an lwe by extracting a coefficient by simply doing a sample extraction so we sample extract the first coefficient which is the one encoding m in the mega case and this is gonna contain the plain text m which was there in the beginning but this time with less noise so our goal of bootstrapping uh has been achieved there is just one little detail that somebody of you noticed in the first place here i have a secret key s here i have a secret key s prime so how can i go back to s if i want to close the circle by simply applying a key switching which is the last building block that we saw in the previous part um and so yeah this is in practice the bootstrapping of tfh um the bootstrapping of tfh in this case the uc is just decreasing the noise but it's actually able to have more functionalities than this in practice the bootstrapping is programmable which means that not only is able to reduce the noise during the the bootstrapping operation but is also able to evaluate a function at the same time so how can we evaluate a function at the same time we simply change the vector that we used at the beginning to do the operation the bootstrapping operation so instead of putting in the mega cases the value of zero exactly zero or one or blah blah blah p minus one we will put instead a value of f of a function f evaluated in zero f evaluated in one f evaluated in p minus one so sorry in practice we are just putting in the test vector in this vector v a lookup table evaluation of all our possible inputs and then what we do we just give this v in input the bootstrapping and the operation is going to be performed in exactly the same way but this time at the end of the blind rotation what is going to appear in the first coefficient of the mega cases is f of m and so we will extract f of m which is the value of the function f in the input m and so we evaluated the function m f in the input m so not only we decreased the noise but we also evaluated the function um so again a slide to summarize everything um we have our free type of ciphertext we saw in here that we can do bootstrapping so remember bootstrapping is the technique that reduces the noise and i note to the techniques to reduce the noise with this dashed arrow so we can bootstrap lwe ciphertext so we can go from lwe to lwe there exists another bootstrapping technique in tfh which is called circuit bootstrapping that uses the bootstrapping itself to be performed it's just a little bit more complex and allows us to go from lwe to ring jsw again by reducing the noise so not only reduces the noise but allows us allows us also to change the ciphertext space to ring gsw so if we bring back all the all the building blocks that we saw in the previous part we see that actually we thanks to tfh we can go whatever we want into the ciphertext space so you can find actually an arrow that brings you whatever you want if you want to go from lw to ring gsw ring lwe 12w and so on so thanks to all these blocks put brought together you can actually um have a large amount of possible operations that you can perform and you can build whatever you want if you're able to combine them in the appropriate way so to finish this section and then i will take some questions tfh doesn't stop in here uh unfortunately like we have just one hour one hour and a half of time so we don't have time to go into the entire tfh but i think what we saw is actually the most maybe important part but there are also other features that are presented by tfh and that might be interesting to see uh we can do of course gate bootstrapping which is uh um the the first thing tfh improved we can evaluate lookup table in a level way we can evaluate to find deterministic awaited automata uh we can use this fanimorphic counter uh we can do the circuit bootstrapping and we can do way more operations so if you're interested in knowing more about this stuff of course we can talk about it in the in the q a session or i will give you just some some references so you can check if you're interested so this finishes my fourth fourth block um the last session will be very fast a section will be very fast but i will take questions if there are any at this point yes can i ask something uh yes sure it seems that during the bootstrap url you have a the the polynomial v that has the encryption of all the possible symbols and and you choose one of them yes right so so it seems that the output of the output is is one of the number of possible uh encryption of each symbol that you have inside v so if you do that many times you will have you start to have verifications and maybe you can you can extract the information again can you can you repeat you cannot really extract the information because you you will extract a cipher text so yes you are extracting information but this information is still hidden so the person that is doing this operation is not seeing anything hello yeah yeah i i i think that i'm asking the the ciphertext uh has a p has a quotation because the cyclotic is one out of of the it is it's one of those cytotec that are encoded inside the polynomial right yes so so you have a finite number of cycle text a finite number of plain texts yes ciphertext after the bootstrap i mean you you know after the bootstrap you still have one ciphertext a single one but but you have the one that come out of the polynomial v yeah yeah but the entire polynomial v rotated is in one single ciphertext it's not separated ciphertext it's just one but let's say let's say you're having v let's say a thousand is cycled encoded does it plain text encoded yeah you have let's say four four plain text let's say let's say you have four play text and you have a thousand uh text of these four playsets so what you're saying is that you have four mega cases yeah and they are encoded in a thousand coefficients so you have i don't know a thousand divided by four should be uh 250 so you have 250 times repeated zero 250 times repeated one 252 and 253 yes so now after the bootstrap i get one out let's say i i put up a symbol zero symbol and i get that one out of that 250 uh so if i do that many times then i'll see that i see that maybe i can see a repetition inside this ciphertext and start to know if you bootstrap the same ciphertext multiple times you will have the same cipher text in output i it will not change it will be always the same there is no repetition like there is no different cipher text that come out yeah so let's say i'll take zero and and let's say let's assume that i can publicly uh encrypt it into uh encrypted zero yes and now i do best buy a bootstrap and get one out of this 250 symbols and then i do it again and again and again and then i'll get the entire 250 symbol ciphertext that's encoded yes but isn't isn't that breaks the the encryption because i can see i mean you know that you're encrypting zero yeah but but what i wanted to know is to learn is that the polynomial v that has the encryption the polynomial v has 250 encryption of zero right i mean the polynomial v is in clear it's given in clearing input so you know already that there are 250 values of uh zero like this is this is clear it's not encrypted is given in clear is rotated by a b value that is known and then you start the blind rotation so you know exactly what are the values inside you can if you want encrypt the polynomial v but then you don't know what is inside the polynomial d maybe you want to evaluate a private function so you might encrypt the polynomial v and so you will give it encrypted but like when you will see the output coming if your the output will be always encrypted so if you didn't know what was v and if you don't know what is m you will not know what is in output in here like everything will be hidden so if you know v in the beginning and you know that the cipher testing is encrypting zero you will know that in output where you will have an encryption of zero because this is the functionality of bootstrapping but if your cipher your v vector is encrypted at the beginning which is something that can be done and you start rotating by a quantity then you don't know what is this quantity you will not know what is the output because it's encrypted so if you are able to know what is inside which means that you are opening the ciphertext is because you have the secret key does this answer to your question yeah i'm trying to understand during the bootstrap where comes the the additional noise that hides the the output uh it comes from the bootstrapping keys so you see in this operation you have the bootstrapping key that enters and the bootstrapping key has some noise and the fact that you're doing operation with the bootstrapping keys will add the noise of the bootstrapping key together and so at the end the noise of course would be less than the beginning because you're starting from something from some clear text let's say but every time you do an operation the noise will increase so the noise will be added and will protect your information okay let's see thanks thank you for the question is there any other questions guys if you have questions because we see a lot of questions in the chat uh it's it's sometimes easier if you just ask them directly this is a very friendly room also just unmute yourself and ask your question and if you want to be extra friendly you can also put up your camera so that you know there's a face-to-face interaction so is there any other question before i continue or if you don't want to put your camera and still ask a question you can do it yeah of course do you have more stuff to present today uh it's very quickly it's gonna be just a conclusion so if you want i will finish so i i stayed in there one hour and a half and then we can continue with questions finish and then we'll take the other questions as well right yeah let's do this so it's gonna be very quick it's actually just a conclusion because like i i would love to talk more about tfh but two hours will be not uh will be not enough so maybe another time um so just to to to finish everything uh to put a conclusion on this thing um we saw a little bit tfh so you you had an initial let's say deep dive into tfh uh if you want to experiment with tfh there exist implementations open source implementation so of course the original tfh implementation is available on github uh the tfh implementation on github implements only bootstrap the binaries gates so you can build the binary circuit homomorphically and there is this also an experimental repository on which the circuit bootstrapping is implemented but again is dealing with binary uh binary plain text um a more recent implementation is concrete which is developed here at zama so concrete is implementing of course tfhe is implementing more functionality so we have the programmable bootstrapping uh the binary integer and real encodings are possible and there is also a module that does noise tracking so it's kind of helping you understand when you should be aware that the noise is growing too much and there are other other also other functionalities there are there are encoded implemented uh there exists also gpu implementations open source as instance new fhe and qfhc are are two examples and i suppose there exists other implementation as well but those ones are the the first one uh that came into my mind at least um so talking about applications i will just make a quick list and i will not go into detail uh tfh is used already to do evoting you can use it to do multi-key encryption so as somebody asked before yes we can do multi-key with tfh it's not uh it's implemented actually and in open source on github but it's like a proof of concept implementation than just to show that it works uh but multi-key uh the multi-clear version of the fha exists uh you can also use tfh to uh in a multi-party computation scenario if you want and you can do machine learning um and and many more applications that we don't have i mean there's no much space and yeah it can be used in many many different ways and maybe something that is uh that is interesting is that the tfhe solution based solution uh was the winning solution in the two past years of the ei dash competition so the adash competition is a competition uh that uh concerns homomorphic evaluation of neural networks so in the last year 2019 and 2020 two solutions based on tfhe won the competition um and yeah i think that's that's all i just put a little bit of biography in here for those that are interested of course if you want to know more about fhe or tfhe feel free to ask me and i think this is all i wanted to say and i already took like one hour and a half so thanks for resisting until they're here if you did and of course if there are any other questions i will be more than happy to to answer thank you very much i don't see the chat so or maybe yes yes i see the chat actually um but there are many many questions i will i will ask somebody to to i mean to a mute and ask me the questions if you have hello maybe i'm just going to steal a question from justine paul uh how does the concrete library padding and precision kind of things map to the tfhe scheme and the encoding you described here which is something i'm wondering as well which is why i'm stealing it from chat okay so i i was very quick on this um so can you repeat the question yeah so in concrete we have uh this padding and precision um encoding right how does that map to the sort of math description that you gave for tfh here okay so the padding is kind of necessary if you want a bootstrap so i i kept this under the carpet uh you will pardon me for this it was just too easy the explanation but yes one bit of padding is necessary uh so in practice this means that we can encode the information only in half of the taurus so tfh already as this and concrete is doing exactly the same so again i put it under the carpet but it's something that should be said in the presentations um and the other one was so the packing and i guess precision right because the precision of course in concrete it's called something slightly different right okay yes um so precision i mean it depends also on the parameter choice maybe i can ask somebody of concrete to tell you more they may give you a better answer than i that i do so um hi so uh speaking yes in in concrete there is this layer crypto api and we try to keep track of the precision as well as the noise and also the bits of padding present in the ciphertext at any moment so does it answer the question [Music] um i guess mostly maybe it's like i have some more technical questions about the encoding thing but i think that's not for here okay thanks damian by the way alex uh uh will be presenting uh the next or the next after now uh fh meet up hill is going to be presenting uh fhe compilers right alex yep uh tilting compilers uh for volume for encryption and how they sort of help you and sometimes don't right uh so that should be also quite interesting so more more practical so i think one one of the things about homomorphic encryption is there is a lot of theory but the implementations uh also require making a lot of different choices and makes it more practical so i think it's interesting also to have sessions that are more on the implementation to explain how these things actually happen in practice so really looking forward to that anybody has any questions oh i have a question about the blind rotate algorithm okay so the during the blind rooted algorithm we have to um discretize the uh coefficients of the l2 is lw cyprotex into a sum uh into a n smaller interest than n so that discretization adds as a significant amount of noise and i'm curious about how um how tfh or zama came up i came over the additional errors that comes from the discretization sure um so it's something that we actually call drift uh so it's the error due to the discretization so as you see like here maybe in the slide is not super clear but like what happens is that uh you just take the most significant bit when you do the bootstrap move right and so this means that actually you're cutting the the tail um the the last part and this operation will add some noise uh so this noise amount uh this additional noise amount can be estimated and so the idea is that before you enter the bootstrapping you are sh i mean how can i say you will be you will make sure that the noise at the input of the bootstrapping is able to still support this amount of noise added by the discretization so you will boost up a little bit earlier than expected in order to be able to also have space for this additional amount of noise that is added by the the truncation by the the surrounding and so this will not um bother you during the bootstrapping is this answering your question yes thank you okay thank you for the question so maybe just a quick additional comment on that uh the the the drift is something that we're actively working on uh counter balancing and concrete will be uh offering some additional features in the near future that will give you much more precision in the programmable bootstrapping than what you can actually get today we literally cannot talk about it now but uh when when this comes out we'll make an announcement on the group as well because i think it's going to be a pretty significant update thank you um would it be like something setting the coefficients of a coefficient with um the power of n or something like that um i'm in initially setting the random numbers into a uh some multiplication of n something like that uh i i i did not understand the question but i would say that for the new things i i will i would prefer to keep a little bit of suspense maybe oh thank you but again you know as everything we do at zama it's eventually going to be published in open source yes absolutely very soon probably nothing we do is kept secret everything eventually gets published in open source but it's uh you know there is a there's a right time to do it and that's going to be soon i hope the thicket keys are kept secret right sorry again all right hello it's just not a funny joke i hope the secret [Laughter] i didn't hear it but i suppose it was funny i thought it was funny actually uh okay thank you everyone mean i had another question sorry yeah glad of course yeah uh i asked the chat before but maybe that was overlooked so i have a question regarding the application to machine learning so you mentioned that that it's possible with tfh to do some machine learning applications yeah and i would think usually you would take something like bfv c library right so something that's based on integers because machine learning needs many linear operations so how does it compare performance with tfhe okay so maybe let's let's re-set a little bit the scenario so you started bgv bfv uh i don't remem i mean one of the two um so um as i explained in the beginning the bgv and bfv um scenarios can schemes can do bootstrapping but the bootstrapping is very very costly so they will prefer to do to use a leveled approach uh so they will do leveled operations so they will avoid doing bootstrapping if possible so um in machine learning of course depending on the on the neural network that you want to evaluate you will have more or less layers so if you have a very little amount of layers maybe some of their approach can be useful especially i'm thinking about so the linear operation of course can be done by linear operations and then when you have the activation function they will try to evaluate it by approximating the function to a polynomial let's say so this will consume layers of multiplication which means the levels in practice and so you will stick into um into the number of levels that you allow to use a very limited amount of operation so a very limited amount of layers if you want to go deeper you need to do bootstrapping and in tfh the bootstrapping is extremely fast so in tfh as you saw you can do linear operations because you can do the addition and the multiplication by constants in every um every one of the three ciphertexts i showed you and then for the non-linear layers like the activation function layers you will actually use bootstrapping so in the bootstrapping as i said you can not only reduce the noise but you can also evaluate a function so in practice what we do when when we evaluate an activation function is that we will use bootstrapping to evaluate this function so in practice the the message m that enters in the activation function will be output as f of n where f is the activation function itself so you will you will evaluate the activation layers by doing bootstrapping and the other layers by just doing leveled additions and constant multiplications and in this case you don't have any more the the depth limitation that you have the in the leveled approach because you can boost track as much as you can and so potentially go as deep as you can and uh we saw in in a recent paper a few um a few experiments uh we were able to evaluate as instance neural network with 20 50 and 100 layers in a bunch of seconds i would say don't ask me the exact time as they are in the paper but it was on the order of a few seconds okay and so the linear layers they will be approximately as fast as with bfv or is that comparable i would say yes like a linear layers are just additions between lwes or wrinkle wwe so and in the fdi they use uh wrinkle w is so it's additions and multiplications between wrinkle w is so addition and constant multiplication between wrinkle w so i would say that the cost is about the same of course it depends on the parameter choice generally bfd bgv has the tendency to use a cmd packing to evaluate many things at the same time so they they use quite large parameters i would say uh with tfh you use a smaller parameters because you evaluate like a single input but of course like it depends on the parameterization but i would say that at same parameter choices it will be it will be the same tfh generally has the tendency to choose smaller parameters because uh we're able to evaluate operations with smaller parameters does this answer your question yeah a little bit i guess yeah so but there's no scienti no but if i mean smd is very yes we don't have a cmd in the traditional way as we intend this imd i suppose like with the slots um in tfh you can use packing in the polynomial packing by putting many messages in the coefficients of wrinkle w which can be used in certain applications like the lookup table evaluation that i did not explain in this presentation um but yeah generally we pack a single message into our lwe so the samd packing can be interesting in case you want to evaluate like a neural network in many inputs at the same time but if you have a single request by a user well you have to put one single message in all the slots so you're a little bit wasting a space um if you instead need to do just one single evaluation i mean one ciphertext one ciphertext encrypting one message is sufficient so smd it's it's useful sometimes but not all the time i would say okay thanks a lot a great presentation follow up on that one it's ricardo here um i so but there is some support for same type of operations you can i didn't understand correctly that you can you can pack and then you can add numbers you can pack in ring a wee and you can do additions in wrinkle we but the packing is polynomial packing so it's it's slightly different so that the packing i think philip um i think was asking uh is called simd so it's um it's working in the fourier domain uh so you're you're kind of doing parallel operations in all the plain text um by moving to this slot space let's say with polynomials you can do polynomial operation which is slightly different so is a different kind of packing for linear operations like additions and constant multiplication is um it's sufficient um the the polynomial packing so you will be able to do the same operation for multiplication it's likely different but you could do something like um adding numbers and sorry adding multiple numbers at the same time pad pack numbers and then then add add multiple sort of sim style representations and then do a lookup table selection on it yes so to do the lookup table selection so yes you can do you can pack into our wrinkle w media will go on the slides you can pack into a ring lwe many messages because you can encrypt a polynomial so in every coefficient of the polynomial we you will put one of the messages you want to pack and then you can do yet the addition the constant multiplication so the linear operations you can do with them in parallel by packing into a wrinkle we but then when you want to evaluate an activation function you need to extract the elements into lwe in order to evaluate the bootstrap the programmable bootstrapping that allows you to evaluate the activation function and then you can of course repack again if you want to because you can kiss oh sorry you can key switch back to ringlw so you can pack unpack repack easily if necessary okay a little bit related to that i think that pascal might already have answered my question in the chat but um i'll i'll ask anyway um i thought this um look up table idea i understand then that let's say that you wanted to do something like um that is not one-to-one you're not evaluating something like the a pre-calculated exponential but you're doing something more like a comparison so let's say that you want to do a lookup table only on the the most significant bit would you be able to do that more efficiently than than just making a lookup table for for all your sort of message encoding bits well i i suppose if you want to just keep the most most significant bits it's just a matter of encoding the right lookup table right you could do it as a lookup table but but then you would have to take like um let's say that you you're encoding two bits so you have zero to three so you would make a lookup table let's say that zero and one maps to zero and one and two maps to ones yes but that could also be expressed as a lookup table or only the most significant bit so i was wondering if it's more efficient to to and and if it's possible to do it that way so it's possible to do it that way yes the answer is absolutely yes um you i mean the fact that you have more repetition like you have only the most significant bits so you have less information might allow you to reduce the size of the parameters but you have to be very careful you have i mean take my answer with the uh as a very let's say um informal answer you might uh adapt to the parameters but need to be careful yeah no i i i think i need to read up more to understand it but it seems like it might might be possible it might be more efficient effectively but in any case it's possible might be more efficient just because you're bootstrapping less information but again be careful with this yeah okay yeah thank you and uh sorry for uh for for taking no thank you thank you for the questions thanks a lot um i have some questions on concrete library um yes um like um the bootstrapping part um like when you create a bootstrapping key it it needs a base log level how does all those things uh relate to the things that you talked just now oh yes so the base log and at the level i keep them a little bit under the carpet but you saw them appearing at some point i tell you exactly what they are um [Music] let me go back for a second maybe here so you remember the the composition part or maybe i can go even a little bit more back in the ring jsw part so you remember that in here in the cipher text you are encrypting the message time s times this q over beta to the j so beta is the base so base log is the logarithm of beta and l is the level and when you do the composition decomposing with respect to maybe it's very small to see it but you're decomposing with respect to beta and l which are the base 2 to the power of base log and l which is the levels that you see in the implementation so uh they are parameters that are they are important for the decomposition part so the decomposition of course is used in the in the product ranges w but also in the external product and the external product is used in the cmux so this means that those two parameters will impact in practice all the operations that you're doing apart from linear operation i would say yeah thanks you're welcome thank you for the question i would stop moving between slides i will i will wait for questions to move guys maybe maybe let's take a couple more questions then we're probably going to wrap it up it's been almost two hours um if you want by the way to ask more questions you know we're very we're very easy to find we're a privacy company that actually is very open and transparent it sounds a little bit counter-intuitive but we love to talk about these things it doesn't have to be just at a meet-up you can reach out to us anytime any final question anybody has like a very pressing question hello hello carefully yeah we can hear you uh i have a question so in concrete library hawkeye you'll see you know include for example how to select the pedium number yeah how to how can i select the pie d select which one uh which number that i can penetrate yeah i mean that if i you will encode there is a include encoder api here api here and then the here is the number of padding um for for questions about concrete specifically so today was really more about the tfh for concrete a lot of implementation details which i think go beyond the scope of today and are actually super interesting to discuss quite frankly if if you have a question uh you can email concrete at zama.ai and we'll get back to you we'll get back to you with with the answers we also have a couple of papers out which might partly address that but yeah just shoot us an email about concrete let's try to keep today about the theory almost yeah okay thank you thank you maybe in that case i have another question um so we've seen the external product and we've seen programmable bootstrapping today and i know how to multiply to ciphertext together with with like a lookup table via some squaring sort of you know exercises i didn't put it in the slides but yeah exactly you also didn't put it in the documentation by the way if remember correctly so that's it which is the commentation sorry uh concrete like yeah that's it i didn't cite concrete i don't know i'm just you know poking some fun here damian it should really be in the documentation that's how you do multiplication that took us a day to forget it but yeah so i know how to do it like with lookup table based bootstrapping but now i wonder how did you do multiplication or and gates in like the non-pbs versions so in the gateway strapping yeah yeah so um [Music] the get bootstrapping is uh maybe to explain it i can go to the to the bootstrapping part just give me one second so in the gate bootstrapping what you're trying to evaluate is a gate which is in practice a function uh so what you will do like the number of messages that you encode is just two in gate bootstrapping you encode them in a in a very special way you encode them in minus one over eight and one over eight um and then you do like an addition or a linear combination initially and then you evaluate the bootstrapping so in the gate bootstrapping the linear initial combination is taking care of the linear part of the gate and then with the bootstrapping you're taking care of the non-linear part of the gate so in practice what you do with gate bootstrapping is just linear combination and a bootstrapping and the bootstrapping is just in the same way as here a lookup table that is encoding two possible output values and uh yeah that's it so it's still basically programmable bootstrapping it's just much like you know much less interesting it's it's it's much easier i would say because it's just like a very simple lookup table let's say if you want to evaluate more complex lookup table then you will have more values but um yes i mean in the end it's a bootstrapping uh bootstrapping is always composed by um modulus switching which is under the carpet when you do the rounding up to the most significant bit the blind rotation as you're seeing in here and the final key switching is unnecessary so uh indicate bootstrap there's just a little additional uh initial um linear combination but it's uh uh costs almost nothing compared to the bootstrapping so again bootstrapping cost as a bootstrapping of course since you have just one bit of information that you're bootstrapping you can choose the smallest parameter possible so it's going to be very fast as soon as you start evaluating more complex functions so you need to store more information inside your parameters grow a little bit but yeah awesome thank you thank you for the question