zkSummit -Fully Homomorphic Encryption: The Road to Secure Computation-John 'Tux' Pacific (Nucypher)

Transcript

[Applause] hey glad everybody can come to this after eating lunch I'm glad you guys will fall asleep during my dry technical talk so hopefully you're caffeinated enough to keep up we got a lot of details to cover so I'm going to kind of slide through a little bit what we're doing pretty overview so I'm going to be discussing a bit what exactly is secure computation what technologies can be used for secure computation things like MPC T's trust execution environments and fhe as well as the shortcomings of each of these approaches and the solutions for the fhe based approach and what new cipher has

actually accomplished recently what we are working on so we'll be very quickly and briefly discussing just the MPC and T's stuff so I can spend more time on fhe so that way if you have questions we can actually get through those so let's dive right in what is secure computation typically there is a requirement for privacy in those cases there's parties mate usually somebody needs to perform a like some function f on some inputs in this case x and y and in this case there's usually a requirement for that privacy where the data X or the data Y may not want to be revealed when you're doing some sort of computation or the output of that and

the computing party may not want to reveal that in this cases is a two-party secure computation scenario that I show on this graphic but it's not specific to this it can be a single party or it can be multiple parties so the requirements for zero knowledge and secure computation are not required but they there may be they may be present and typically in a secure computing environment there is a lack of trust in the computational setting one that means like it's a network level adversary a computational adversary as in the person doing the computation or if it's dead on or maybe you don't trust the hardware in cases like you know you don't trust the hardware that the computation is actually being performed on in either way there's a

there is an adversary that exists in arson in our situation that threatens the confidentiality and the integrity of that data solutions can exist in both in hardware and software will be discussing which of those and I only have one which is you know like something like Intel SGX or trusted execution environments that are built in hardware but and we'll also be saying how those software security is achieved and as well as for security computation threat the threat models for specific secure computing protocols vary greatly and they change based on the solutions that you use what may be considered secure in one setting

may not be in another and it depends very heavily on what your use case is so you know in some use cases it's okay to leak some information in some use cases it's not okay to leak any information right so to give a brief overview talking about multi-party computation it can be considered a software based security protocol the security reduces to a cryptographic primitive use in many cases people use Shamir secret sharing and we can actually reduce some of the security to the mathematical properties involved and in this case what happens is we have multiple parties that will perform a computation and the computing parties gain no knowledge of the inputs

to a specific circuit right so the input data in the beginning is split and then shared across to all these computing parties and at the end it's then reconstructed at the end by somebody and at this point in time right here this is the only point in time when any data is actually leaked so in that case we're not leaking any data during the circuit computation but whoever reconstructs the output of that circuit will actually learn some data and a trusted execution environment situation there exist hardware it's a hardware based security protocol what essentially means that the security

reduces to the safe implementation of an enclave or a specific dedicated part of a processor literally exists is just a separate secure in quotes secure partition in silicon most implementations of T's our vendor-specific give some examples here with Jerr like something like Intel SGX AMD PSP and arm trust zone it requires that client API to communicate with the conclave so if you can see in our diagram here we have a client API which will communicate with the processor itself and allow the application to be executed inside this Enclave inside this

secure part of the processor there's problems with this and we go over those as well but essentially we're going to have an operating system that runs directly on the processor itself for that execution environment and then it will perform whatever API call you tell it to perform in this case they can be function specific so it doesn't have to be some generic it can get execute anything but it you know there's things like hardware security modules which are also forms of trusted execution environments that may do things such as key generation and signing or encryption dedicated to a spot these are in wide use today but some other things like SDX may not be and more wide use then say

you know a TPM or HSM like I said so now we can get into the meat of what I'm going to be discussing here fully homomorphic encryption so it is a software you could say software based security protocol we can reduce the security to hard lattice based cryptographic problems the most practical implementations reduced to learning with errors which is actually a quantum resistant problem so in a if there exists a really strong quantum computer there this is incapable of being broken by that quantum computer fhe solutions exist for both single and

