DAPPCON 2019: Fully Homomorphic Encryption & Secure Computation - John Pacific (Nucypher)

Transcript

hi so I'm tux I work at new cipher I'm a cryptography engineer there what we're gonna be going over today is fully homomorphic encryption and how we get here from other secure computing solutions so as a brief overview I have a lot of material to cover by the way so we're gonna go through this really quickly and if we have time for Q&A afterwards I would love to talk about it and get some feedback from you guys on what you understood and what you didn't so I can clarify it so we're gonna be going over what secure computation is what technologies can be used for secure computation multi-party computation trust execution environments fully homomorphic encryption the shortcomings of each approach and solutions for an fhe based approach and what new cipher

has contributed to the space for that in the previous talks I've probably heard people talking about MPC and T's as well and so if you're going to be we're going to be discussing really the specifics of those solutions and why they may or may not be good for the applications being developed today so what is secure computation this is a diagram of a two-party computation protocol where Alice knows some data point or variable X and Bob knows some variable Y and they want to perform this function f did you see right there very top where the nodes are there I perform some function up with those two inputs x and y without revealing any of the information on that so what does this mean for secure computing in general parties involved

have a requirement for privacy to some degree usually they have a need to perform some computation on data that is considered secret or private requirements for zero knowledge are not required but can be present meaning like we don't want to reveal some information in that computation so some of the information on those variables sometimes the requirement is there sometimes it's not but in general in secure computation there is a lack of trust in the computational setting what this means is we're talking about adversaries and threat modeling so we you're probably familiar with network level adversaries you know if you're in China or Turkey you may have a government that is sophisticated that

does deep packet inspection and where things like encryption may not be great because it starts flagging your traffic and there so what that means is we just have some adversary that is seeking to break the confidentiality or gain some knowledge about that computation or performing solutions can exist in both in hardware and software and while we're going to go over the specific solutions and what that actually means but really what it just means is that something can be written written in hardware for secure computation or something can be made in software so something like a multi-party computation protocol or an encryption scheme or something like that the threat models vary greatly between different

solutions so for example the threat model you use for something like fully homomorphic encryption may be vastly different from the threat model defined by Intel's SGX and what a threat model is it pretty much says here's the attacks that are able to be performed on our technology and here's what we're trying to prevent against some threat models pretty much exclude things they say we don't care about that type of attack the very common one is we don't care about somebody who has local access to a machine because typically once you can touch a keyboard of a computer that's all that's running or have access to it you can violate it in many ways to gain access to it so in those cases the threat models are very you specific so it depends greatly on what that

implementation is so let's dive right into multi-party computation multi-party computation is a software based security protocol security reduces to the cryptographic primitives used like Shamir secret sharing and in many cases it's built upon principles of mathematics usually so we have when we're saying software based like I said it just means that we can implement something using mathematical security or provable security that says if somebody can break this and they can usually break some mathematical hard problem obviously there are multiple parties involved and data is shared between all the parties the computing parties gain no knowledge of the inputs to the circuit and where that circuit is is a

actual computation so that and when you hear the word circuit I want you to think of like program or logic flow the input data is split and share at the beginning of the protocol and reconstructed at the end so if you can see in the diagram here at the very beginning a party will say Alice splits up a secret piece of data a plane usually like some plaintext she splits it up and distributes it distributes it to multiple parties those parties then perform our second stage here that computation that's the circuit being performed that's represented by that binary addition that binary multiplication there and then at the end that reconstruction is usually Alice or the person requesting that computation to be done receives all the inputs back out from that computation of the output

of that circuit from each party and performs a reconstruction usually associated with that secret sharing scheme so at that point there that data is then put back together and naver they've achieved the output of that computation without usually the people in the middle performing the computation actually learning anything about those inputs so now we're gonna get into trusted execution environments and what they are so as you can see in our diagram here just it's and well actually I'll go over that just in a second but all right it's a hardware based security protocol so what that means the security reduces to the safe implementation of an Enclave on a process and that's specific towards this solution here we have a

