Building a fully homomorphic encryption compiler for the real world / Rick Weber

Transcript

foreign [Music] thank you hello everyone my name is Rick Weber and I'm going to be talking today about fully homomorphic encryption and what all needs to happen in order for this to become a reality in web 3. so um just a quick survey has anyone here heard of fully homomorphic encryption okay a few people then you may have heard some of these uh rumors you may have heard that it's kind of slow you've heard that it's unusable or that's kind of useless two of these in fact today are actually kind of true in web3 and

one of them a little less so and hopefully at the end of the talk you'll know which is which so to start off what is fully homomorphic encryption also known as fhe so you take a traditional public key encrypted scheme so you generate a public and private key then you can use the public key to encrypt data and you can also take a ciphertext and use a secret key to decrypt the data but there's these additional operations you can do so you can add ciphertext together which will produce a new ciphertext that contains the sum of the messages in the operands and similarly you can do the same with multiplication producing the product

there's an additional operation called bootstrapping and all fhe schemes today use a branch of Photography known as lattice cryptography this means that they are quantum safe but they unfortunately have the side effect called noise and what noise is is as you perform these add and multiply operations you get more and more noise in the resulting ciphertext if that noise exceeds some threshold then if you attempt to decrypt this ciphertext you get garbage and so what bootstrapping does is it resets the amount of noise in a ciphertext and using this technique you can compute for effectively forever

and because you can do addition and multiplication and you can do effectively unlimited number of them you can compute polynomials thus you can compute any function you want so to give a kind of brief history of fully homorphic encryption it came into existence conceptually about a year after RSA was embedded it took about 30 years from there to come up with the first implementable scheme this was done by Craig Gentry where he introduced the idea of bootstrapping this scheme was extremely slow and in practice it was more academically interesting than practically interesting a few years later bgv and vfv were born and these feature very fast arithmetic

but bootstrapping under these schemes is fairly slow and so in principle in practice people don't actually use bootstrapping under these schemes a few years later we got ckks which uses approximate arithmetic and then we got tfhe which uses binary arithmetic and tfhe has the added benefits that bootstrapping is very fast which means that you can effectively do it every operation currently if you were to deploy fhe you could expect to see performance slowdowns of between a couple hundred thousand to a couple million and you would further see memory usage increase by about that size too and

um yeah so why are we here talking about fhe um fhe is a new tool in the toolbox that you can use to create new kinds of applications you can have private auctions you can have dark pools and you can compute on private shared state if you also use multi-party computation fhe by itself is not extraordinarily interesting in web 3 because people can just send random messages that aren't ciphertext you wouldn't be able to tell the difference and it would break everything however when combined with zero knowledge proofs you can create robust systems so how do we combine fhe and zero

knowledge proofs in web 3 there's two kinds of different models that you theoretically could use so you can use honest majority whereby every validator is running the fhe computation and validating proofs coming from users to show that the ciphertext they're getting are well formed and that the message is contained within them obey the properties of the system but you could also turn this into a roll-up where a validator can do everything that we just talked about and then additionally produce another zero knowledge proof showing that the proofs were validated correctly and the fhe computation happened correctly this roll up today is kind of academically interesting but in practice is too cost

prohibitive to actually perform so everything we're going to be talking about today we're going to be talking about implementing things with honest majority so you want to use fhe and web3 what do you have to do well you have to pick an fhe scheme we have three schemes to kind of choose from today we have BFE ckks and tfhe and so we have three schemes but we actually only have two schemes ckks uses approximate arithmetic which if you've ever seen the movie Office Space you realize maybe a bad idea for financial transactions as you get rounding errors BFE and tfhe then BFE you can perform fast computation so addition and

multiplications are very fast you get lots of precision way more than is needed for performing operations in a blockchain setting the keys in ciphertext are small and yes those are scare quotes because everything is relative unfortunately performing some computations with BFE is fairly difficult for example if you want to compute the maximum of two values this is very hard to do if not not practical with BFE furthermore bootstrapping is extremely expensive with BFE and so in practice you don't do it which means that the number of computations you can perform is finite tfhe on the other hand

you can do a lot more operations because of the binary nature of it so you can if you want to compute the max of two values this is possible to do in a reasonable amount of time you can bootstrap on every operation which means that noise in practice stays at a fixed level unfortunately There's issues with Precision so if you want to use 32-bit integers or something of approximately that size your arithmetic is going to be kind of slow and performance will be affected so you also have fairly large keys and you can have large ciphertexts if you use tfhe