multiple parties which means like we can have a single person when we have this in our diagram here we can perform a function like a circuit evaluation here we can have a single party perform that function or we can have multiple parties perform that function and in which case that would be something called multi key fhe so in this case and fully homomorphic encryption the function is computed directly on our ciphertext it's not computed on the plaintext so we can actually encrypt some data and if we look at our diagram here we can take some plaintext m pass it through an encrypting function and get the

encryption of that so we have a ciphertext here we can evaluate any arbitrary function f on this and the output is the function computed on the plaintext itself it would be the exact same output how do you perform the function on the plaintext there so it's in short the it's the equivalent of performing the computation on the plaintext just encrypted what we can refer to this as is and frequently when we talk about how a morphic encryption we say things like the plaintext domain or the Homma morphic domain what that means is when we say we compute something in the holomorphic domain it means we compute some function some circuit or function while the data is

encrypted so the data that we're computing it on is encrypted so that's a how that works there's two keys that are used typically ins and depends on the scheme that use but and the schemes that we have worked with we have two keys and we have an encryption key which you know you're familiar with symmetric encryption or public key cryptography we can encrypt some data and then decrypt some data and our computation key enables the computation on that encrypted data so to actually perform this evaluation function here holomorphic lee it requires that you know the computation key here okay so briefly going over some pros and cons

of multi-party computation circuit designs with MPC are relatively straightforward they can be constructed with boolean logic gates debugging is also straightforward as well and it's very clear you can just perform a reconstruction at any moment in time whenever here in the middle of your circuit say you're designing your circuit and you don't know why you have some value or you can just reconstruct which you have at that moment in time and you know see what it is and do it I notice I'm not saying it's easy but it is straightforward you can just pretty much say give me this value and reconstruct it and do whatever and you can get that information the proofs reduced to relatively simple secret

sharing scheme the proofs for those are I say relatively simple mathematically they make they make more sense than say something very complex you know but it's some cons of this many constructions require additional zero knowledge proof for security so for example threshold ECDSA which has recently amassed some really cool following and I do think it is very cool but it is kind of difficult because you actually have to include some you know relatively simple zero knowledge proof to ensure that the protocol is secure itself so the protocol note does not just include boolean logic gates it also requires zero knowledge proof sin there branching is also either

impossible or some does or make it makes it really complex to perform so when you perform some NPC operation it's going to require a ton of complexity just to be able to perform some branch if you can perform that branch at all and the security-wise operations are still performed on plaintext data although split you know it depends depending on what your threat model is if there's a collusion adversary this may not be preferable to you so if that's the case this may be sort of a not-so-great thing to use now the biggest problems with NBC come with scalability complexity grows literally

linearly with the circuit at best that also included you also have didn't have to include knowledge proofs which can add quite a lot of interactivity between the parties involved and network overhead is very very large depending on some schemes may require exponential communication so if you have three parties that would require like three to the three community communications back and forth there's a huge liveness requirement all an offline node can block the entire protocol from continuing so you'll have to wait for that one party to come back online to perform something which is great and any network latency can have absolutely horrible effects on these protocols it will pretty much cause you

know if you have to wait ten thousand milliseconds to communicate with one party well since its exponential you have to talk to them many times that's you know a few thousand milliseconds that you have to continuously wait to finish the protocol so now moving on to trusted execution environments circuit design is also relatively straightforward it's not necessarily like a circuit like you're used to hearing with ZK snarks but it requires its uses a very similar API to what you'd normally just be developing with any other library like open SSL it's easier for your regular developer to look at and reason about build on scalability computation only requires

the liveness of the computing party really so you can encrypt some data send it to the computer that you want to compute on and it can perform inside and it can perform some computation inside this environment there is also some network latency that airboat will dry it will dump into that soon debugging is quite complex on SGX or really any Enclave unless they build a specific interface for this which arguably might make it more insecure than it already is there is no way to really just peek into an enclave and see what's going on you have to provide a ton of print statements and just really see what's going to happen in the Enclave and then