platform and that diagram usually something like a CPU or a trusted platform TPM that's usually a chip on a motherboard what you want what I want you to think of when you say when you hear Hardware base security is a separate partition in silicon what that means is we have like a little piece on the actual silicon of a chip of a processor of a motherboard that acts entirely different from the rest of the computer and there is an API in which you access it but there's only some functions you can do and it performs those away from the rest of the machine where the rest the machine should not typically have access to it most of the nations are vendor specific in our case proprietary and close source

so if you're building open source to technology this becomes a major problem things like Intel SGX which has become very popular in the blockchain space AMD PSB arm trust zone these are examples of trusted execution environments that are accessible to the consumer class so it requires a court API you see that little brown box it could be brown I'm color blind so I don't know what that is but it says t client API and what you're when you build an application in the rich execution environment there meaning if you're actually getting some Python code or some C code or rust for example you're going to typically be in executing stuff in the current are on the kernel on the operating system where

other programs have access to that's the rich execution environment and what you're going to do is when you access other T's you're typically going to be accessing that T client API and it's going to access the core API inside the other chip and that's what we call the trusted execution environment there where your code doesn't have direct access to that data being executed there these things can be functions specific and you're typically going to see these more often than not if you know a ub HSM that is consider that can be considered trusted execution environment it's a hardware security module that performs signing key generation encryption things like that and put things like Intel SGX are more generic which let you do a few other things beyond that but typically

these solutions here are increasingly problematic because of hardware and and because of hardware security and I'll get into that a bit later but typically the function specific ones like the UV HSM are typically better for security than the ones like IntelliJ X which are more generic so now I'm getting into the big thing that everybody came here for fully homomorphic encryption it's a software based security protocol it's a form of encryption it's implemented with lattice based cryptography and reduces to mathematical hard problems associated in that space specifically things like learning with errors I'm not gonna dive into the technicals of what that exactly is but when you think learning what there's think about like a lift at curve

cryptography with discrete logarithms and things like that a major benefit to this is that it's quantum resistant so if you're worried about quantum computing which you don't really need to be right now but to be fair it is quantum resistant solutions exist for both single and multiple parties I'll get into that a bit more later the function is computed directly on the ciphertext so what that means is we take an output of an encryption function and we can actually perform a program or some logic digital logic on that ciphertext directly without ever knowing what the underlying plaintext is so the output of the holomorphic computation is equivalent to the computation performed on the plaintext so if you were to perform if

you were to add or multiply two cipher texts together it would be the exact same equivalent is adding or multiplying two plaintext that should help this diagram here makes it a bit easier to understand that where you can perform the same function f on that plaintext m and get the same exact function that you performed on the encryption typically there's two keys used this is for security and I'll go into that also a bit later but we have an encryption key used to encrypt and decrypt the data in a computation key which a party needs to actually perform the computation on that data so diving into some pros and cons on multi-party computation circuit design at MPC is pretty nice you can construct it with boolean logic gates

debugging is straightforward you can perform a reconstruction operation in the middle of the circuit meaning that you can just say oh give me the data now so I can figure out what my logic is doing you can reconstruct it security is awesome it reduces to relatively simple secret sharing scheme that's great however circuit designs some cons about that requires initial zero knowledge proof to make the protocols secure which can add a ton of complexity and it also makes it and also branching is either impossible or kind of complex operations are performed on split a plain text data so still plain text data collusion results in the breaking of the confidentiality of that data complexity grows linearly with the Circa size I'm

not going to get into the technicals of this but essentially what it means is when you start having to include network overhead when you have to start including zero knowledge boot proofs it becomes incredibly interactive and difficult to scale there's a large liveness requirement every single party needs to be online to perform the computation an offline node can result in blocking of the entire protocol from advancing and like I said network latency wreaks havoc on these protocols so if that's a problem in your networking environment it's probably not gonna be ideal for NPC so now we're gonna get into trust and execution environments and to be honest I don't really have a lot of good things to say about it so I'm not really going to talk about the pros for just time but I will make it you saw an argument about why

