ZK12: Speedrunning (T)FHE - Ravital Solomon & Rick Weber

Transcript

[Music] hi I'm Rital the founder of sunscreen and in this talk we're going to be speedrunning tfhe T here stands for Taurus not threshold and it's a particular fhe scheme so the whole motivation of this talk and frankly our work for like the last N9 months is to understand how can we beat state-of-the-art performance for tfhe and what would a winning strategy even look like to accomplish this so what is the TF scheme well it's considered one of the state-of-the-art schemes for fhe and by ZK standards it's pretty old it's from 2016 it's natural

to wonder what fhe folks have been doing in the meantime if there are no new schemes and they've been working on a bunch of other side quests so to speak everything from multi- party multi key fhe to hardware acceleration of the technology and semi- efficient combinations of FHA and ZK when most people introduce fully homomorphic encryption they talk about it as an extension of public key cryptography where in addition to being able to generate Keys encrypt and decrypt data you can now perform computation over the encrypted data itself so specifically we talk about adding and multiplying Cipher text together but the reality is a little bit

more complicated than that so for certain kinds of FHA schemes you can also perform comparisons over the encrypted data in a fairly efficient way and to actually support all of this computation over the encrypted data there tends to be a lot more algorithms in the background that actually facilitate this process the key thing you need to know about fhe if you're working with it if you're a cryptographer or if you're an engineer is that you need to manage something called noise I'm not going to tell you what exactly noise is just the consequence of it so as you're performing these computations over the encrypted data this thing called noise keeps growing and if it grows too large if it becomes too big you will no longer

be able to decrypt your data and expect back the right result so we need to make sure we manage noise when working with FHA how did we end up at tfhe well very first scheme was about 15 years ago it was from Craig Gentry and it wasn't particularly practical in real life but it introduced this concept called bootstrapping and if we want to control noise growth we absolutely have to use bootstrapping at some point in time so second generation of fhe comes along in 2011 2012 and it tries to avoid bootstrapping entirely so the idea for second generation schemes is we're going to work with a leveled scheme where at

no point are we going to use bootstrapping and we can only support report computations up to a certain depth after that point we're basically screwed the good thing about these schemes is that they're really really good with arithmetic so if you're looking to add multiply Cipher text together this is the way to go final generation comes along this is where tfhe sits the whole focus of this talk the nice part about this scheme is that it's very very good at performing comparisons over encrypted data so if you want to order things this is a way to go it took a totally different approach to BR strapping than second generation fhe so whereas second generation avoids bootstrapping entirely

with third generation we're going to bootstrap super often so basically after every homomorphic computation so now that we've told you a bit about noise and a bit about bootstrapping we're ready to introduce our strategy to beat state-of-the-art performance and at a high level our strategy is actually really really simple it's just that we're going to be super smart about how and when we bootstrap so what does that specifically mean when it comes to how to bootstrap we are going to go see what types of bootstrapping variants actually exist out there in the literature and what are their trade-offs on the one part we're going to see if we can take some sort of Middle Ground between second and third generation FHA so we're not going to

avoid bootstrapping entirely but we're not going to bootstrap super super often if you don't actually work in FH your lattice based cryptography you might think this is actually easy to implement and try out our strategy so maybe it looks something like the following we go look in the literature we see what types of bootstrapping exist we then write our nice little fhe program and we replace we'll say bootstrapping method a with bootstrapping method B maybe we'll have to make some fairly minor parameter adjustments but honestly how bad could that be and finally we just run our program and we see how we do that is not what the strategy looks like at all and

you would be very very wrong if you thought it was that easy so there are a number of problems with trying to take that approach the first problem is that you can't simply write a program take one bootstrapping method and replace it with another they behave totally differently problem number two that noise issue I was talking about well it turns out that noise grows differently depending on which boot strapping method you use three it's not super obvious when you look at the academic literature what the trade-offs for performance are going to be in some non-trivial application and four those parameters well there's not a few of them there's

actually over 10 of them they're all deeply interconnected and it turns out they handle everything from performance security and correctness so when you're working with the tfhe scheme there's a chance of a decre encryption error so you might get back the wrong answer what kind of error rate are you okay having so let's look at what bootstrapping options even exist out there option number one is called gate bootstrapping you can think of it as the original form of bootstrapping in the tfhe paper you're going to work with binary messages and your goal is to just reduce noise programmable bootstrapping Builds on top of gate bootstrapping you can think of it as a general generalization

here we're going to work with messages of greater than a bit and we're also going to apply a function at bootstrapping time the idea for programmable bootstrapping has been around for a while it's as early as 2018 finally we have circuit bootstrapping and what distinguishes circuit bootstrapping from gate and programmable bootstrapping is that it produces a totally different Cipher text output type and what's special about this output is that it can be fed directly into a multiplexer if you need a brief refresher on what a multiplexer is just think of it as a way of implementing an if condition but here everything's encrypted the idea for circuit bootstrapping is also quite old