pull it out and and see what's going on there there's no way for you to look inside the Enclave and see what's happening in comparison something like a software-based protocol where we can you know just reconstruct it like I said with MPC and just see where we are in the current state that's just not possible with SGX so you have to print a lot of data provide a lot of debug statements and just try to figure out where a problem is it would probably be easier to construct it outside of SDX and then move it on the inside but sometimes that's not possible security the reductions if you can call them that are basically the difficulty to explain hardware which as we've seen

in the case of Spectre meltdown especially foreshadow these just aren't that secure as much as everybody wants them to be secure we wish they could be secure unfortunately they just aren't that secure these of the attack surface for modern processors is absolutely massive and if you talk to researchers in this space well we are confident that eventually someday we might find something and build something that can withstand a lot of attacks and scrutiny there will inevitably be a break in it and that's just my opinion as well but also I think the opinions of many researchers working in this space for example for shadow which essentially

allowed the researchers to attest to any computation for the keys that they leaked from SDX that that was a massive break another problem is that it doesn't really work well with tress 'less technologies you obviously have to require trust in the vendor that Intel not only is manufacturing it correctly that they're not hiding backdoors in this as well and given what we know about the Intel management engine this also seems like a kind of bad assumption we can't trust that vendors are going to do the correct thing all the time there is no working open-source implementations as of yet Oh Intel has worked a little bit to open-source some of their technology but it's still none of it is really open

source in the true meaning of the word and any hardware updates still require actual Hardware replacement I can't just update my CPU easily nor can you get your stagers or miners or whoever to update their CPUs easily it's more easy on say you can still deprecated some old process but that means you have to get everybody to spend you know upwards of maybe a thousand dollars to a few more thousand dollars just to upgrade their CPU to fix a security vulnerability not to mention there is no way of knowing if anybody actually exploit in their machine that would require some weird Oracle that I also don't think it's possible so now we're get to jump into fhe circuit design is

also very very easy to do in this case and things can be constructed with boolean logic gates the talks before Isaac and Harry gave great introductions to circuit design there and this if you're starting to reason about how to build logic gates and circuits and snarks you can probably easily figure out how to do this as well and fhe as isaac put it the Starks don't necessarily have bit stuff so you have to use actual mathematical operations to perform this as well but fhe actually provides a nice interface and to using bit stuff so if you like bit stuff then

you'd like fhe but there also exist schemes that don't also necessarily require binary logic gates you can also use integer operations and we'll be talking about approximate arithmetic here in a second which there are schemes for that as well security the operation you performed directly on the ciphertext and it requires a computation key to perform the operations itself so this can actually add a lot of great value to a protocol where you can grant access to who should actually be able to compute it's not just anybody it's who you designate access to but this also has downsides we'll talk about that here in a moment for scalability like I said it can be performed with a single party or

multiple parties with multi key fhe and it only requires the wideness of the computing parties right so you can send some data to that person and they can compute it and send it back but there we the Bo beyond just sending the data there is no isn't necessarily any erotic interaction required between the two to perform something however branching is also impossible or it requires really complex protocols at the current moment so I'll show the diagram here in a moment about that so I'll leave that little discussion here for a little bit later a big problem with fhe at the moment is that it since holomorphic encryption is inherently

malleable the best security achievable is CPA chosen plaintext attack security typically what you'd want is CCA security for anything in the real world but the highest we can achieve is CPA security I'll get a little bit more into that a bit later but bootstrapping what bootstrapping is just to give a very brief overview on it it gets really technical really fast but to actually perform this computation like I was saying it requires the computation key that computation key is a what is an encoding of the actual encryption key so when you perform a fully homomorphic encryption operation what happens is you use a bootstrapping key that would be

