The encrypted computer - Janmajaya mall

Transcript

[Music] Okay. Um hello hello everybody. Um I'm Jan MJ and uh I'm from Phantom Zone. Um today I'll be talking about something um something quite special. Um the encrypted computer. Uh so you might wonder what the encrypted computer is, right? So well the encrypted computer is sort of um is a black box. What it does is that it takes encrypted programs. So you write a program on your laptop. You

write it and then you encrypt it locally on your device and then you send it to this computer and this computer would execute your program without learning anything about your program. What can do in addition to that is uh this this computer can also take encrypted inputs from someone else and then can run the encrypted program on the encrypted inputs and give you the output and it guarantees that no one can um learn anything about the program. No one can look into inside its memory. No one can uh learn anything from the execution price. So everything remains encrypted. The only thing that you learn

is um are the outputs. Now um okay so uh for the rest of my talk I'm I'm I'm going to sort of ignore a very important question like why is this encrypted computer useful which is important in another respect and probably if you were at Jord's talk you would realize why it is why why it is important. what I'm going to focus on is how do we go about building this encrypted computer like uh how do we sort of get to the point where this is practical. So um the first question that comes to mind when you want to build the encrypted computer is essentially if you realize what you want to do is that you want to compute

on encrypted programs like you want to implement a virtual machine on encrypted programs. How do you do that? the then the question reduces to how do you how do you compute on encrypted information? How do you compute on encrypted data? And if you if you ask if you go around, you know, if you go to your neighborhood and ask a cryptographer over there or someone who's familiar with cryptography, how do you how do you compute on encrypted data? They their answer would be you know straightforward like just use fully encryption and the thing works. Um so what's what's fully encryption? Basically like for your Murphy encryption is a very simple idea.

What you can do as a user is that you have a private information. You are in a dilemma. What do you want to do is that you have private information but you want someone else to compute on a private information and give you something else using FG. You have FG secret key. You encrypt your private information using your FG secret key and you get an FG cipher text. No one can learn your private information but you can still give your F cipher text to someone else. they can uh compute on their FG cipher text meaning that they're actually computing on a private data and get then and then produce a FG output and then you get the output FG cipher text and you decrypt using your u secret and you can learn

your the the function evaluated on your private input given the fact uh right um Cool. So what did we do? We we tried building this encrypted computer and we in fact built it using FG. Um we for some reason call it phantom. Uh so we prototype this risk and and and what we did is that we took risk 5 virtual machine like risk 5 virtual machine spec and then we implemented uh the risk 5 virtual machine spec using FG circuits.

So we simply wrote the entire spec in FG circuits and then you and that's how you get a risk 5 virtual machine that is encrypted. Um so we put it out uh the full implementation is not ready yet. It is still under development. Um the VM does exactly what you want to do. It takes encrypted risk 5 binaries that you can write like you as a as a developer you write in rust. It compiles down to risk 5. You encrypt locally on your device. you could encry five binaries and the VM you send to the VM and the VM would execute it. As simple as that. The problem is that um it's pretty slow. It's like two cycles a second. While at the moment it's it's not still two cycles a second. It's I

think um it has it has increased to like 2.5 something like that. Um but um you know the improvements are happening. I so I I think that um with advancements in FHE and some engineering advancements and you know putting a lot of investments into engineering stuff and if you allocate resources to improving the speed of the risk 5 VM we would be able to make it a lot faster like this is just the first prototype that we have and gradually we'll be making it a lot faster and today's focus would not be this today's focus would be something

that FG itself cannot be solved but it is very important to but these problems are more important to build the trustless computer like the trustless encrypted computer and why is that the case because FG has a problem uh the virtual machine that we built using a fully free encryption needs someone to hold the secret key. The best that you can do today is that you can take the secret key and shard it among a threshold committee. So you have like multiple servers that hold some shard of the secret key and as long as these servers don't collude like they don't come

together and sort of play against you. As long as they don't collude everything is secure but the moment they collude things things sort of like break. So that's the best we can do at the moment with FG and we need to get around this problem. What are the missing parts? Well, there are two more things that are necessary. The first one is publicly verifiable FG. I'll get to that. And the second one is practical offiscation. The reason that I mentioned practical offiscation is because there exists schemes for offiscation but they're not practical.