it's been around since 2017 potentially even earlier we're not very interested in gate bootstrapping it's certainly not going to allow us to beat state of the-art so we're going to be interested primarily in programmable and circuit bootstrapping so naturally at this point we should go see what research exists out there what are other people saying a lot of interest has gone into programmable bootstrapping both on the industry side as well as in Academia and circuit bootstrapping has largely been ignored by the community at large we have a few theories for why this might be but one potential theory is that if you take a fairly Standard Security level so say 128 bits of security

circuit bootstrapping doesn't look that promising the time's pretty abysmal and it's over two and a half times slower but looks can be deceiving so should we actually call it a day at this point what actually happens when we try to write a non-trivial program using these two approaches so we're going to focus on a comparison program the reason for that is because the whole reason to use the tfhe scheme is to get cheap comparisons over encrypted data I've chosen 16 bits because it's non-trivial and it fits nicely on a slide and here we're seeing how to do that program using programmable bootstrapping you'll notice

on the left hand side with that nice diagram these red nodes which is where you perform a programmable bootstrap operation the important thing to note is that there's dependencies between these red nodes so there are programmable bootstrap operations dependent on other programmable bootstrap operations what happens if you try to implement the exact same program using circuit bootstrapping you get a very different looking graph and while this graph looks incredibly ugly the important thing to note are the red nodes where we're using circuit bootstrapping and you'll notice that there are no dependencies between those red nodes no circuit bootstrapping operation is dependent on any other

circuit bootstrapping operation why does that matter well it means in theory this program can be parallelized a lot better than the previous one with programmable bootstrapping can we actually take advantage of this parallelism what do we need to do to accomplish that Rick will tell you all about that thank you RTO so circuit boot strapping has these nice uh computer science theoretical properties but unfortunately at 128bit security the performance of the bootstrap operation itself kind of hampers the overall um computational scheme but maybe there's some things we can do to improve the performance of

circuit bootstrapping such as we can reduce the security of the underlying lwe problems or we can perhaps accept a higher level of error rate um and both of these things are going to manifest themselves at twe uh tweaking the parameters of the underlying scheme so to get started let's look at how does programmable bootstrapping work um you have you start with an lwe Cipher text that encrypts one or more bits of data and then you apply a negga cyclic function f while you're also resetting the noise in the cipher text and then you do some other things I'm not really going to talk about but you'll note that there's these L and beta parameters which I will talk about in a little bit

but first let's look at and contrast with circuit bootstrapping whereby you start with an lwb Cipher text that encrypts a single bit a binary message and then you do a bunch of steps and get this ggsw Cipher text in the middle and it's important to note here that we have just produced this ggsw Cipher text as a result of circuit bootstrapping we haven't done any computation yet we do that by Computing a lookup table built out of a mck tree Multiplex operations are hundreds of times cheaper than a bootstrap operation and then finally we do some other boring things I'm not going talk about but you'll note here that there's more of these L and beta parameters so what are they well these L

and beta parameters Define base decompositions a base decomposition is a technique used during um homomorphic multiplication and what it does is it limits the noise growth um when you apply this operation during the bootstrap process so to give you an idea of what a Bas decomposition is you take a value like 12 five and you break it into digits so 1 2 and five and they're multiplied by their constituent uh Gadget coefficients and then when you sum them all up you get back the original value in practice when FHA and TF in particular we can we often use approximate decompositions so if we took the digits

one and two and multipli by them by 110 respectively you would get back to the value 120 which is approxim o imately 125 so what are all the parameters now that we have to muck with with uh circuit bootstrapping under tfhe well circuit bootstrapping starts uh in practice with a programmable bootstrap operation and this exposes these p uh programmable bootstrap uh base decomposition parameters um we then do a private functional key switch and this exposes these pfks um base decomposition parameters and in doing this after doing these operations you have produced a ggs

w Cipher text which is itself radic decomposed and that produces these uh CBS radic parameters finally we have key switching which is another thing I'm not really going to talk about but it gets you back to uh the original key under which you started so you can continue the computation or send the data back to the user so we have all these different parameters um let's take kind of a brief look at how do they impact performance security and correctness um unfortunately it's a very complex multi-dimensional search problem um we iterated through tens of thousands of simulations whereby we would run a synthetic computation and we would measure the

performance the noise and um we would fix the security level to some desired amount um and to give you a flavor of how all this stuff is intertwined um if you take the CBS level and the pfks level and uh take the product of these two this is uh the relationship for the overall performance of your scheme so if the circuit bootstrapping level is one and the pfks level is one versus if they're both two in the latter case you'll be four times slower and looking at the CBS Bas and level values uh specifically if you have a lower CBS level in your decomposition