so now that we've chosen a scheme depending what we're trying to do we need to set up the scheme so with BFE plain texts are polynomials where every coefficient is modulo p p here means plain text coefficient it does not mean Prime as it usually does and ciphertexts are polynomials modulo Q for the scheme to be correct and functional we have to have that Q is significantly larger than p so working with polynomials is kind of annoying so we want to encode data onto the polynomial for example an integer one way you can do this is you can

ignore and zero all of the terms in the polynomial except for the constant term and then when you add and multiply these you're multiplying integer values and this will behave correctly but this requires a fairly large polynomial modulus or plain text modulus in order to not have overflow problems alternatively you can decompose your integer into binary and transcribe this onto the coefficients of the polynomial so once we've chosen how we want to encode our data we need to choose the scheme parameters so we've already kind of talked about the plain text modulus and uh coefficient

modulus Q but there are other scheme parameters as well such as a polynomial degree and if you choose these parameters poorly you can either have way lower performance than needed or if you make the parameters too small then you don't have enough computation to successfully decrypt the result um so choosing a larger value of the polynomial degree means you can do more computation because you have a larger noise but it but it also increases the size of ciphertext and reduces the computation throughput finally BFE has this re-linearization operation that after multiply ciphertext grow in size re-linearization knocks

them back down so the question is when do you put these into your computation so is fhe faster slow well it depends what you're trying to do if you're trying to do something reasonable and you choose the appropriate scheme uh fhe can actually be very fast furthermore if you choose you need to choose the parameters correctly suitable for your computation and then you have to create a circuit that efficiently runs that computation so if we're looking at 32-bit precision and we want to compare BFE to tfhe we see that key generation takes a can take a quite a while with tfhe but this is often a one-time cost so maybe it's not

a problem but the other areas where they differ is that you can see multiplication is significantly faster with bfv than with tfhe and to kind of give some even more context this uh bfv time was not multi-threaded the tfhe1 was um unfortunately doing computation comparisons with bfv as we've mentioned before is extremely difficult um but it is possible with tfhe now let's look at what happens if we change the scheme parameters with vfv so we see if we change the last Dimension from 2048 all the way up to 8192

then we see that the runtimes of various operations increases by maybe a factor of 16. so choosing the right parameters this kind of highlights why it's important to do so everything gets slower if you make things bigger conversely with tfhe if you change the amount of precision you can see that if we one point x 1.5 x the amount of precision going from 32 to 48 bit most things are about 1.5 x slower except for multiplication which is not it grows uh by more than a factor of two so what's challenging for fhe you have to pick the right encoding how

you want to map your data onto the underlying plain text values you have to choose the right scheme parameters you have to insert ciphertext maintenance operations as appropriate for example re-linearization with BFE you have to choose the right amount of precision you want to use if you want to use tfhe and then finally you have to make an efficient circuit that performs the calculation you want to do so taking high level descriptions of programs and turning them into some kind of executable format is exactly what a compiler does but unfortunately today a lot of fhe compilers are not so great at this so we're going to look at an application

from this sok paper and this is a chi-squared test and if you were to implement this manually in Microsoft seal with BFE and you timed the key generation encryption computation and decryption you can do this in about 50 milliseconds on a commodity laptop however a lot of fhe compilers you just can describe this exact program and you get overheads anywhere from a few hundred fold to tens of thousands of fold two notable exceptions here are Ava which is a Microsoft compiler that built uses ckks and again ckks is not so useful in web3 um and then the sunscreen compiler which

can do this with a 1.3 X overhead so for compiler to be useful in web3 it has to deliver performance um and then kind of the final step you have to do if you want to use fhe and web3 you have to prove that your ciphertext obey the properties of the system and are well formed so let's take an exist example we Alice wants to send some money to Bob so the way you can do this is you have a ledger balance that's encrypted on chain and Alice can produce a value that she wants she encrypts under both her key and Bob's key and she has to show that both of these ciphertexts are well formed so they're

not just random garbage she has to show that the amounts contained in the message that will be subtracted from her balance is the same as the message that will be added to Bob's balance even though they're encrypted under different keys she also has to show that the amount she's transacting is greater than zero shows she's not stealing money from Bob and she also has to show that it's less than her balance so she's not printing money so fhe on its own is actually not useful um in web3 because everyone can just print money and do all kinds of things that violate the system so you have to have zero knowledge proofs to go along with it and unfortunately zero knowledge

