An update on the encrypted computer - Janmajaya Mall

Transcript

Um just waiting for the display to show up. Uh Okay. Uh it's the last day. I know it's a lot. Um and uh it's the morning as well. But um I'm going to keep my presentation. I I'm going to leave a lot of cryptographic details out of my presentation. I'm going to give an intuitive introduction to what the encrypted computer is. And I'm also going to tie it back to my previous presentation back in 2015.

Um but before that, hi, I'm Janmejay. I I work at Phantom Zone and I also run a company called Oxalabs. Um and I'm going to talk I'm going to be talking about the encrypted computer. First, what is encrypted computer? You can think of the encrypted computer as a machine that executes encrypted inputs on encrypted programs and it produces selectively either public or encrypted outputs. So, you think of this as a black box machine in which it just takes the input, produces the output.

You cannot think You cannot look inside it. Um and it cryptographically guarantees that no one can look inside the machine. Now, you know, this might look like a black magic, but today I'm going to describe you like couple of methods on how to achieve that and sort of like make it clear that it's not black magic. Um Okay. So, the first part the first part that we started to explore to build this encrypted computer was Phantom. You can think of Phantom as a RISC-V virtual machine that is built using FPGA circuits.

And in ETH Zurich 2015, I introduced Phantom as a prototype. Back then, we estimated that Phantom as a RISC-V machine um, which can execute arbitrary code, um, would uh take roughly two cycles per second, which is immensely slow than ZK VM that, uh, Jardi presented previously. But, we found as the implementation last remember, and it takes a approximately 600 milliseconds on 32-core CPU, and we expect roughly 100 to 150x improvements using GPU, but with the caveat that we do not have a GPU implementation yet.

But, there's a problem that, uh, Phantom faces. The problem is not just particular to Phantom, it's because we're using FHE. In FHE, someone needs to hold the secret key. Who holds the secret key in this case? Well, the best practical answer to that is something called threshold FHE committee. Um, and in my opinion, this is not ideal for two reasons. First, secure threshold systems are really hard to bootstrap in blockchain systems. Like, people have been trying to do this for, I don't know, half decade now. It is In my opinion, like, it's not doable.

Third, collusion, particularly for threshold FHE systems, is not possible. Like, it's not possible to detect. You cannot You cannot detect whether someone has colluded and leaked the secret and hence leaked privacy. Um, and of course, threshold committees, you know, they they may work for closed and gated systems, but when we speak of closed and gated systems, those are not decentralized systems. Um, okay. Which started, you know, which which, uh, roughly two years back, you know, started us to question like whether there's any other path apart from this, and that did a transition from FHE to something called obfuscation. And back then, obfuscation was, you know, this

this fancy thing for which there existed this impractical construction that would take, I don't know, a gazillion years to execute, etc. etc. Um Okay, so the road map for today is that first I'll tell you what is obfuscation, and then I'll tell you about our evolution and thought about uh around FHE plus obfuscation, and then I'll give you an update on the local missing approach to obfuscation, and an update on other approaches to obfuscation. Okay.

What is obfuscation? Obfuscation simply says that you take a you you need a method with which takes a program, does something to the program, and produces an obfuscated circuit with the guarantee that if you give the obfuscated circuit to someone else, the other person should not be able to recover anything about the program other than the input and the output. So, for example, you take a program, you put your secret key inside it, and this program signs on your behalf. Let us say Ethereum transactions. You can now obfuscate this program using the obfuscation procedure,

and produce an obfuscated circuit and give it to someone else, so that someone else can sign the Ethereum transaction on your behalf without learning your own secret key. Now, if you are in Ethereum space for a while, you will understand why this is useful. One instance why this is useful is because now you can have smart contracts signing stuff for you based on some condition and have the secret key. Okay. So, back in ETH Bogota 2015, I presented this uh one method of uh obfuscation, which was you have FHE. In particular, you have publicly verifiable FHE, publicly verifiable FHE, and you have Phantom that takes an encrypted inputs. It takes in uh

Okay, so for some reason it's that visible. Okay, sorry. Uh uh uh it takes an encrypted program and it takes the encrypted inputs and it executes the encrypted inputs and outputs two things. It outputs the encrypted output and a proof. Okay? We're using publicly verifiable FHE in the sense that the it's like ZK plus uh FHE if you want to look at it that way. It's not ZK in the sense because ZK is zero knowledge. Publicly verifiable means like this it's just a sync proofs. Uh it produces the output and proof of execution.

And then we obfuscate a very small functionality that I refer to as the conditional decrypter. And this conditional decrypter uh takes in the proof and if the proof is valid and then it will decrypt the uh output ciphertext. Otherwise, it returns null. And the reason we do this and the reason we need a proof is because the conditional decrypter would decrypt anything. The proof sort of like makes sure that it only decrypts the output of the phantom via. Um Now, the logic back then and I think that still today um if I look back seemed sound in my opinion