you'll get better performance but often the expensive more noise conversely if you use a um higher number of digits in your decomposition I.E a higher level but with a lower base you get less noise but worse performance and then there's this um kind of interesting relationship with the log of the base times the level this represents how approximate your decomposition is so if you had a 64-bit value and the product of this is 34 then you have captured roughly half the message in your approximate decomposition um this product is very non-intuitive as to what the sweet spot is and it varies from decomposition

parameter to decomposition parameter and here we have two graphs kind of highlighting as we change the CBS radic and base level what happens to the performance in some kind of application so we see that all the values over here on the right are about twice as large as those on the left because we have held all the other radex parameters fixed and we've doubled the number of levels all right so we've run tens of thousands of these experiments gone through and picked out uh parameters that work the best for us and what is all this bias so we're going to compare tfhs uh and its comparison operation the nice little apple tree that Rob tuls

showed earlier running at 128 bit security compared to sunscreen running with circuit bootstrapping at 80 bit security um and we also have slightly different Notions of correctness so with programmable bootstrapping uh under tfh RS they guarantee an error rate of 2 Theus 64 um conversely with sunscreen running at 80 bit security uh we have an error rate rates of 2 Theus 63 after we have done a circuit bootstrap operation and run a depth 512 mstre which is pretty deep actually and what we see is that comparing and operations the whole um thing that motivated all this so again

we're running the apple tree on the left and we're running The Hungry Caterpillar on the right uh two very different looking things but uh at the end of the day they're Computing the same function and we are circuit bootstrapping is 3.5x faster under this setting addition is even faster at 4.5x and multiplication requires multiple rounds of circuit bootstrapping uh so it doesn't have nearly as much gain at only 1.5x but now let's look at let's put this into some larger application that's more interesting than just comparing two numbers so we're building a first price seal bid auction and if you're a computer science person you can think of this is um you have an array of integers find the max the index of the maximum

value um again we're comparing tfrs at 128bit security with programmable bootstrapping to sunscreen with circuit boot strapping at 80 bit security and we have the same kind of error rates as we had before and what we find is that at 64 bits um with 16bit Precision sunscreen is 5.7x faster um at 128 bits it drops to 4.6 X 256 bids it's 4X and 512 bids it's 3.5x and this results this kind of decreasing uh speed up results from gustafson's law as more parallelism becomes available the larger you make the auction and the programmable

bootstrapping algorithm has more parilis to exploit and starts to catch up so some takeaways from all this um programmable boot trapping has been kind of one of the most common um commonly researched techniques in tfhe but it's by no means the only way to perform comput ation with it um not all apps require extremely low error rates so maybe you can drop your error rates by few of magnitude so from like 2- 64 to the 2 Theus 50 or something like that and not all apps require 128 bit of security in particular for short-lived little things like an auction where you run the auction you decry you threshold decrypt the answer and um now it doesn't really

matter if everyone's bid's revealed cuz the auction is over so in this kind of setting maybe you can get by with less security such as 80 bit um under these kinds of conditions uh circuit bootstrapping can outperform uh PBS by quite a bit um unfortunately using CVS is extremely hard for kind of asinine technical reasons um you have three different type of Sur types of Cipher Texs you have to worry about and convert between you have to worry about how much noise you have at what stage of your computation and so on so forth forth sunscreen's been building tools to make managing all these problems easier and building applications that you can use CBS uh significantly easier to do um and we expect that this work will become

more relevant and more important even in the future as accelerators come online and expose even more parallelism available for the system to exploit um and with that I'll take some room for questions I guess [Applause] and thing again okay yeah please wait one second yeah you were a bit faster than I anticipated so yeah please go ahead so uh what tools did you build uh for making this easier for um Engineers to use it yeah so when you're working with

circuit bootstrapping it's very unlikely you can actually write the low-level operations yourself so you really require some compiler that abstracts away most of the FHA specific parts for you so we've been working on a compiler for our version of the tfhe scheme what what what's it called sorry what's what called how it's called that this compiler's it named does have a name we haven't we haven't named it yet I'm sorry to say yes uh you compared your system with 80 bits of security it's a tfhe with RS

with 128 is there a reason you couldn't parameterize tfhe with 80 bits as well so that's a funny question and we knew we were going to be asked this by somebody because it's a totally fair question to ask I would ask it as well so we did in spend some time trying to get tfhe with programmable bootstrap to have a suitable error rate for 80 bits of security but frankly the simulations and the modeling took too long so I'm going to go off of what I've seen from flash Bots work where they were playing around with tfhs they dropped the security to 80 bits they expect about 30 to 50% Improvement which would still not account for what we see there so

certainly tfhe RS with programmable bootstrap would improve but it's not going to improve by 5X great thank you anyone else we have a bit of time don't be shy hand okay so we're just going to take a few minutes break to wait for the other stages but yeah stay around if you want to follow up with the next talk of this FH segments with Michelle just after but thank you very much Rit and Rick