and uh you know for the details that I'll mention later practical offiscation only for something called conditional decryptor suffices and I'll get into the details what that means so what is public verifiable FG well it's pretty simple you take you modify the FG scheme so that instead of just executing on on a on encrypted data it also produce a proof of execution it also produces a proof that have executed the FG circuit correctly. What why do we need this?

Well, one instance of this could be that we implement the entire risk 5 VM that we implement at the moment using normal FG. We implemented using publicly verifiable FG so that uh the virtual machine outputs the encrypted output which is what we need in addition that it outputs a proof of execution sort of claiming that I executed the program correctly. So you do not have to trust the machine to do it like you can verify it yourself. What is offiscation? Well, using a practical offiscation scheme, you can take a program P like any program that you want and you can transform it like offiscated and get a offscreen program and you can give this offscreen

program to anyone else. They can you know execute this program on any input produce some output. Uh think of it as like an API to the program. But what they cannot do is that they cannot learn the exact instructions of the program. They cannot learn anything about the implementation details of the program. One instance of this could be that you take your um you you sort of encrypt your uh program that signs using a secret key. You sort of offscate it and send it to someone else. Now anyone can produce signatures on your behalf but they can never learn your secret key if you offscape it. Okay.

So why are public why is public f and condition decryptor relevant? Well, what you can do is that um you can first have the rest five implemented with public f and it produces the encrypted output and in addition to that it produces a proof of execution and then you can write a program called conditional decryptor. This conditional decryptor hardcodes the secret key of the FG secret of the FG which was pro which at the moment is sort of sharded among threshold committee. It hardcodes the secret key and then it verifies the proof and then and if the proof is val and and it decrypts if and only if the

proof is valid otherwise it rejects. In this case you're trusting the offiscation scheme. You're not trusting the threshold committee anymore. Uh now you might you might you might be concerned like how do you hardcode the secret? Well the way we do that that we we sort of like perform a trusted setup that we do at the moment for zero knowledge proofs. We perform a trusted setup of skate this conditional decryptor with the secret key inside it and that's it. Um okay so what is the state of public f like how practical is it? At the moment you have to pay roughly like 1.5 to two orders of magnitude um cost over normal FG schemes but as uh all of us are

aware cryptographic proof systems and FHE both are like very uh both are advancing rapidly and uh I don't see any blockers in sort of like bringing down the cost of uh publicly ver verifiable FG to something that is more practical and that we can use rightly you would obviously have some cost over normal FG for public verifiable FG but I think it it would be somewhat minute I don't think that uh it is that a big of a problem so um I'm going I'm not going to talk about this further because the other problem that I mentioned offiscation is in much more depressing state um what is the state of scation well

there are multiple approaches uh there's no secure and practical scheme There is a pra there's a secure scheme. So we know that offiscation exists like we know that it is it's it is true but um there's no practical construction for it. I'm only going to cover two approaches and my intention with covering these two approaches would be to first sort of give you an intuition of what that is in addition to tell you about the problems and sort of give you a flavor of what the problems look like. The two approaches that I'll be covering are local mixing and offiscation of matrix branching programs. Local mixing is fast. It's practical but it's not secure. We don't know whether it's

secure. Uh we its security is based on things that we don't understand well enough. So we cannot say anything about the security and matrix the the offiscation of matrix management programs is probably secure but it's very impractical at the moment. Um okay. So what is local mixing? Well, local mixing says that you know instead of obscating boolean gates, I'm going to sort of change the model of computation. I'm going to offsiscate something called reversible circuits.

And you can think of reversible circuits as a collection of bit strings like collection of wires and you put in gates one after the other and each gate is itself reversible. What do you mean by reversible? Well, a reversible gate is something that if you put in the input, you get the output. You can always get from the you you can always go from output to the input as well. For instance, and gate is not reversible like because gate if you if you perform an and it loses information. But if you can express an AND gate in a reversible manner by something like this where you sort of like have a b and zero. These are the bitst string. you have this reversible and gate that sort of takes a and b and zords the third wire. So you