part proofs are the expensive part of all this computation so the first thing we have to show is that ciphertexts are well formed and there's a number of ways in which you can do this we first attempted to use r1cs and then try to find a proof system supporting r1cs that met kind of the approve or verify times in proof size needs but we were unable to succeed in doing so so we moved to something called the short discrete log proof and this is not a general proof purpose proof system it is specifically for showing lattice relations and so Alice who knows s and the

verifier knows a and t s contains your message and the noise used during the encryption process T contains the ciphertext and a is just setting up the last structure and it's public so Alice can create a commitment to S and then prove that s in zero knowledge that a s equals T and if she does so and also shows that the coefficients in s are sufficiently short or small then she will have proven that this is a valid encryption under a specific key so short discrete log proof has some problems uh and it's when you implement it the prover times are okay compared to

other things out there the verifier times are not and the proof sizes are actually pretty good they're under two kilobytes so what we're working on currently is can we accelerate the operations used during verification so we have scalar inversion scalar multiplication and guess what multi-scalar multiplication everyone's trying to speed this up we're trying to do it on curve two five five one nine though so now that we've shown that a ciphertext is well formed we have to show that the messages contained in the ciphertext obey the properties of the system so like you're not subtracting money from

someone else um so we um to do this we use bulletproofs with r1cs and uh even though we're using bulletproofs which has linear verification time as the number of constraints increases the number of constraints and multiplies you need to create these kind of circuits is not very large you don't need very many of them so we have pretty reasonable prover times reasonable verifier times and our proof sizes are under two kilobytes but we have a problem so the prover has created a proof to short discrete log proof and a proof to the bulletproofs kind of in a vacuum how do we how does the verifier know

that the inputs you gave to both of these proofs were the same well it turns out both schemes use Patterson commitments at their core and so what you can do is break these Patterson commitments into shared and non-shared parts and if you uh the shared part contains the commitment to the inputs to the R1 CS circuit and is also part of the short discrete log proof coefficients in s um so because you're sharing the same commitments you the verifier knows that these are the same inputs and so using a number of other tricks like using the same curve uh promoting some generators and reusing uh the blinding Factor the

verifier can be convinced that the inputs going into both proofs are the same so when we initially set out we started trying to prove all of this with r1cs because it would provide a nice interface so we built a compiler because expressing this directly with the bulletproof Library would be kind of tedious so we built a compiler this is currently ongoing work and we're kind of refining it but the kind of general idea is you write a rust function uh you put a little macro on it and pass it to the compiler and it will build a circuit for you because everything is in Rust it's in a DSL you can share your circuits with others using crates as you would

anything else in Rust you also get all the syntax highlighting and all the other nice things about the rust ecosystem today we support types gadgets and public and private inputs and for r1cs alone this API is very straightforward you compile a circuit you then can feed some inputs and generate a proof for it that should that satisfy that circuit and then you can give that proof to somebody and they can verify that it's correct however what happens when we bring short discrete log proofs into the picture um how does one specify that a matrix to set up the proof of ciphertext

well-formness and how do you specify what you're going to share between the two proofs this is currently an open question and we're still iterating on this so you wanna if you want to build a compiler for web3 it has to do a number of things ask to support BFE and TF or tfhe because these are the two schemes that are useful in web3 it has to build fast circuits and then you need a runtime that can efficiently run the circuits so using multi-threading um you need uh data types so users aren't playing directly with polynomials and you need kind of efficient mechanisms for under tfhe so that people can play with integers

um you need to automatically insert ciphertext maintenance operations such as re-linearization because it's a not you don't want to have to explain to a developer what relinearization is and finally a lot of compilers today view fhe compilation as I'm going to compile this one circuit I'm going to run some inputs through it get a result and then decrypt that and that's the end of the story but that's not really the scenario in web 3. in web 3 you have a balance that's on chain I send some money to you your balance increments you send some money to someone else now it decrements and so the ciphertext is going through multiple circuits we call this program chaining and this is a mechanism that

will help inform what parameters you should use during compilation then finally fhe is useless without zero knowledge proofs so you kind of need a runtime that can marry the integration between zero knowledge proofs and fhe so today fhe is not actually usable in web3 we need better tooling and you in particular we need to marry fhe and zero knowledge proofs together so now we've kind of talked about a number of problems with bringing fhe to web3 we can hopefully start bringing some solutions to the table

so this concludes the talk you can follow us on sunscreen tech on Twitter or you can visit sunscreen.tech and that's our website from where you can access our Discord our GitHub repository and our blog so at this point I can take any questions thank you foreign