you shouldn't use T's debugging is complex that's not big issue for me but there really is no way to peek into the actual processor and say tell me what you have it just performs its functions when you say so so it becomes a little difficult to debug them reductions reduce to the difficulty to exploit the hardware which if you've been paying attention to the hardware security seen specifically Intel and AMD for that matter this is a really bad way to base your entire decentralized network and protocol and things on top of because it's not that difficult to exploit hardware especially since the threat model is preventing limited local access which these things don't really do a

good job of doing free look at side channel vulnerabilities like specter and meltdown which led to foreshadow which you broke the Intel secure Intel SGX security which leaked what we call the attestation keys attestation keys essentially said I can prove that I performed a computation in SGX and they were able to say I can perform I can do anything and say it came from Intel SGX they actually made a Twitter bot that you could tweet out it and it would sign anything and say I was purported until I see X so Intel SGX when you hear that I want you say this is not ideal for a trustless environment so it's called a trusted execution environment remember that it's not great for trustless

trustless technology it requires trust in the vendor there are no working open-source implementations there probably won't be there's too many of the like I said the attack surface on hardware is massive so this becomes really difficult to do and updates require Hardware replacement so in the case of foreshadow all the Intel processors out there at the time if they were we pretty much don't know if it was explaining or not so if you're building on top of Intel SG sorry it's kind of broken so fully homomorphic encryption lots of things to say can also be constructed with boolean logic gates debugging is straightforward just decrypt the state as required there's also schemes to construct it for

integer operations if you don't want to use logic gates operations like I said are performed directly on the ciphertext and it requires the computation key to perform those operations they can be performed with single parties or multiple parties in case in case of multi key fhe and it only requires the liveness of the computing party so in the case of one person you encrypt data for that person and then they start performing operations on that ciphertext and give it back to you so if that person is not available you can trust anybody who's just going to you know give you just perform the computation however branching is impossible when you design circuits or incredibly complex and requires specific algorithms to be constructed a lot of people are working on this space so if you pay attention to a few in universities that are specific

in fhe we're seeing a much more healthy ecosystem through this but it's still a problem another thing is fully homomorphic encryption is inherently malleable meaning that anybody can manipulate the ciphertext this is a given because we are operating on that ciphertext if you can perform some logical operation on that ciphertext clearly anybody can do whatever they want to it so the best security we can achieve is chosen plaintext attacks security or CPA security ideally you want to see CCA security but that's just not possible with fhe yet but there's other things we can do and I'll get into those another thing is that bootstrapping which is the technical term for what we call a homomorphic decryption while inside the holomorphic domain kind of complicated but it enables us to do arbitrary

computations on that ciphertext requires a strong assumption called circular security I have a Matt Green has a blog post I have a link in my presentation with it that will explain it very easily to you so I recommend you look into that if you're interested cybertek's are large too by the way this is the part that everybody's interested in is tfhe which for a 256 bit security level has about a 16 thousand times expansion factor so if you encrypt one bit it goes up to 16,000 bits not great but this is actually becoming less and less of a problem we actually have solutions for this which I'll go over in a bit compensation keys can also be large so 100 megabytes for a little kita you distribute to somebody to actually

perform the OP the computation and performance speeds are heavily dependent on the computation environment so in some cases we need to have it will specifically a new Cypress contribution we can actually perform these holomorphic computations on GPUs so of course it depends on the speed of your GPU to actually perform a fast computation so getting into this circuit design requires for branching would require pre computer values or interactivity between parties so if you see that like that little selection there that's a branch in case you've never seen one before that's impossible in fhe unless you do a few things because that little if true or false

would actually violate the security and so it's actually not possible however compilers are being researched easily construct these digital circuits one of our hackathon winners Denver implemented a Watson interpreter for fhe where they could write stuff and rest compile to blossom and then we could actually execute that Chris peickert a researcher in the space has published a compiler for this it's actually pretty cool so if you're not research check it out there's other schemes too for fhe for different uses approximately rithmetic it's useful for machine learning so it's like you can you know I'm not gonna get into that I own a time but tfhe is useful for binary operations this is what we've implemented with new