called your also that's also called the computation key but essentially as you perform operations on ciphertext what you call noise like you have to imagine like if we're speaking about radios or radio signal as you go into a tunnel you may lose signal and it becomes more noisy and you hear more white noise very similar things happen to hum amorphic ciphertext as you perform computations noise grows on the ciphertext and the more operations you perform the less you're able to do to the ciphertext eventually hits a ceiling or a threshold where no more operations can be performed and the decryption is not possible anymore what bootstrapping allows you to do this was created by Craig Gentry and his seminal thesis in 2009 which gave us the

first practical or not practical but theoretical fhe implementation essentially it encodes the private key of this fhe scheme and then allows you to homomorphic perform a decryption and this gets really complicated in why I'm not diving into it a lot but it performs a morphic decryption while the data is still encrypted and then it Riaan crypts it so that way it reduces all the the noise and refreshes the ciphertext and gives us a nice new ciphertext that we can perform any operations on that's why we can perform any arbitrary function on that so the following when you encrypt or when you encode that private key like you can literally think of a computation

key as a hammam Orphic li encrypted private key of that encryption key right so that's called circular security Matt Green has a fantastic blog post about this I have a link in the presentation and an upcoming slide but if you want to learn more about what circular security is you can go on Matt Greene's blog and he has just a fantastic write-up about it another problem is cipher texts are extremely large sixteen thousand times expansion factor in tfhe that's what we implemented in new ciphers into fhe computation keys can also be large around 100 megabytes in C fhe as well and performance speeds are kind of slow depending on computation environment however we're going to be discussing all

these cons in the next little bit here and say what solutions we have to this so not all hope is lost not everything is bad and broken there are there is there exists great research on how to actually solve this and what we can do to actually make it usable right now so we'll go on a circuit design like I said branching would require pre computed values or interactivity between parties this kind of logic if this if true do this if false do this absolutely not possible to do that it would break chosen plaintext attacks security like clearly if you have some sort of logic

that says if this variable is this then do that of course you can't do that on encrypted data right it's encrypted you don't know what the data is however compilers are also being used to create easier built circuits okay so very similar to what you'd have with like snarky J s or other implementations for snarks we have compilers that are being developed to actually make it so easier to build the stuff in fact one of our hackathon winners at youth denver they were called trustless health they implemented a wasum interpreter to fhe logic gates which was exceptionally cool so you

could write your logic gate your logic and rust compile it to lhasa m-- and then interpret the wasum to perform the homomorphic operation very cool stuff chris peickert also has great research on his paper called alchemy it's more of an academic project it's called a language and compiler for fhe made easy I have a link to that there as well it also links to our hackathon winner there various schemes exist for different uses so if you want a different type of circuit that that is different from say binary logic gates then you can also use something like he Ann which is great for machine learning it uses approximate arithmetic which I'll basically just describe as like say you don't need an exact answer to some mathematical

operation you just need something near it approximate to it so that you can paint say perform some operation like machine learning or neural networking right tfhe uses binary operations and say you want to do both but you don't want to use different schemes well fantastic there is a framework for this called chimera that is currently kind of out there and getting some notoriety right now that we're also looking at it allows you to have interoperability between he an and tfhe so meaning you can go between the different schemes and perform computations and either so we'll get more into the security now fhe is inherently malleable anyone with the computation key can perform any

operation on the data right so only the encryption key holder can decrypt but so since we have chosen plaintext attack security as the highest achievable form of security here there exists also leveled fhe which enables us to actually achieve CCA security which may be more preferable right so when essentially what it does is it limit circuit depth and prevents some arbitrary computations but you're simply saying I will only ever do this circuit of this depth but no more no more computations other than that and we can actually form CCI secure protocols and schemes from that and also zero knowledge proof can be used to prove

