Efficient Homomorphic Integer Computer from CKKS

Key Takeaways

Okay. Uh good morning everyone. It is my great pleasure to introduce today on Kim. He is currently a PhD student at Stanford uh under the supervision of professor Dan Bonet. uh his uh focus is fully homorphic encryption where he focused uh in both theoretical and practical aspects of FHE systems and more specifically his expertise lies on uh this discrete version of CKKS variant of FHE. So precisely today he's going to talk about uh discrete CKKS exactness from approximate computation. So the floor is yours you. >> Oh thank you so much for the introduction. So let me let me start the presentation right away. So the title of this um talk is discrete CKS. This is um combination of like our recent works like on building discrete systems upon um the approximate scheme called CKKS. And um in terms of like presentation overview, I would say it's more like telling you a story about how do you start with like um noisy uh approximate computation system and try to build um exact computation system. So it will be like kind of a cute mass mass talk I would say but also some some intuitions on uh FH. [clears throat] So I I guess most of you here would know what is uh FHE or fully homorphic encryption. But let me briefly describe what is this. So this FHE is in terms of technology FHE is a a member of what is called priv privacy enhancing technologies or pets. So it allows you to compute um whatever things you want without sacrificing privacy. So um you may compare FHE with different kinds of PET options including a multi-party computation or MPC um differential privacy or DP um trusted execution environment or TE and uh in terms of advantage of FHE FHE is the only option that provides cryptographic confidentiality um together with um no interaction property. So, so as you can see in the table and so like if you just think about like functionalities of like um how what FH do and it it it is amazing because like you can do um whatever computation you want like without really interacting uh interacting with others. So it's nice but but the biggest uh like disadvantage uh is that it is pretty pretty expensive. So um how much expensive where let's say you want to do um some computation uh like machine learning then then in and then the computation cost I would say is usually like three three to four orders of magnitude compared to like the plain text computation. So um that was a brief introduction of FHE and and um I would like to describe uh like a syntax of how FHE works. So the basic example of FHE is where you have a client and a server and you want to do um kind of outsource computation. What what it means is that client has a data which doesn't want and the client doesn't want to reveal the data to the server or the cloud and but but but want to do some kind of of computation and and and and therefore they outsource the computation to the server uh using FHE and and to do this the client first encrypts um their data with FHE and sends the cipher text to the server and in the server side they and somehow uh compute function um f on this cipher text without really looking into the cipher text and then um you get a an encryption of the result you want and then it is sent back to the client and client can decrypt it and um yeah this is how it works and I would say FHE is now already pretty mature like uh since the first development and now like started to be deployed I would say. So for instance um Apple recently um like introduced uh visual search in their mobile devices. So, so how it works is that like uh think of you have have like photos in your iPhone and and um they and uh like you don't want Apple to really like access all all your photos but but like um you want to uh identify any landmarks in the photos then then then like Apple uses FH to like not look into your photo but like they they send the send I mean they get the encryption of these photos I mean actually embedding encryption of embedding of these photos and then they identify uh landmarks in an encrypted form and then sent back to the client and client I mean the user can actually uh see that for for instance oh there's a like a a famous building there and so on so this is one example um and the other application um is uh like like providing privacy in blockchain. So usually blockchains are very transparent like like for instance you get salary uh uh inside blockchain then like like your friends or families or whoever can know like in d what amount you get uh for salary by blockchain and which is not so great and and um f is kind of a good solution in this way that like you can actually like for instance hide your salary salary or or or like u transactions Um and and compared to like other options that provide this kind of of confidentiality like I mean the ZK snarks or I mean I mean the zero knowledge proofs are widely used in blockchains but but like FHE provides some good like efficiency in in many cases because you don't really have to like like prove your knowledge or some or something like like to to provide privacy but you can just upload your cipher text and and and and and then afterwards you can compute whatever uh transaction functions you want. Okay. So now now I want to go to like mass parts of this presentation um and let me formally define what is uh FHE. So FHE is uh an encry encryption system consisting of a encryption function and a decryption function. So it is it is pretty much the same as like what you would think of an encryption scheme but like the the it is called homorphic encryption because it is because the encryption function is homorphic what it means is that let's say you have like two cipher text CT and CD CT ct prime and uh and then you can define addition and multiplication over the cipher text space and it satisfies these two properties. Um so first it should satisfy that decryption of addition of two cipher text should lead to addition of of the underlying plain text and also similar for multiplications. So like since you have addition and multiplication and these operations are pretty complete you can you can compute whatever function as you want um starting from by building like any anything as like a combination of addition and multiplication. So at a first glance this looks uh pretty strange because usually if you have this kind of good mathematical properties then like it is usually insecure. I mean like if if you can add and multiply on like cipher text then like it usually makes makes it easier for you to decrypt the cipher text but uh but surprisingly um uh there there has been a construction from lattises which is a well-known primitive in cryptography uh uh by gentry in 2009 uh like he introduced the concept of bootstrapping which I going to describe later um to to make uh fully homorphic encryption work. So since the beginning of I mean the invention of uh at the beginning of lehomorphic encryption uh there has been like many schemes uh like many FHE schemes that like fundamentally and practically improved the performance of FHE. So in the beginning it was like really slow like like even like single addition or multiplication took like like so much time and it was not like something you could use in your like your application. But since then like like all these like developments uh like improved the performance by like orders of magnitude and and and now like the performance is pretty I mean still far from like plain text computation but like like um usable in in real world scenario. Um so so the first kind of schemes were are called BGB and PFB. So like in terms of functionality you can regard them as like vectorzed operation over some finite fields. So you can imagine like a P is a prime and then and they operate on like modulo P arithmatics and and then like um later um by the development of like techniques called like GSW and like and like um Duka's Michentio scheme and and upon it um like there was a scheme called TFHE which efficiently works on individual cipher text. So that this is no longer vectorized ones but like work efficiently on like bidle operations one by one and and provides fast bootstrapping and this this now serves as a one branch of FHE and the the other improvement was in like changing the the plain text space. So, so there was a scheme called CKKX where where now they natively uh work over the real number um uh space R um in in still in a vectorzed format. And since real number armatic is so so used a lot in machine learning and since like outsource machine learning is one of the main application of FHE like it has been widely adopted uh since then and uh like uh in the recent like two or three years there was an there was some attempt to like do discrete arithmatic using the approximate scheme CKKS and that is what I'm going to talk about in this talk today. Okay. So let me now start the math. Uh so so I want to keep this very high level and like I want I want to give you intuition on like what is going on with these like different schemes and like uh especially what discrete CKKS is doing. So I would I would you I would I'm going to use an abstraction where like um I just I would just regard lattice arithmatic as just like noisy integer computations. So, and and I'm going to use a kind of non-standard notation of uh like putting least significant beats in in the left and most significant beats on the right and and these bars will denote um integers and I will place like error something like error e there like inside the inside these long bars to indicate where the where the message or errors are located. Um and and yeah and and let me start uh talking about these noisy arithmetics. Um so yeah let let's consider you want you have like two integers x and x prime um and you want to just multiply. So these these long two bars are just integers but like the problem is that they are they are noisy. So what it means is that we want to compute on an integer x but but they are actually x plus e and x prime plus e prime for some small errors e and e prime. Um and and another property is that every multiplication accumulates some additional noise from the least significant bits. Um so so you will be adding more noise after every multiplication. So for instance if you multiply these two integers then then what you would expect is X prime um which is a product of X and X prime but you would get additional noise XE prime plus X prime E plus E prime plus some more multiplication noise. So to to get this you can write uh the the multiplication formula in this way and you can uh like group everything instead of xx prime and you can see there's a huge error coming from here and in particular if since x is as long as the size of the bar uh the noise the the multiplication x prime and x prime e like makes you makes your error bar grows as as long as like the the original uh u message space uh and and therefore the the every time you multiply like the noise grows like by a hugely by huge amount. So and the question of this talk is how do we design an exact arithmetic from this kind of noisy arithmatic. Um so uh please please please feel free to interrupt if you have any questions because because this this this notation will be used throughout the talk. So do do you have any questions on the notation? Uh if not then I I will proceed. Okay. So the first and natural attempt is to completely separate uh message and error uh also can be called as BFV scheme. Um and and and this attempt enables arithmatic over ZP for a small uh smaller modulus P. So this enables modulo P arithmatic and I'm going to explain how this works. So instead of like treating your message to be like entire uh integer for this large uh bar, you you you can like locate your message in the most significant bit of of of the integer so that they are they are well separated with error in the sense that error is small uh in in the LSP and message is large and in the MSP. Um and and if you multiply with these then you you still get these huge errors but like but your message is uh the product message is now located in your MSP and so you still have some separation u between message and error. So if you write down as as a formula then then uh we introduce some kind of a scaling factor delta which which puts you puts your message in the most significant bits and if you multiply these scaled messages I mean scaled noisy messages and um divide by delta and round then rounding operates like a cutting error uh at this point and then you get a a product message uh noisy product message which has your uh product in the most significant bits. Um and like okay sorry okay so if if you look at this formula you can observe that every time you multiply the error would grow by roughly by the size of the message um and therefore the error uh like Eouble prime is is always larger than the initial errors EN any prime and they will like accumulate throughout the computations. Um and and therefore like in order to provide some exactness of this MSB this this this computation is by definition is naturally a bounded computation. What I mean is you can only do a bounded number of addition and multiplication. Um and that is why we need to introduce a process called bootstrapping. So bootstrapping is a homorphic operation which means we we compute on cipher text and and and that is an operation that reduces the noise. So let's say you have a noisy message uh with with huge error and you you convert it to another noisy message with much smaller error. So this is the definition of uh bootstrapping and um then you may wonder how bootstrapping works then then I can I can I can like intuitively describe a high level idea of modern BFB bootstrapping. So you start with uh noisy message with large error and and you you modulus switch um your your noisy message to a smaller modulus. What it what it just means is that you just cut your bar at this point and and then um it will it will not like exactly cut. So you will introduce additional green noise new green noises and in the the least significant bit of the shorter noisy message and then the trick is that you can regard this u new short noisy message as if it's a fresh fresh one. So you can you you just like make it longer again. I mean until until the as long as the original message and pretend that this is like a fresh message without noise. and and and and the and the key part is that then now you you like evaluate a homorphic modular reduction which is essentially homorphically extracting uh this MSP from from um from this noisy uh message and then it would the homorphic operation itself would accumulate some noise but it will be smaller than the initial noise so that eventually it it allows you to success uccessfully bootstrap. Um okay. So and and the next generation um called CKKS takes another approach which is to just live with uh the error. So what it means um is that so this scheme is uh a scheme over real numbers. So an arithmatic is now over reals and um but but we will we will put just put our message together with the error. So what it means is that we we have um real numbers m and m prime and we we increase the these real numbers by some scaling factor delta. So, so we somehow like try to preserve some kind of precision but but still the but but but still these these messages will live with the error like accumulated in the least significant beats. So like you can just think that well we have a we we we have a noisy message um which is contaminated from the bottom and and as exactly as in a BFB multiplication you can you can multiply these two um and and like like cut cut the noise and get get um get get multiplication result And um this so and this enables uh multiplication over real numbers because like if you if you try to multiply these then uh and and and you cut then you have the same scaling factor as the beginning and then yeah this this gives you uh some kind of a fixed point multiplication. And if you think of like usual uh floating point or fixed point arithmatic in the plain text world I mean where where where is not like encrypted world then then you you already have like error in in some kind of error. So like in some sense that is this is acceptable and and yes and this this paradigm is just um leaving with the error and so now we don't have error accumulation problem um so we don't need to like bootstrap in the BFB bootstrapping sense but but now the problem is that every time you multiply you actually cut uh your LSV and and the bar is actually getting shorter and shorter as you proceed. So like at some point you will you will have like no no space um in front of of these messages and then it will it will like like incur some like overflow. So this so it is also bounded computation and therefore we need to uh do some CKS bootstrapping which is an operation that homorphically raises the modulus instead of homorphically um reducing the noise um and and and sim and like this is kind of I would say this is analogous to VFP bootstrapping but in the most significant bit version. So what it means is like uh if you have a cipher text with short bar then you extend the bar by raising your modulus and and like raising actually introduces some new green errors uh like slightly uh higher than the initial message. And there you you you evaluate a homorphic modular reduction function which which removes the green error and and then you get uh the extended bar uh which is essentially the result of CKKS bootstrapping. Okay. So I I described the the two schemes a BFB and CKKS which operates over different error message models. So in BFB the message was put in uh the most significant bits and errors are accumulated from LSB and while in the CKKS you put both message and error in the least significant bits and just live with uh your error and but but the next scheme I want I'm going to talk about is this CKKS where which can be regarded as some kind of hybrid between the two in the sense that you put message somewhere between LSPD and MSD but like but you still have clear separation between message and error um so that you can achieve some kind of exactness. Um here um first of all I want to talk about uh like BFB bootstrapping aspect of discrete CKS. So for simplicity uh let's consider uh like encrypting a bit B instead of uh like a large message M and u as as in the BFP was wrapping we want to somehow reduce the noise of of this um noisy message and and to write write down as a formula uh the the plain text message I'm the noisy The integer can be represented as u like a scaling factor times bit plus some small error and if you write this as a like a real number then it can be written as delta x where um x is a noisy bit so x is near zero or one but like pretty close to zero or one and what we want to achieve is to reduce the noise. What it means is that input uh uh a number that is close to zero or one. You want to output also output a number that is close to zero or one. But the requirement is that the distance from the init the the target bit should be smaller after uh this operation. And and now this this comes to like like like kind of a undergrad level like calculus thing because we we do know like which which real number fun real function like uh have this kind of property. So let let's say you have a function f(x) = to 3x^2 - 2x cub then this function is nice in the sense that it satisfies f0= 0 f_sub_1= 1 and it have vanishing derivatives in around 0 comma 0 and 1 comma 1 and and you can see that this is exactly the property we want. So I mean like if we we wanted that like we we start with the points that is close to 01 and we wanted to make it closer and and the the fact that it's it has vanishing derivatives it roughly um squares the um error like away from uh each point 0.0 0 and 1.1 and achieving the cleaning property as desired and and I would also consider the property of raising the modulus because this is kind of a hybrid scheme. So we also need to tackle the problem of of like the bar getting shorter and shorter. Um and and for this like discrete bootstrapping is now defined as both raising the modulus and cleaning and cleaning could be achieved by uh like evaluating a good-looking real number function and bootstrapping will look almost remains the same but but like it turns out that we could achieve both at the same time easily by by uh like what is called hermite interpolation which is a kind of a cleaning interpolation version of uh of usual lounge interpolation but uh I would not go deep into the details um and one interesting property of this new discrete bootstrapping is that we can evaluate a function on the way for free so let's say we have uh our method space is m then then we can we can compute arbitrary function from m to m um on the of like evaluating a discrete bootstrapping and um this is this is quite analogous to like the the framework of of the TFHE like I mean the bit bit wise uh FH uh because like in there they they everything operates on like like functional or programmable bootstrapping and they combine these to make like whatever circuit is you want and and our discrete uh CKS bootstrapping provides some kind of a like a vectorzed version of TFHE or or DM bootstrapping. Um um and to to like to like note what it really provides in terms of arithmatic, it provides uh arithmatic vectorzed arithmatic over some small message space. For instance, the message space is like like Z2 to the 8 like modulo 256 operations and like you can use these to build whatever applications as you want is and this is kind of a like a like a fundamental pit primitive of these this discrete CKS framework. So like >> can I ask a question of this? >> Oh sure. What's the what's the limiting factor here for the message space uh size? >> So basically what you will be so so so your functional bootstrapping is basically applying interpolation over the message space. So if if your message space got gets larger then then so the the size of the message space corresponds to the degree of the interpolation polomial. So like it cannot be like very large. So so it it grows. Yeah. It it grows almost exponentially. So So you need to like kind of choose a good number that like that is that is sufficiently large but like not so large to be like uh to make it difficult to be interpolated. So >> practice you can really go much larger than the space. I think Z2 to the 8 is like kind of uh near the boundary. So like because because it's already like two degree 256 polinomial it's pretty okay but like but if you go like degree like let's say 10 1 or 2048 and then it it takes too much time uh it soon becomes like too much time for this and and like alternatively we can actually iterate this to get like get uh arithmetic what I mean is like let's say you have like 16 bit um arithmetic Then instead of like interpolating over the entire like 2 to the 16 degree polomial, you could like like uh interpolate I I mean you you could divide it into two chunks like two 8 bit chunks and and and and operate on it and usually that is more efficient than than like interpolating over the the the larger space. Um okay and that is actually what I was going to explain in the next slide. uh like so so using using these I mean by by in by representing like large uh message space as like smaller chunks uh you can actually like enable like any precision arithmatic uh I mean with with like digit style representation and you can do like textbook multiplication or or or or like multivaried like style interpolation and so on to achieve whatever arithmatic you want over over these uh digit represented um uh like data and and and that is why I I called it a al au and it can be used as a kind of a primitive for any unsigned like integer computations um in general um and in particular uh like we compared with the the other branch I mean the bit fat branch uh and and the the well-known library tfrs And if you compare like like 64-bit operations different 64-bit operations on uh like if in compare with them um it's in terms of amortized latency like I mean this approach is like two to three orders of magnitude better but like in terms of latency um it's it's much worse but like there were some even uh recent uh developments that that even reduces the latency uh close or even better than uh bitwise FH. >> What's the intuition for why the um the advertised latency is much better than your case? >> Oh, so so like so TFH is a kind of a completely different branch. I didn't really mention in in the talk and and like these CKKS and VFB and these schemes are vectorized schemes. So you can think of more like a GPU but but like in but but like the the entire latency is slow and and TFH works is not vectorzed scheme. So it it works on individual um cipher text I mean individual like messages. So but but they are pretty fast. So, so there there there there was there has been always a trade-off between like like these nonvectorized FHE and vectorized FHE. I mean the trade-off between latency and amortized latency. But like until until now like there were no good ways to emulate what they can do in bitwise FHE because like in bitwise FHE they they had a very fast like like small integer uh style arithmetic whereas like in in in the corresponding vectorzed world we we didn't have one like we we more we had more like uh interpolations over finite fields. So which which are not not so great. um usually for for D small and jurismatic and like and like this this kind of uh like approach lets you emulate I mean the vectorzed version of what bit bit FHE or TFH could do. So, >> so oversimplified would would it be more or less correct to if I oversimplified and just said that the setup is slower with your approach but once the setup is done things run faster and that's why you you know the latency is slow but you get better advertise time overall. >> So I I I would say intuitively it's like a comparison comparison between CPU and GPU. So for for individual like GPU it each thread is like much perform poorly than than like CPU thread but like it has like many threads. So so the amortized latency is always better. depends on the application, right? If the application allows you to to vectorize the the computation, then CK would be superior because you don't care about the latency much and then the scheme on the left, they are more optimal to really deal with the single uh vertex, right? >> On the right, you need to do this big thing anyway, but luckily you have the opportunity to pack a lot of messages into one. Okay. [clears throat] >> Yeah. And you you can play a little bit more and like for instance you can run run try to run like a residue number system like homorphically inside uh I mean inside FH and and and then and and that essentially provides like arbitrary modulus arithmatic and you could achieve yeah you can achieve like any like z m arithmatic for whatever um integer m you want. So yeah, this is more like an example and also uh like this this makes you this allows you to connect uh CKKS and discrete CKK or which I mean by like CKK operates on uh like floating point or fixed point numbers and discrete CKS operates well on like small size integers and and and we have efficient conversions between the two. Um and and and then this this this pretty fits well with the quantization framework in machine learning where where you you like instead of like operating on like huge floatingoint numbers, you you you like look look up in look up for like short size like four bit or 8 bit integer and yeah it so so this this naturally um yeah fits the framework and gives better efficiency. And like alth although this this kind of framework is like very new like there were already like a bunch of works in the last last two years. Oh yeah I wanted to like just just let you know like those big from the beginning the start like there are a large attempts to like build a better lookup tables. I mean which is essentially better functional bootstrapping and I mentioned like attempts on like like building integer arithmetic system um upon this framework and and and many applications uh were there too. So this this is the end of the talk and thank you so much for listening to my presentation. [applause] >> Are there any questions? >> Let's stop the recording here. Um >> okay. Yeah. And then uh we can have any questions you want.