but because, you know, obfuscation as a cryptographic primitive is harder than FHE. Intuitively, logically it should be more expensive. So, you should try to lift up as much of computer as possible into something that is more practical today, which is FHE. And only limit obfuscation to a very small surface area, which is this conditional decrypter. Um but however, uh looking at the progress that we've made in the past year, it feels like uh it's just an intuition today, but it feels like it'd be more practical, perhaps more practical, to obfuscate programs directly.

Hence, in my opinion at least moving forward, we as a research group, I'm working with other people on this, are going to discount this, you know, method out of FHE plus conditional decrypter. Which brings us to the next topic, which is the local mixing approach. This is one of the one of the methods of achieving obfuscation, and this is one of the methods we which in which we have uh progressed quite a bit in the past year. So, what is local mixing approach?

You can think of local mixing approach as a new approach to obfuscation that is efficient, but it is not yet provably secure. In local mixing approach, you first shift your computational model. You go from circuit land to reversible circuit land. What is reversible circuit? Intuitively, you go from this Boolean circuit model to this reversible circuit model, and in a reversible circuit model, the logic is pretty simple.

You never lose information. From input, you get the output, and from the output, you can always get it to the input. That is not true for Boolean circuits. For example, an AND gate, you lose information. You lose the inputs. But in a reversible circuit, an AND gate would look something like this. Where you, in addition to getting the output, you also get to the input as the output. So, you never lose information. In a reversible circuit, the goal is pretty simple. You need to find an obfuscator method which, when applied to circuit P for program P, outputs an obfuscated circuit that satisfies the definition of obfuscation. Like, you should not be

able to learn anything about the obfuscated program. Sorry, you should not be able to learn anything about the original program P from the off-the-cuff program. So, in ePrint 2015, roughly a year back, I presented local mixing as a two-step procedure called inflation and kneading. In simple words, what is inflation? Inflation adds a lot of redundancy to the circuit.

It takes small parts, small gates, small pairs, I suppose, in the original circuit and inflate it, and like add a lot of fat to it. So, that the circuit becomes large. And intuitively, you can think of it like adding a lot of rubbish data to the circuit, so that you cannot figure out what it does. And then, we do something called kneading, which is the third slide here. In kneading, you're just jumbling everything together. You're just mixing it well, so that no one can unroll the off-the-cuff circuit. And of course, the got the exact procedure is way more complicated than what I'm describing, but you know, intuitively, that's how it feels like. And at And And a way to test, I presented something called heat

map. You can think of heat map as trying to find correlation between computation across the off-the-cuff circuit and the original circuit. Um Intuitively, you can think of this is what I refer to as heat map. On the Y axis, you have the original circuit. Sorry, on the X axis, you have the original circuit. On the Y axis, you have the off-the-cuff circuit. And each ax- like the graph represents the computation flow. And if the computation is correlated, you would see a straight line.

If the computation is not correlated, you would see something jumbling here. By the way, this is not off-the-cuff, this is just two random circuits that I just sampled. Okay? So, we do not have a like we have a heat map that looks like this, but you know, this one is fake. Uh Okay, and then I I I ended with an experiment that sort of showed a hazy line. Like something that is ideal, but with a hazy line. And I made a claim that if you do more kneading, you'd be able to erase the line.

Um but then we went back to whiteboard. Uh Turns out like doing more kneading steps would erase the line, but it would make it much more harder to look at. But there were few critical questions that we were not able to answer. Uh first is like when to stop kneading. Like this you just keep doing for years and years and years. Um second question was like whether the adversary, assuming the adversary know which was the last kneading step, wouldn't the adversary be able to start unrolling the thread from the last kneading step?

Um and what about second order attacks? Like for example, heat map is this first order attack. Second order attacks are something like differential analysis where where you try to figure out something from the degree of the computation. Um and differential analysis is pretty common in symmetric crypto. And why can't anyone apply that to our methods? So this led us to sort of quickly analyze our methodology and segment the procedure into a preprocessing step, which introduces high degree which introduces high degree uh high algebraic degree to the circuit, and a four-step repetitive process. And I'm quickly quickly go through them.

So the first step is high algebraic degree. What we want is First, you can think of each s- wire in the reversible circuit as a polynomial. If you take a random reversible circuit, the degree of the polynomial would be very low, you know, not that high. We want to make sure that the degree of uh polynomial of each wire is high. So, what we do is that we XOR the wires together. So, we take one wire in one computation XOR with the other one, and we do it at randomly.

This increases the degree, but this changes the functionality. Then we introduce something called gadgets. I'm not going to go into uh going into detail of what exact what is the exact structure of the gadget, but think of this gadget as this magic thing which reverses the computation so that you get to the original functionality. By the end of this preprocessing step, you should have a circuit where each polynomial uh which where each wire polynomial has very high degree. So, you get around differential analysis. Okay.