store the information of a and b into the third wire and you get art press a and b. If you look closely over here you can definitely go from this to this back by just going the other way around. So you take these gates many of them together and that's how you construct the reversible circuit. So the local mixing approach sort of says that instead of offsc offskitting boolean circuits, ledgers offskate reversible circuits. Now the reason for that is somewhat more involved but it somewhat follows from the fact that reversible circuits are easier to understand and has less surface area of attacks and they had it has some nice mathematical properties that you can play around with

to come up with proofs or something like that. Um okay. So the first step in offscation of local mixing like the first step in uh local mixing approach is to offscate a random reversible circuit like a randomly sample like you just sample a reversible circuit of nowhere and you have to offscate that. You can think of it as if you're familiar with cryptography as um you need to come up with an offic scheme that offscates a random functionality. That's the first goal of local mixing. So for now we'll be only concerned with how to offscate a random reversible circuit and there are two

steps to do that and I I call these two steps inflation and needing. What is inflation? Well, think of inflation as you're taking a small reversible circuit and you're adding a lot of redundancy to it. Think of it as adding a lot of um complexity fat to the circuit like uh I'm just I'm just adding a lot of fat. Uh and you blow it up in size. So you take a small circuit, add a lot of fat, blow it up in size. How do you add a lot of fat? Well, you take a smalls size circuit. So you take a sub subcircuit like a subcircuit in the reversible circuit of size two and you replace it with a

bigger circuit let's say say in this case of size five and the bigger circuit is functionally equivalent to the input circuit like the size two circuit and you do this many times over and over and over and over again and that's how you inflate the circuit you're adding a lot of fat to the circuit this is inflation the second step is needed Think of kneading as you've added a lot of fat. So you can obviously take away the fat, right? Like you can obviously very easily reverse the thing down. What kneading tries to do is that it tries to mix a lot of added fat with the actual computation. So that with the hope that after a while it becomes locked and you

cannot reverse it. You can think of it as if you're familiar with comp complexity theory um adding a lot of fat sort of decreases the complexity of the circuit and needing sort of hopes that with some randomization you spread around the added comp like decrease complexity around around the circuit so that uh at random if you pick a subcircuit it has enough complexity. Um the way kneading works is that you take again a size five circuit in this case. So previously in at the inflationary step we were taking a size two circuit. Now you take a size five circuit and you replace it with another functionally equivalent size five circuit. When I say functionally

equivalent the input and output of these two circuits are the same. Okay. So that's and you do this many many times with the hope that the circuit becomes locked which means that you cannot reverse anything that has been done to the circuit. Okay. So if we do these things, if we do inflation, we do needing how do we know that offscation is really happening. So to measure the effectiveness of offiscation, we define a very simple metric and the metric is how correlatable is the offscated circuit with the original circuit. Like how correlatable it is and there could exist

multiple huristics for correlation. And I'll I'll simply stick with do because at the moment for experiments these two suffices. The first one is something called computational flow heat map and I'll get to it what it is. And the second one is somewhat simple. It's like reversible circuit optimizer. You can think of it as a analog of boolean circuit optimizer. We have boolean circuit optimizers in the world. Think of it as a reversible circuit optimizer. Like you're reversing the um you're trying to optimize a reversible circuit and that's it. And if you're able to optimize the reversible circuit back to the original circuit, then obviously offication doesn't work.

Um, okay. So, we've got the these two things. I'll tell you what computational flow heat map is. Uh, okay. So, what is computational flow heat map? So, computational flow heat map sort of um, you know, I I wouldn't call it computation flow because it's pretty long. Let's just call it flow heat map for now. Um, so flow heat map sort of builds on a very simple idea. What it says is that you have two circuits of different sizes because original circuit that you offscate is way smaller in size than the offscape circuit. You sort of chunk these two circuits into smaller time slices. And if the state at any time slice of these two circuits, let's just

say the first circuit like you chunk these circuits into 10 time slices. So 1 2 3 4 5 6 7 9 10. And if the state of these two circuits the offscaled circuit and the original circuit at time five or like time I whatever I is if the state is moreover similar if it is if the states are similar of these two circuits at that time slice then they're correlatable which means that you can say that sort of the computational flow in the offscaled circuit is similar to the computational flow in the original circuit. So that's this this and and and computational flow heat map sort of builds on this simple idea. Um and if the state of the two circuits is similar for many time slices

