An update on Local Mixing (iO)

Transcript

[music] [music] Um hello um hello everybody. Um before I start um a quick show of hands of how many of you guys are familiar with offiscation. Okay. So before I move on, I'd like to give a small brief about what officcation is. Well, offiscation is a cryptographic technique to u take a program and do something to the program so that you get an offscale program and when you give

this offscreen program to someone else, they cannot learn anything about the program uh except for the input and the output. Um so for example you can hide a secret inside this program give it to your friend and your friend wouldn't be able to find what the secret is. So that is what offication is and I'll today I'll be talking about um I'll be giving a high level but still bit technical level uh technical uh introduction to local mixing and uh and then after that I'll you know in short try to motivate offiscation and local mixing.

Um there you go. So you know u before this presentation I was chatting with a close friend of mine. He's like do hard things first. So in this presentation I have two parts. In the first part I'll as I said I'll giving a high level introduction to um high level but still technical introduction to local mixing which is hard for me. And then in the next uh in the second part I'll be giving um a short motivation for why do off sketch and local mixing.

Um before we start to learn a bit more about reverse uh local mixing, there's some background information that I think I shall tell you about. Um so the most crucial piece of information is uh something called reversible circuits. Um so and the reason reversible circuits are important because in local mixing we offcate reversible circuits not boolean circuits. So what is reversible circuits? Uh what is a reversible circuit? Well, a reversible circuit um composes of reversible gates and the computation happens from the left to the

right. What is a reversible gate? Now well a reversible gate um consists of three kind of wires. The first one is the target wire and the rest of the rest are the control wires. in a a particular gate only mutates a target wire based on some function which is a boolean function computed on the control wires. So reversible gate only mutates a single wire which is the target wire.

Um and it's it's quite important to observe that in a reversible circuit the computation can always be reversed. So you can always go from the output to the input. Um okay. So so far in our research there's some the there's there's a particular gate that has been really helpful for us and we call that gate gate 57. Um the only difference in g so the only special property of gate 57 is that um it uh the target wire over there uh flips if and only if the um positive control wire

which is the b wire here is one and the negative control wire which is a c y wire there uh is zero. Um and now surprisingly well surprisingly gate 57 is universal. So you can build any circuits out of gate 57 it'll be fine. So at the bottom we have a diagram of an gate only constructed using g57 subcircuits. [snorts] Well in our offcation procedure we do a lot of subcircuit sampling. So what is a subcircuit? Um, a subcircuit is a small section of a big circuit. Now, there are several ways of sampling a subcircuit.

The first one is naive and the and there's a better version. In n version, you simply take the contiguous gates in a circuit and call it a subcircuit. But this has a problem. This is representation specific. In the better version, we pick gates that are convex in nature in the sense that you can you the gates here are not contiguous but you can rearrange the circuit to build uh to bring them together. And we call such gate set of gates as convex uh circuits. And if you were to draw a dependency graph of the circuit, you would see that um you can bring all um when you when you draw a dependency graph of the circuit, the conveys gates

from a conveyor subgraph. Um okay. So first attempt um in our first attempt we'll try to officate a random reversible circuit. Um what's a random reversal circuit? Well um for our purposes random reversible circuit is consists of bunch of reversible gates sampled at random. That's it. Um and the property that we want from a rand reversible circuit is that the output permutation which is the output of the circuit should be indistinguishable from a truly random permutation.

So we have two stages in our first attempt. First one is an inflationary stage and the second one is a needing stage. In the inflationary stage, we try to blow up the circuit. What does that mean? Well, we sample short subcircuits again using this subcircuit sampling procedure that I read before and then find a larger circuit that is functionally equivalent to this circuit and put it in place. That's it. Um at the kneading stage we want to thoroughly mix the circuit. So you take again you sample a small circuit a small subcircuit and replace it with another

circuit of the same size and that's it. So the two procedure at this uh uh in a first attempt versus like infl inflationary and the second was in needing. Um now how do you find replacements? Well, what you can try to do is that uh you take a subcircuit and try to find the replacement on the spot on the fly like just brute force to try to find the replacement. Well, you know there's so many circuits that good luck with that. Um so the idea that we came up with is that you a better version to do this is that you construct a table that consists of all the possible circuits.