correctness in in the computation to prevent malleability so we can theoretically we may be able to say are you sure that you perform this one circuit right so the example I always give is say you want to perform a computation on two encrypted numbers and you want to add them together say two plus two we may get the output of four and that's what you expect however because you can perform any computation you can do two plus two minus one plus one and it simply gives you the same answer but did you ask for that no you just want two plus two right so we may be able to use providing zero knowledge proof to prove that the computation was the correct one and that's something we are actively researching and we need to

learn more about that and see exactly how that can be utilized but we are working very hard on that bootstrapping requires the weak circular security assumption level of fhe does not if you do that I have Matt greens blog on that so if you'd like to see that definitely check that out their level of fhe actually doesn't require bootstrapping at all since you can build a circuit that will work for or build a scheme that will only work for this one circuit you can do that and then you don't actually need the bootstrapping part but you know cypher text size may vary and we're getting into weird realms there cybertek's are extremely large so as you can see here one megabyte plaintext is approximately 16 gigabytes of cipher

text that sucks but all hope is not lost ciphertext compression also exists I have some examples of a poor graph that I pulled off of a nearly dead PDF and it looks like there but essentially what we can do is we can before we perform a humma market hum amorphic evaluation on that data we can actually encrypt the data using a generic stream cipher like you know you're probably familiar with this as a ChaCha 20 right but we wouldn't use that we but we can use fhe efficient stream cipher to encrypt the data symmetrically before placing it in the hama morphic domain and doing computations on it what that means is we can encrypt the data before

as in the plaintext domain then as it goes into the holomorphic domain it gets encrypted we say with like a public key and then gets evaluated using a just hama morphic decryption so you do the you do the homomorphic decryption on the stream cipher encrypted data which will roughly keep it the same size as the original plaintext data so it allows you to you know keep the cipher text small in storage but expand it in memory which is great depending on what you need to do he an potentially only has a 40 X expansion which would be much much much better but that's kind of research level right now we're still evaluating that and also he and the authors or we're

still trying to figure out how that may be used performance speeds can be improved from GPUs Asics and FPGAs new ifhe has increased performance by a hundred times in the GPU so you see tfhe normally has 13 milliseconds per bit we actually achieved that speed-up to 0.1 3 milliseconds per bit making us as far as I know the fastest fully homomorphic encryption library available so that's pretty cool and on the GPU we also have NTT so that's with FFT we can also use NTT and it's still roughly 0.35 milliseconds the same speed as CUF HT which is another fhe library but of course this can also be improved with

GPUs ASICs and FPGAs which is something we're interested in so that's the talk obviously a ton of the extra information so if you have any other questions ask them please see me after I may even do a breakout session if anybody's interested in talking more about this and explaining some of these concepts but feel free to go on our website new Cybercom join our discord email me tweet us and definitely look at new fhe thank you [Applause] we have time for a few questions if there's anything anyone wants to ask right now otherwise we can take it to the breakout session afterwards maybe hello so when I have cached on the

decompression so this means that the I have you implemented this and tritium Saipa in the hybrid way your question is if we have actually implemented it yeah no this is all if you read a lot of the fhe papers they explain how to actually achieve this compression but it's well it's not I'd say it's outside of the realm of theory in my opinion that what we need more so is the existence of an fhe efficient stream cipher and to prove the security of those ciphers there's some examples here and this paper and I have that link there if you'd like to look into that but essentially you just need to implement that it's relatively straightforward bringing that out of the

papers and into the practical applied realm but it seems pretty straightforward right you just encrypt the data and then pass it along into the f18 cipher and then it can then perform the like a decryption circuit in the hama morphic domain perform the computation and then you're done it just expands in a memory make sense right yes - yeah AES does take a long time but that's also because it's not an fhe efficient stream cipher so there's been research into finding something that is much more efficient than AES right as far as I know actually we have spent up

a es computation and F H Eve actually quite a bit now but it's still you know not that practical we'd much prefer something like Caribbean 13 or something all right thank you very much thank you