then they're obviously correable and when we think it when I say of state think of as the Hamming weight like how many values in the state are zero. So how many values in the state are one think of that as the state of a particular circuit. So u you take build on the simple idea and that's it. So you build this heat map along this axis is the original circuit like time slices of the original circuit. Around this axis are the time slices of the offscated circuit. And each data element sort of like represents the Hamming distance like uh Hamming distance of the Hamming Hamming uh sorry Hamming distance of the Hamming

weight of the of the states of the two circuits at any time stamp. And if the humming weight is if the if the um humming distance sorry if the humming distance is somewhere around equal to the half of the wires in the circuit like reversible circuit has many wires if it is equivalent to the half of the wires then uh the circuits are not correlatable but if there if it is biased then the circuits are correlatable. So what you should observe in the heat map is that the circuits are not correlatable. You should observe something like this. But if they're corable, you should see a straight line.

Okay? So you see a very definite straight line when they're corable. Okay. So I've told you about you know what is offiscation? How do you do it? How do you measure the effectiveness? But now your question is is does this work? Well uh we don't know. We've been running experiments for a while. Um our experiments are explicitly designed for to get something conclusive. Up till now we have haven't been able to gather some information but we have some information that we can show like looks like there's something there but you cannot read it for too long like you should not overread this information. Um okay so the experiment one what did we do? Well we sort of uh ran ran inflation we took a thousand

gate circuit we sort of added a lot of fat. We inflated it to a 300,000 gate circuit and then we ran needing for 500k times and every time we were doing replacement at the inflationary stage we were going from two to four. So every inflationary step sort of increases the size by two and at needing we went from four to four and the results are that we did not observe any offiscation. Our circuit optimizer which is the reversible circuit optimizer was able to reverse the circuit or to the back to the original circuit and the correlation sort of like speaks tells you that the circuits are correlated right you see a straight line the two circuits are correlated the original circuit and the offscreen circuit and then we thought that we should try to do something more um so we

ran needing for like 1 million 5 million 10 million like it doesn't help you see still see the same thing but then recently we sort of um did something else. We sort of like took a 256 gate circuit and inflated it very minimally like very minutely. So we only inflated a 256 gate circuit to 1800 gate circuit like very minutely and then we ran needing for 500k times and we observed something special. We observed something like this. It's still coatable, but it's very blurry. And our circuit optimizer found it really hard to optimize it back. It was not able to optimize it

back. We still stuck at 700 gates probably from last night. Um, and it is not able to go below that. Uh, what changed? Well, in this case, nothing changed. The only thing that was changed was that we inflated very minimally and that's it. like we just inflated to 1,800 gates instead of inflating to 300k gates and then we sort of like we got curious we sort of instead of just running for 500k needing we ran the in minimally inflated circuit for 1 million times we need we ran needing for 1 million times I'm not sure whether you can observe this but as you run more kneading the graph becomes more hazy okay

Um so we don't know whether more needing would sort of like erase the line. We still haven't observed it but it's still running and these results are very recent honestly like I don't know like a week back or 1.5 uh two weeks back. Okay. So what is the takeaway? I'm sort of running out of time so I'll just quickly go through this. Um so looks like the key variable is that you need to be running more kneading steps per unit area of the circuit and inflationary stage only it seems to sort of like jumpstart the needing stage uh so that the uh needing stage can do its work. There are open questions as well.

Well uh first open question is you need to develop an understanding of like we don't understand the inflation and needing stage that well we need to develop a better understanding of these things. There's no security proof. So even one day our experiments be like you know the offication works you no one would trust us because there's no security proofs. So if you're researcher in the room you should sort of like think about these problems and we need to improve the sampling random circuits. Uh it's like a runtime thing. You don't have to worry much about it. Okay. Uh I think I only have like 30 seconds. Uh so I'm going to sort of skip a few things.

uh um you know these are like the impractical schemes and I would sort of like move on to credits basically. So I'm just the person who's speaking here. John Philip put in a lot of effort to build the phantom VM the risk 5 virtual machine. The local mixing approach is uh the experiments and all the things that we did was in collaboration with the authors Ron Kennedy Claudio Andre Ellie Bomb who's a PhD student Kari who wrote the circuit optimizer who and sort of which was able to sort of break off circuit Alexander who works in random zone and that's it right on time.