Now if you were to true that the table is going to be really large and it's it's like if you look at the numbers it's improbable. Um so what we did is that we defined we first observed that many circuits are just structurally redundant um in the space of circuits. Uh and then we define a canonical form for the circuits and we only store the canonical circuits. And as you notice the requirement the the hardware requirements for after postconicalization is just very small. It's like 300GB.

So what we hoping on for what are we hoping for in the in the in the first attempt? Well, what we're hoping for is that once you've inflated the circuit enough um which is post-inflationary stage in the kneading stage, we mix it thoroughly so that we put the circuit in a stationary state in a manner that coming back to the original circuit is just computationally infeasible. And if you're familiar with Kaly graphs and graph theory, this is an alternate view of how would you view this kneading procedure.

Um, so exactly what are we hoping for? Well, what we want is that the structure of the output circuit is completely distinct from the structure of the input circuit and the functionality in the output circuit is diffused. um which you know intuitively means that the fun the functionality is spread out throughout the circuit. It doesn't remains concentrated at the gates. So what happened? Well the structure of the output circuit was significantly different which is a good news but the functionality remained concentrated uh the functionality did not diffuse and this is evident by what we some what we call the heat maps. Um I would not tell you more about heat maps because it's

going to take time. So uh but you know whenever there's function whenever there is where when the function functionality is concentrated you get a big huge red line on the heat maps. Um so why did it remain concentrated? Well, um hm you know if you look notice the uh if you look at the replacement procedure that we did at the needing and inflationary stage the input and the output to the window which is being replaced remained the same. We did not change that at all which basically means that the functionality never got a chance to change. And we'll tackle this problem a bit later. Um, but one might

ask whether database mixing is enough. Database mixing basically is the name that I use for the two-step procedure that is described. Um, we don't know. We don't we don't have a justification either way. Maybe more rounds or like a stronger rainbow table would uh would um h you know have it work. But we still don't know whether why why database mixing is not enough. Okay. So the solution to the problem that we came across before gadgetization gadgetization has the following goal. It basically mask the value wires and then have compute on the masked wires.

For example, here's a single gate circuit to gazitize. You first add bandwires. So you take the circuit, add bandwires. What are bandwires? bandwires basically compute carry a lot of junk as a function of the input and then you take these bandwires and mask the original computing wires which are the value wires. So now you have masked the value wires. Um so once you mass them the functionality has changed because these are just random junks now which is why you have to add more gates to compute the same functionality as the original

gate and I'm not going to go into the equation of these gates um there are several ways to do it. This is just one way to do it. So what you would notice is that we masked the original wires and then add a bunch of mo new more gates that would compute the same functionality as the original circuit and then if you have many gate circuit you just repeat this caseriz procedure for each gate. Now observe that in caserization if you do not have access to the bandwires like let's just you know blackbox the bandwires and you only look at the value wires it's complete junk like you cannot observe anything from the value wires

um and it not just only diffuses the functionality like it's just complete junk um and I like to call this pro I like to call this changing the algebraic structure of of of the circuit because if you were to take compute the algebraic polinom sorry uh if you were to compute the polinomials of the wires um you would see that the uh polomials are completely random. So um but caserization is not enough because in offcation you're supposed to publish the circuit and give it to anyone else and if once you give to some circuit to someone else they would be able to see what the bandwires are. So you know that's not enough. So offsc uh

sorry gadgetization in itself does not hide anything. So now coming to the new method. Okay. So what do we know? We know that gadgetization randomizes functionality. Um right it changes the algebraic structure. We know that database mixing erases the structure to certain extent. So the new method combines the two. New method has the following four steps. First gadgetize the circuit. Second, database mix. Third, crosswalking and trace eraser, which I'll get to. We've already covered gazard the circuit. Um, we'll cover database mixing again, crosswalking, crosswalking, and trace eraser.