Now, we come to shuffles, which is the first step in the loop. I'm going to describe four steps, and we do them repeatedly for three to four times. Shuffles. You can think of intuitively shuffles as uh shuffling the wires and shuffling the gates. To be more specific, this is the method uh you know, I can go through this, but this will take time. Uh but intuitively you can think of it like shuffling the wires together and shuffling the gates together.

Making sure that the functionality remains same. Shooting. Shooting literally means what it says uh says basically. You take each gate, and you try to shoot it as far as possible in the circuit to the extent it is allowed without changing the functionality. You just shoot it as far as possible, and that's it. And this is this is useless until you do the third step because this doesn't change the structure at all of the circuit.

This is useless until we do something called locking. So, what is locking? Locking takes the circuit. For example, let us say you have a five gate circuit. It takes the first two gates, replace them with a large identity circuit. Identity circuit meaning that it computes nothing, but it's just it just looks like a large chunk. So, it takes the first two gates, replace with a large identity circuit, and then do this repeatedly for each pair of gates again and again and again and again and again until it reaches the end.

You can think of it as we have taken the computation of the circuit and we've introduced redundant blocks within the circuit, which you cannot compress, and hence we have locked the circuit. Okay? But, this is a randomized procedure, which is why after this we run something called compression. Compression simply means we just have a really good compressor that just try to reduce the size of the circuit. That's it. It's like a brute force procedure. You have we run it like, I don't know, for I don't know, couple of minutes, and it try try to reduce the size of the circuit, and then we go back to shuffle, do it again, shuffle, do it again. The more time you do it, the better the

results are, but we expect that doing two to three times will suffice. Okay. Now, I'll show you some fancy graphs. Uh Now, this is what a reversible circuit look like. You can think of the vertical lines of the gates, the horizontal lines of the wires. Each gate, yeah, I can describe you what the gate is later. If you only do shuffle, this is what the circuit looks like. You can think you can you can see big chunks here.

And you can see the data lines. What are data lines? Data lines are the original wires, original original gates in the original circuit. You can see in this particular subsection, by the way, this is a huge circuit. In this particular subsection, you can see two data lines that are visible. This is with shuffle only. And then we move from shuffle to shuffle plus uh shoot plus lock. And then you would notice that the original data wire data gates have been jumbled up with random gates.

And they're no more visible. And we measure the entropy of each wire in this particular circuit, it's nearly 0.5. Range you know, taking a scale from 0 to 1. Um And the heat map looks fantastic. Look at this. Um Anyhow, the blow up in this circuit is roughly 100 to 1,000x. With two to three rounds, the more you do, the more the blow up, but again, we're trying to make sure that the blow up remains as much as as minimal as possible. And this is good news because I I work in FPGA, and FPGA has a million times blow up.

Uh this has 100 to 1,000x, which is way way better. Um What's next? So, I think we're ne- nearing the end of our first iteration, which is which is a real year-long iteration. Um we we would be releasing a challenge with a collection of obfuscated circuits, uh putting our method to test, and see what happens. And one of the best way to contribute to this effort is to try breaking this challenge. Reach out to me and try breaking this challenge.

Um if you want to be notified when the challenge is released, which would be roughly in, you know, 1.5 to 2 weeks, depending on how efficient the code is. Um You can scan this QR code, enter your email, and I'll send you an email when the challenge is out. Okay. Now, other approaches. The other approach is from Machine IO. Oh, sorry. Makina IO. Uh it's a team from Ethereum Foundation that is working on uh building obfuscation from secure approaches, so not taking the not not doing a departure from existing cryptography the way we have done.

Uh but instead trying to use existing cryptographic primitives to build obfuscation. They have pulled off something that in my opinion I I I told the person that's not possible a year back. They've pulled out an exact implementation of Diamond IO, which is an obfuscation scheme based on cryptographic like secure cryptographic primitives. Um The implementation has practical lattice parameters, but again astronomical um uh execution parameters. Meaning, you know, it will take I don't know how many years before I die before it to be executed.

Um The key improvement in Diamond IO is something called key homomorphic encoding, and just think of it as like a a step towards getting obfuscation using lattices, which is a cryptographic primitive. And the next step for them is to find an efficient technique for homomorphic encoding. Um you can check out their work at makina.io.com. Um Okay. Cool. Okay. So, by the way, I'm just the person who's speaking here. There's a huge team behind this. Uh for local mixing, I would like to credit uh Ran Canetti, Claudio Eduardo, Andrei Nikolaev, who has done a lot of code. He has written most of the code. Eli, who's a really good PhD student BU. And Iggy Man, again a PhD student BU. For

Phantom, um most of the work was done by Jean-Philippe and Rasul. And for Makina IO, most of it done by most of the work is done by Sora. And that's it. Thank you.