fhe and I'll get into that in a bit but you can do like X or noir and not etc and then chimera is an interoperability framework for all these different libraries he an and tfhe specifically as well as a few other schemes which allows you to go between both so you can do a lot of really interesting stuff there so security like I said fhe is inherently malleable anyone with the computation key can perform any operation on the data however only the encryption key holder can can decrypt it so you act as like a little you act as a barrier between a lot of attacks there like I said chosen plaintext attacks security is the highest achievable security however we have leveled fhe which actually allows us to women's circuit debt and

prevent some arbitrary computations meaning that you normally with fhe we can say I can perform any in operate I can reform any arbitrary number of operations and that's that however with level fhe you can say I can only perform in operations and with that we can actually achieve CCA security for some stuff zero knowledge proof can actually aid in this to prove the correctness of a ciphertext to prevent some of that malleability and increase the security in general just a bit this is something that new ciphers actively researching and will be presenting some of our work at Def Con later this year in October bootstrapping requires like I said reach bar is a strong circular security assumption however level that pacie does not require that again see

Matt Greene's blog post on this if you're interested in learning more about that it's a scalability everything the thing everybody's interested in right now cipher texts are large right one megabyte sixteen gigabytes however we have ciphertext compression we can actually use a fhe efficient stream cipher essentially an encryption function to encrypt the data symmetrically before computing it in the hama worship domain so essentially you can encrypt the data before you put it into this hama morphic domain itself and then you can have the computing party decrypt it inside the hama morphic circuit so that expands in memory only instead of on the disk this is really great people have been using this with

AES but there are like if you see this table here there's actually a few schemes that are really really nice now coming out for that newer schemes are coming out like he an that only have a 40 X expansion which is a huge improvement and we expect to see many more solutions coming to actually make this far better so in my opinion it's not that big of a problem performance speeds can be improved through GPUs basics and FPGAs we have our library called new fhe which has increased performance by 100 times so we have our speed up here 100 point 9 for Tia for new fhe over tfhe for binary gates and as well as the much larger

speed up for MUX gates like ternary gates I actually believe that no fhe is the fastest fhe library in the world so if you're actually wanting to like dig in and figure figure out stuff and play with fully homomorphic encryption figure out how it works it's written in Python you can easily write holomorphic circuits with it we use it to win ether Lin last year where we wrote Sputnik which was the first ever fully homomorphic smart contract so if you're curious about that please play with it we'd love to see what you think so yeah that's it thank you for coming please check out our github a new cipher dev slash new fhe for new ciphers fhe library our discord feel free to email me with any questions

and I'll respond as soon as I can follow us on Twitter happy to take questions too by the way thanks [Applause] so when you fall when you encrypt something and you're trying to prove that a computation was done correctly it's very similar to pretty much saying when you perform it when you perform an operation on plaintext say you add two

numbers together you can prove that some two numbers were added in zero knowledge typically so with fhe in there in the literature fhe actually implies zero knowledge so the existence of a fully homomorphic encryption implies the existence of zero knowledge proof which zero knowledge crisper found way before I think she was but that's the side point but in the case of proving this data what you're trying to aim to do is prove that the computing party who did a computation actually perform the right one right so we're trying we're trying to find different ways of doing this mainly through the use of like different technologies like bulletproof soar even lattice bases your knowledge proofs and we're trying to simply say when we prove that what's called well-formed

ciphertext so when I encrypt some data for you to compute on something I want it to say I want you to prove that this ciphertext actually has some format or structure inside of it that I know is the computing party when I do it I can still say it still is okay right so that's it's it's it's hard to we can talk afterwards because it's fairly technical and I would actually love to share it with you sorry no it's it's hard to explain but it's a typically it it can be structure it can be content what you're just trying to say is that this ciphertext that I encrypted is actually what I encrypted if that makes sense and typically it can be structured

to some degree yes they have a kind of computation key so they can pretty much return whatever they want they can do whatever computations they want so our goal in research has been able to what we're trying to aim to do is say I want to do this circuit can you prove to me that you did this circuit correctly that's so that's where our active research is that's what we're doing and we'll be talking more about that at that yeah yeah any other questions no other questions wow you guys understand that thank you really well all right great all right thanks again guys