So, in this slightly modified data mixing, um, in each round, we either uh compute we either do a mix round or a compressed round at random. In a mix round you sample a subcircuit of roughly around six six gates and replace it with either a smaller equal or a larger subcircuit. Um think of mix round doing a combination of the inflationary stage and the needing stage. And the compress round you take a large subcircuit and replace with a smaller one. So you're explicitly compressing.

Crosswalking. Well, in crosswalking, you sample a random gate and push it as far as possible until it collides with another gate. So, this particular uh this diagram in the middle is a diagram of a colliding pair. The one above is a non-oliding pair. Colliding pair is not commutable. You cannot commute them. You cannot swap them. Now uh when you make a gate go through the colliding uh gate uh you change the functionality of the circuit because you've you know commuted a non-committed uh non-committing gate pair. Um so you fix the functionality by adding residual

gates and the reason we call them residual gates is because we think of it as a collision and once the collision happens you get a residual. So you fix the functionality by adding residual gate and that's it. Um why is crosswalking important? Well, crosswalking changes the structure of the circuit way beyond what database mixing could change because database missing restricts itself to a convex subcircuit whereas crosswalking pushes the gate beyond its convex boundary. Trace eraser. Well, trace eraser has a very is a very simple idea where we want to erase the entire um history of the procedure. Simple as that. We want to erase, you know, whatever information of

the procedure exists in the output circuit. How do you do that? Well, a simple way to do that is that you compute the polinomials of each of the wires, get rid of the circuit and reynthesize the circuit from scratch. Um, and following is a very simple procedure to do that. But there are various kinds of other procedure to do that. Um, and that's it. That's the new method. Um and what's next? Um well in terms of security we tried of all kinds of human expertise. Um you know also using you know all kinds of artificial expertise like clouds various kind of s solvers and nothing has you know baited so far

and there no bro there no breaks yet. Um and um we are in the process of preparing a documentation uh and we'll be releasing the documentation soon. The documentation would have challenges which is a good spot for someone who's interested in offiscation to participate and if you break any of the challenges then you know you're directly attacking on a scheme and that's good to do. Um here's the source code of the local mixing repository. Um that's the website where we will upload upload the documentation in a week or two. Um and if you if you guys want to reach out then you can reach out to to me directly or on Google group or GitHub. Um okay so

now I'll go to the part two of of this presentation which is going to be very short. Um so in this part two I'm going to talk about two things. Why work on offiscation and why local missing is useful beyond offiscation. Okay. So on the right on on the left um I have this you know really nice u graph that sort of uh compares various private computational technologies like FG T threshold FG FG snark and IO. IO is impractical which is why it has a dotted circle right there. The circle sort of represent their you know relative overhead. For example, FH has overhead of 10 ^ 7 or you know one would call it

10^ 6 whatever that is. um uh sorry FG plus pern thresh FG has um overhead of 10^ 4 um and snark you know roughly has overhead of you know 10 ^ 2 or 10^ 3 um and all I'm trying to say is that you know snarks went from Pinocchio which was a roughly you know I don't know like back in 2013 around 10^ 6 over at to today where we approving you know Ethereum blocks in in real time and like a few days back we learned that Now you can run a 400 billion parameter um in in LLM and prove it with just you know roughly 75 to 80x overhead. So that's that's good news. Um FH went from you

know back in 2011 um 2011 was it? Yeah 2011. Yeah. Um 2011 um uh where computing and gate took 30 minutes. Um now you know you can compute many many and gates and do many many bootstrappings many thousands of bootstrapping um within within a second. Um but but what what happened for offiscation? Well um the only provable construction for offiscation appeared in 20 2020. Um, and I understand the problem is hard, but to me, obscation seems a bit of an anomaly in this world.

And I think we should fix that. And I think that attempts like, you know, local mixing, attempts like diamond.io and among others are are are trying to fix it. And I think in this world today we have many reasons to be optimistic the offiscation because you know a lot of our research has been already spread up by um at least in local mixing by by um LMS and other other types of artificial intelligence. Um okay so local mixing um so okay uh the second point I wanted to make is that local mixing is is not just uh for offscation but you can think of it as a new primitive uh it is useful beyond

obscation. Um my claim is that with local mixing you can construct all kinds of uh various um um cryptographic primitives like public key encryption, fun functional encryption, FG and of course offiscation and um and the most crucial of this technology is public key encryption. So if in a world um if you live in a world where there exists a quantum algorithm for lises um and other codebased primitives then um we should try to find alternative alternative candidates and local mixing is one of those candidates and uh given the progress in AI I I don't think that this world is that improbable.

So yeah that's it. Thank you. Wow, that was really interesting. Uh went over my head honestly on some of these things, but we have some questions. Um so the first question that has the most up votes here is how does how does obuscation differ from functional encryption? >> H so offiscation takes a program. So functional encryption has a um functional encryption does not hide the circuit or the program whereas off sketch does.

>> Okay. Um another question that we have is how does local mixing differ or is better than other attempts at IO? Um I I'm I'm not making a claim that local mixing is better in any sense than attempts at IO. It's just the path that my research group has taken. Um it differs from other other attempts from IO in the sense that local mixing is uh completely foreign to uh many of the things that are done in the past cryptography world whereas other approaches are trying to build on existing cryptographic primitives.

Another thing that I was like wondering this is also a question that's here is um like how is this like is this postquantum secure like um just talk about that a little bit. So, so far we have no reason to believe that uh this is not postcon secure like of course you know someone would come with the reason tomorrow and be like okay yeah >> another thing that I was just like wondering when I was as I was listening to this is like have you done any work on like formally verifying any of this logic? No, no. Uh, well, it's a it's a it's a theoretical construction right now. Well, not theoretical in the sense like we have an implementation of it.

We've not done any formal verification of it today. Like we we don't know how to do it. >> Nice. Um, and like I this is a very new concept for me honestly like IO and like I Yeah. So like what what would be like something like a practical application that you could build with IO? Um I think one practical application that I can assume everyone would be familiar with is encrypted smart contracts. So you can have smart contracts where you can hide secret keys and no one can learn what those secret keys are. So you can have a smart contract that can sign on your behalf based on something or or you can have encrypted smart contract with encrypted states um that you cannot look inside.

>> Okay, cool. So yeah, it's super exciting like and we have some more questions here. uh what is the overhead because like it seems like there's when you're actually doing this computation in this op obuscated state like it seems like it's a massive overhead like could you just talk a little bit more about the overhead >> um well so far um so there are two kinds of overhead uh first is like conversion from boolean circuits to reversible circuits and there's the override of the offiscation procedure in the reversible on itself when you convert a boolean circuit to reversible that's a large blow up The the problem with that approach is that I don't think we should take that approach. We should try to build circuits within the reversible land. And within the reversible land,

the blow up remains roughly I don't know 10^ 4 10^ 3 or even like could be 10^ 5 if something goes wrong. Um and I'm hopeful that over time one would be able to bring that down. >> Also like looking at those heat maps uh that you had like someone's asking uh what does the heat map look like for your final result? They look good but I I think that we passed the stage where I would trust heat maps. Uh so which is why I did not have more heat maps in my presentation but I'm past I think we passed the stage.

>> Another question is really interesting. Do you do you need special hardware to run local mixing? I know for like uh there's certain special specialized hardware for other types of cryptography and like >> would you need specialized hardware for this? Uh so if you go on phantom zone repository there is a hardware implementation of local mixing um in FPGA um but we didn't pursue that part further because previously we thought that we have to do a lot of gates but I don't think that's true today >> and nice and for the final question um what potential capabilities excite you the most uh like and when IO is actually achieved >> um okay so you I I I like u I I I I I

think that uh encrypted smart contexts are a good application but the one the most that the ones that excite me the most is trying to build this um are you familiar with the concept of blackbox computer like on an encrypted computer that just excites me the most uh building the I don't know if you're familiar with the gods protocol or you know this um yeah impartial it that sort of works Then we go swim. [music] >> [music]