Episode 384 - The Quest for Practical iO with Machina iO

Transcript

Welcome to Zero Knowledge. I'm your host, Anna Rose. In this podcast, we will be exploring the latest in zero knowledge research and the decentralized web, as well as new paradigms that promise to change the way we interact and transact online. This week, Tun and I chat with Sora and Enrico from Machina IO, a team within the Ethereum Foundation. In this episode, we explore the details of their IO implementation work. IO stands for indistinguishability obfiscation. It's a type of program obiscation where for any two equivalent programs, once obfiscated

would seem the same. They would be indistinguishable from one another. It's very much in the realm of theoretical cryptography today, but as we learn in this episode, Machina is attempting to do some of the early implementation work around this technology. This is our second episode on the topic of IO and for a full explanation of what IO is. I would recommend listening to the episode with Rachel Lynn. In that episode, we go over what are the theoretical primitives, what are the assumptions, what is the state-of-the-art, what have they tried and decided to move away from, what are they actually moving towards, and I think it gives a more comprehensive definition of what IO is.

I'll add the link in the show notes to this. In this episode, we dive quite deep into the challenges and opportunities of this cutting edge privacy cryptography. Our takeaway remains that IO is still far from truly practical. However, as with these frontier technologies, having both attempts at implementation alongside the theory can offer interesting insights into how this actually works. Now, before we kick off, I just want to share that we've launched season 3 of the ZK whiteboard sessions. The ZK whiteboard sessions are produced by ZK Hack in collaboration with Bane Capital Crypto.

This series goes deep on some of the key concepts in ZK. I've added a link in the show notes. Be sure to check out these videos. They are a great way to learn about the fundamentals and techniques powering the ZK systems we often discuss on this show. Also, if you're looking to jump into ZK professionally or just looking for a new role, I wanted to point you towards the ZK jobs board. There you can find job postings from top teams working in ZK. And if you're a team looking to hire, you can also post your job there today. We've heard great things from teams who found their perfect hire through this platform, and we hope it can help you as well. Find out more over at jobsboard.zeronowledge.fm.

You can find this on our website and I've added it to the show notes. Now, here is our episode with Sora and Enrico from Machina I.O. Today, Tun and I are here with Sora and Enrio from Machina IO, a team within the Ethereum Foundation. Welcome to the show, Sora and Enrico. >> Hi, everyone. Thank you for inviting us to this podcast. Thanks uh thanks Hannah for having us. >> Cool. Hey Tun, how are you? >> Good.

>> Excited to jump back into IO? >> Well, yeah, somehow I don't know how I became the person who's the co-host on all the IO episodes, but I guess that's that's that's somehow what's happened. >> Nice. Yeah. So, a few months ago, Tun, you and I spoke with Rachel Lynn from University of Washington and in that we discussed the state of like theoretical IO. It was like one of my favorite episodes of the year, I think. I think I can say that now. IO had been teased on the show for years, but that that was the first episode where we actually jumped into it. And in that episode, we discussed how like she and her colleagues had in 2021 proved that IO was at least theoretically possible if it was built on wellfounded assumptions,

which they kind of proved in their paper. I very much recommend listening to that one to the audience if you haven't already heard it. Today, I feel like we're switching more into the realm of practical IO, but I'm putting practical in quotes here because as far as I understand, like IO isn't usable yet, but I know that's what you guys have been trying to do. So, I'm very excited to hear Yeah. how how it's going, how far you've gotten, like what you think is possible, what still needs to be figured out. Yeah. I'm very excited to learn more.

>> Yeah. Okay. Okay. So like uh like I think as far as I know we know or most of the I all of the IO construction we know or including ours is still far from practical or so for example even overcing some socket with like a just four input bits still takes more than like 6 hours however I don't feel or we are still in the like a dark forest of the practical a rather than that we found or some of the long path concrete path toward practical IO and uh yeah we see practical IO as a complete technical challenge rather than some like a missile like a dream.

>> Okay, I would love to get to know both of you before we jump into Machina and the project. So why don't we start with you Sora tell us a bit about what got you excited about IO. Yeah. When did you start working on this? Were you working on something else before? Like have you ever done ZK or >> Yeah. Yeah. So like uh our my story with IO stat from 2021. So exactly from the paper from our professor Ash or Rachel and or Mr. Hai about the IO construction from standard way from our assumptions.

>> Yeah. >> So it start from the uh wired article my a friend of mine shared with me and this articles was about exactly about the this like a paper of IO from standard assumptions. Wait, this was like a wired article. Is that what you just said? >> Yeah. So like after this paper was published, I think like they wired picked it up. >> Yeah. they becomes the wired article and I led that paper and this was the first time for me to uh know the concept of the IR and at that time I have already worked on some blockchain technologies and uh some like ZKP application developments and I know some of the concept of using cryptography for smart contracts like using MPC or FG but like

uh I feel like if we use such MPC or FG this decrease place the security of or smart contract applications because you additionally need to write on some like ad hoc or threshold committees >> but like uh so that's like uh when I learned the concept of IO I was really surprised and fascinated by IO because it was an ideal solution for enabling smart contracts to process some secrets such that no human can or a learn but anyone can use in some predefined logics. So, it's almost like it's the optimal. It's like if it worked, it would be amazing. There would be so much potential. It would actually like do a

lot of the things that ZK and FH promised to do, but in better form. But I mean, did you learn quickly that like it's still a ways off like >> Yeah, of course. Yes. But like uh when I read that article I yeah I was really surprised because this universe allows the existence of such secure IO construction and uh I thought like uh I found like a new kind of dream complete dream and uh or goal or to achieve which is like big enough and uh difficult enough. So this is like how I first like uh meet.

>> Nice. So I'd also like to hear from you Enrico. What's your story? What got you excited about this? >> Yeah, I think uh in my case I I came to know IO more recently. So I think it was around like u one year and a half ago, two years ago. And at the time I was working on a on an application like I was writing a paper related to multilateral um credit setup which is a very practical application in which you have an agency that is collecting uh invoices and IUS from different businesses different companies and >> they kind of create a network of IUS after collecting this information and

>> and you're saying I use here not IO yeah no Nothing to do with IO at this point. >> I owe you as in like credit. >> Yes. Yes. Yeah. Exactly. I I owe you. Got it. >> And since the this agency, this single party is able to construct this network, they can then identify cycles of debit and credit and they can cancel them out from this network and this yields some liquidity saving for the company. So I think it was a very compelling application for for privacy because I thought that if if companies would be basically guaranteed that their personal information wouldn't be revealed to this agency, they would be more encouraged to submit their invoices and therefore this

would yield bigger liquidity savings for the whole system. And uh I started looking into technology to enable that. And uh for example I was working with FHE but I I soon realized that if you want to use FHE you need somehow to you cannot distribute the trust across the whole firms because uh let's say you have like thousands of firms >> you might end up with a very kind of weak system in which just a a single firm dropping off the whole process will kind of destroy everything. So what what we ended up doing in this paper was just which is kind of what happens in most of production ready application today is

like >> they kind of delegate the security of u the f the security of the decryption key to a committee to a very small committee that is kind of trusted to not collude to not to not misbehave I wasn't kind of satisfied by this solution and this is actually when I I already knew knew that Sora was was kind of interested in this in this IO thing even without fully working on that. But um >> we we we decided to undergo this challenge last year. I think it was exactly one year ago at at Defcon and for me it was more to kind of a frustration from an application developer point of view. But it's weird

because you were like experimenting with FHE which is also not quite practical and instead of going backwards to the things the libraries that exist you went further. >> Yeah. Yeah. I think it was too practical for me so it wasn't satisfying. >> Okay. So, Machina, I've sort of said this in the intro that it's a team within the Ethereum Foundation, but like were you both working already at the Ethereum Foundation and then you sort of formed this I don't know subcom I don't know what it is exactly but yeah tell us a little bit about how what the connection point is there and yeah what Machina is >> yeah so like our magnet IO is like a team or like a project within PSC of the Ethereum Foundation and we have like

worked on PSC even before forming this magnet IO project. So like uh yeah, this is a exactly project we started to research a practical IO. >> Yeah. But I I was kind of curious like why IO why Ethereum like is is Ethereum is it in the road map? Is it part of the plan to explore this stuff or is it more just like experimental? You had the green field and so you you decided to to explore this. >> Yeah. So I think this is more kind of like a experimental things and uh of course like uh IO is not in the offshore like a road map published by ES foundation because IO is still not yet practical but I think IO is aligned with

like a especially the privacy goal of the E3 foundation E3M >> and uh this is because when we want to protect privacy of applications which inverse matchable practice secrets data such as like a private form of the DEX or like yeah some kind of like a mixing applications with like a enhanced security or like a crosschain bleach with bitcoins uh they need to write so they cannot be implemented only using zk but in this case without IO we have to write on either like MPC or TE or like a F mult key F and so on. What do you mean like you if you have IO if you want to work with IO you're actually using these

other tech stacks? >> Yeah. Yeah. So like uh if we have IO like we can uh use IO to to protect our data such that no one should not be able to know. So for example >> uh if you want to build uh some bridge crosschain bridge systems with bitcoins like we need some system such that this systems uses some bitcoin private key no one knows uh for like a signing transaction to withdraw bitcoin if and only if a user bs the corresponding wrapped bitcoin or is blockchain. But to like manage such private key and use it only for some like a valid cases we usually need to write on some NPC or

threshold signature or T is but if we have IO we can just makes one obiscated program which hand codes this bitcoin private key and if anywhere like anywhere inputs some zip proof to say your my like my wrapped bitcoin is honestly like banned on ean blockchain with some like test consensus then this oriscated circuit will output the signature to withdraw bitcoin for your address. >> Are you talking about replacing existing zk systems and architectures or are you saying you're adding IO to some sort of architecture? Yeah, I think this will replace some of the systems based on like NPC or like a threshold based

cryptography such as uh threshold signature NPC and so on or maybe some of the T based applications. >> Your research is about replacing it. It's not about like working with it. I I think actually this is something that we've been uh discussing very recently that I think we fit very well with for example existing FHE application and especially for example I know that you guys at Zama people as a guest of the podcast you know that they are building this FHE VM which is basically an equivalent VM in which all the smart contract states are encrypted under FHE >> and In this uh scenario, I think we can

kind of plug into this FHEVM and uh only replace the decryption part actually making the decryption part more secure. So the old uh FHEVM let's say the onchain logic of an H FHVM remain the same but the thing that we can actually provide as a as an add-on with IO is actually replacing their current system that is handling the decryption part which uh similar to what I I was describing before is uh relying on a committee of people which can always kind of I don't know just decide not to cooperate or even worse behave maliciously and we kind We can kind of uh embed this conditional decryption

logic inside an offuscated program such that once offuscated this can be just released in the public and uh everyone can consume this everyone can use this program everyone can pass cipher text to this program and uh if they are are allowed to obtain plain text as a result but the point is that for this decryption process there's no longer the reliance on the on the committee members. So I think this actually kind of fits very nicely with some existing architectures.

>> So in summary like we can say IO will replace the trust assumption in particular special assumptions from the existing cryptography based applications but at the same time or IO will be like used or combined with the other cryptographic techniques including ZKP and FG. >> Got it. Maybe an place to kind of go more into like the technical details. I think like if you think about the the original construction that we talked about during the ritual in episode, right, where you have this circuit and you divide it into a public and private bit and then the private bit is very low degree quadratic and then the public bit but but potentially large but still low degree and then the public bit is

unbounded degree. and you kind of separate the calculations with this sort of projecting back into the the secret space. Obviously, that is very cool, but obviously there's all this this kind of like exponential space blow up that can happen as you're doing the the computation. To make things practical, of course, you have to effectively choose a different set of assumptions that underly the security, right? like instead of kind of relying on PRG and degree 2 and and things like that, you have to rely on something that's more like linear algebra in LWE. So maybe I guess let's talk about the assumptions you know you're you're making here you know why why LWE why ring LWE obviously that shows up in FHE as well

but just sort of just to get an idea of like you know why did you choose the assumptions you chose and then then let's talk about like how those enable you to to get something more practical a and before we describe the IO just more like the the core assumptions you make how those assumptions differ from sort of the theoretical constructions and what those buy sometimes from these papers where it's like there's a thing that uses very simple assumptions but like impossible to construct in practice and there's a practical thing that makes a different assumption which is not equivalent in many cases but like seems like it should be equivalent and in the sense that we don't know of any poly time reduction

but yeah just would would love to kind of go down that path with you guys. So first of all like our IO construction on only latis assumptions but not only standard RW assumptions but also some uh two non-standard assumption and one of which is actually new new assumption we we repurpose we introduced for our IO construction called all product LWE >> all product LWE. So like uh this is our product because we consider a variance of the our LWE or instances for corresponding to like all of the like input patterns. So like uh if you have like a three input bits like we have or

three input bit or we have like a two power three equal eight like a patterns of the input bits and uh we define adree kind of different but valant of the LW instances corresponding to each input bit. So in total like 8 bit if we have three bits and uh our assumption claims that even if we reduce the adree such kind of adree instances for all of the product patterns >> all products okay >> all of these like instances remain through them >> and there's no kind of ration which blacks the security of such instances >> but you are creating your own assumptions here so you are deferring from the initial at least for sure the

2021 work. Are you taking any of their assumptions along with you in these implementations though? >> From 2021 paper, we only took standard LW assumption. >> Okay. And then you added this all product LWE assumption. >> Yes. And also uh we have also used one more nonlinear uh non-standard assumption called evasive LW assumption. >> Evasive. Okay. >> Yeah. Actually this is also like super strong assumption and uh I think in the last Richard I think she mentioned new assumption as a assumption with hint and she said like recently some counter examples against this assumptions have

been proposed and this debris is ex is actually one of the such assumptions >> evasive LWA but was that is that something that existed outside of this and you've found you've kind of brought it in Iversible is a like a kind of new new assumption like this this has been introduced from like 2022 and this has been used in many of the lattis best construction and we also use that assumption but in I think in the beginning of this year just like right before and after we published the diamond io paper I think the other four papers uh which has proposed counter examples against this event where the venture Oh no. So what did was it like

you released some work and then it got broke right away? >> Actually this is slightly like a situation is slightly different from like a usual assumptions because in like a most of the assumptions treat graphic assumptions like these assumptions are like a first fireable which means if you provide some counter examples like this assumption is basically completely broken. But in the case of invisible ad you can consider like a many valance of this assumption because it's has a lot of like a valance of the like a sampler definition used in the definition of the assumption and this attacking paper like a proposes just a counter example of

some specific samplers. So this does not mean this assumption does not fall or for all of the cases. I see I see. So, we are still not sure if our use of the assumption is secure or not. >> But it does sound like you are you guys are building on to use Rachel Lynn's metaphor like moving lava. >> Yeah. >> That like may or may not hold. >> Yeah. Yeah. Yeah. Yeah. You go through. Yeah. >> Got it. Terrone, your question I feel like was broader though. I know we just kind of dug into the actual assumptions here. So, >> yeah. To maybe give a little background, learning with errors, right, is like I take a a plain text, I embed it into a lattice with the cipher text, I add some error and the goal is that like, hey,

this linear system like the generator matrix is not easy to invert. So by adding the error it becomes too hard to exactly invert and like the hope is that I can add a small small amount of error small in the sense of the noise or the magnitude and also in the support like the number of coordinates I have to add you know and and one reason that's very appealing right is linear algebra is something we know how to do very easily and do it efficiently everywhere. So for FHE, you know, no stock LWE is like more or less sufficient to get pretty far. But for IO, you have to really deal with this idea that at each step, your LWE assumption is sort of implicitly leaking something about the circuit you're

using. It's sort of like there's some correlation between like the way you're constructing the generator matrix and the the circuit. And so you have to like keep refreshing. And that refreshing is very slow or expensive. Again, this isn't my heristic explanation, so you guys can correct me if I'm I'm wrong. It's like just like I'm trying to simplify as much as I can of what I understand of of this. So, so you have to keep refreshing and that refreshing is expensive, right? And so you need to find some other shortcut where it's like I can apply another LWE like transformation another projection maybe to a different lattice whatever maybe with different error but something where it looks like it's matrix multiplication but such that I hope that the matrix multiplication like whitens or like you

know adds so much noise to the circuit definition >> without removing the effect of the circuit computation. And so somehow this all product assumption and the evasive assumption effectively do that right like the hint is sort of a trapdoor to allow you to you know kind of like in in FHE where you you know you project and then d noiseise and you can only dn noiseise if you have the secret key there's sort of some sense in which the hint lets you dn noiseise the real answer if you knew enough information right so maybe walk us through those assumptions how do they map to that again I I tried to simplify it a lot I know it probably misses a lot of the the nuance But yeah, just like walk us through that just like why do you need these assumptions like you know there's a

sense in which there's a gap between FH and IO right that very non-trivial from a complexity theory standpoint but somehow that also maps into this assumption space and so I slightly changed my question but I think hopefully that gives a little more context into it. >> Okay so like your question is like how each assumption is like necessary and important in the IO constructions right? Yeah, I I think I I just wanted to you know I think one really big difference right between FHEA and IO from just like the the standpoint of a user is the circuit has to get obuscated. So but somehow that the normal LW is not sufficient. So why do I need these extra assumptions?

>> I see I see. So basically as you said we need new assumption because while we want to hide most of the secrets about the offiscated circuit we also need to reduce the or only the socket output as a plain text in a no interactive way. So that we have to prepare some like a hints which reveals such corresponding output and we we need new assumption to say that this hint does not reveal information beyond what we want to actually reveal to the evaluator of the overkated circuit. For example, we need BB assumption because yeah BB provides some kind of similar role as a P link but it's not necessarily restricted to

the just a digly to multiplication and some like constraints because like this plays a similar role to the palings but it's not restricted to digly to multiplication like a similar technique or so like a key building block for regarding this evasive ad reassumpion. is a latis trap door. So if you have some like a instance which encodes some like a secret and some like secret data and if you have like a play image which also encodes another secret or you can do multiplication between them and this makes another LB instances which encodes some like a product of these two secrets and you can do the similar things

multiple time. So this like a plage latis plage it was originally proposed to make the kind of material maps but finally people found marinia maps or for general use cases based on such techniques are insecure but if this better be rule ads are similar use cases of such play image let's spray image multiplications which allows the same type of the attacks against meium apps in particular if the products remains sandum for adversaries. This assumption says these like prime images will not reduce the intent of secrets and it only reviews the sandom value obtained by

merge applications. I think we we rely on a different line of work compared to the 2021 paper that uh Richard Le talked about in the in the previous episode. And uh I think the the core of our construction of IO relies on a paper that was published in October last year which is called compact pod random functional encryption authors aky and uh basically this this paper proposes a new more algebraic construction of functional encryption. This is also where the evasive VW assumption comes from. And in our work in the diamond IO paper that we published earlier this

year, we kind of add let's say an additional component to this AKY 24 paper in which we allow basically a user an evaluator let's say a consumer of this offcated program to dynamically add their input bits. And this is where the old product LWE assumption that Sora was describing comes into place. So we are more let's say on a on a different line of work. >> Tin did that answer your question? >> Yeah I mean it kind of gets at this but I guess the the real question is just more like why should I kind of trust that these assumptions will be equivalent or like at least give me like some comparable amount of of security. I

think like the other thing I'm a little bit and maybe this is actually worth going from now the assumption to the implementation is you know I think of a lot of LWE things and it's like I do a single matrix multiplication I guess cipher text and then I do apply the circuit and then I project back for you know FHE but then for IO I do something sort of different where I embed the cipher text and then I look at the difference between the cipher text and the true circuit evaluation and then project that again. And I that naturally sort of seems like why you would need this all product thing, right? Cuz I'm doing two nested LWS. I'm doing an LWE on the raw input and I'm doing LW on the difference between the cipher text and

the sum embedding and the true value. Maybe let's talk through if it's sort of these types of matrix multiplications, why are they so large for a particular circuit? Where does it blow up? Like you know, is it like nested multiplications blow up really quickly? Is it actually the fact that addition and multiplication blow up the polomial degree in some more nuanced way? Like what like what what makes it really large? Like what makes these matrices large? What makes it kind of slow? And we we'll talk about optimizations next, but yeah, just maybe why does it have this reputation of being such a a large kind of program for small circuits?

Basically the main bottleneck we have is that like when you have like a larger input size you need to prepare more matrices as radishes and you need like a more number of the matrix multiplication to insert each input bit and uh this binary like blew up the like accumulated error size because like initial error is merged by this matrix so that the size of the error increase but at the same time we need to ensure that the modress of the matrix is like a sufficiently larger than this like maximum bound of the error. So like uh finally like if we have more input size like we need more modress and since modress is large each

of the matrix size also increases by the increase of this modress. This is like a main reason that why like arbitration size matrix size increases so quickly even for simple functions. everything we're talking about, is it completely theoretical and you guys are making kind of toy implementations, but it's so unusable at this point or do you actually see like a glimmer in what you're doing that it could potentially be used? >> Yeah. So, I actually have um in front of me our benchmark results that we shared uh earlier this year based on this uh diamond IO paper that we published. And uh yeah I think we can definitely say

that this is not practical and this is not usable. So we have a for example >> as Sora was mentioning we think in terms of like input bit size because our construction is basically what allows users allows evaluator. So again let's go back maybe make a step back and when we talk about offuscation we always have these two different phases. One is the offuscation phase in which basically the compiler phase in which you take a program you you pass it through this compiler and you you then get the offiscated equivalent and then there's evaluation phase in which users like a consumer of an application will pass their input into this offiscated program

and obtain an output without learning the inner working of this program. And uh this input size refers to the input size of of the evaluator. And uh for input size of just a few bits. So we test it with one two four bits. A program that is that is doing for example just a bunch of multiplication like uh the the size of the program is huge is around 50 GB and uh the offcation time for four bits for example is like over 300 minutes like 5 hours. Oh yeah. Yeah. So I'm not saying that this is a hint for practicality but I think one interesting observation that we see is that actually there's this huge asymmetry between uh the offuscation phase and the evaluation

phase. So the the offuscation phase for example in the case of the 4bit input size took around 5 hours but the evaluation took only let's say 18 minutes. So and the cool thing is that the offiscation is something that needs to be done only once. So we can potentially admit that this takes long time and what we really want to optimize for in order to make it practical is uh the evaluation phase. So I think yeah the the our implementation at least gave some some numbers. They put some some numbers into something that everyone says yeah it's very inefficient but they didn't have the numbers. So I think this

is a a good point to start and we also have a lot of idea and we also have a lot of let's say we have a rather clear road map in order to to make it practical. Actually, one kind of interesting question that maybe this brings up this like asymmetry is like you know I think about ZK how ZK went from like very impractical because like everyone wanted to you know until kind of like 2012 gentry paper like everyone was like we have to do a PCP versus like you know then people were like okay find a way to write the a constraint set that's small and then in that constraint set all the polinomials are small so then you can kind of like you know make optimize

things you know before we got to GR 16. It sort of seems like you need a step like that where you find some like lower dimensional reduction that like allows you to embed how you describe the circuit efficiently. But there's also a question of like pipelining like can I separate is there like any ability to parallelize some of the obfuscation versus evaluation components such that they can kind of like run in tandem. So I'm just kind of curious like what are kind of the optimizations you see that are possible and like which things are impossible which things would not work because I do think like that for ZK right it's like in theory people could have made really inefficient implementations of ZK in the '90s but then it just took kind of like 20 years

to find like the right representation such that things were small and then it was like off to the races towards optimization and that's not to take away from like all of the things like lookups and whatever that obviously made things faster but but I do really feel it was like changing how people thought about representing the circuit that changed things. So like how do you how do you foresee that for IO? How do you think about optimization and within IO? >> Okay. So I will take my my favorite let's say optimization potential but then I will also let Sora add his opinion like for me is actually I would make an analogy closer to like the FHE space rather than the the DK space which is when Gentry introduced the bootstrapping technique in FHE that

allow basically to let's say allow computation for like unbounded uh circuits and uh I think this is also the case for for IO or in general is not strictly for IO but is is more for let's say the underlying uh primitive that we're using for IO is something called BG encoding which actually one of the G is actually gentry and the B is damon >> and this was a a construction that was published over more than 10 years ago for attribute based encryption and is still the the main building block for this whole category of non-interactive cryptography that for example involves also witness encryption functional

encryption and IO and uh we actually need a way to do noise refreshing a sort of like a bootstrapping on this BG encoding that would allow similar to what Sora was mentioning before to increase the input bit size such that for example we add some input bits then we we the arrow blows up but we are able to do this noise refreshing to kind of move the error back to zero and keep doing it again without having to let's say allow from the very beginning uh this error space to handle this gigantic input size because this wouldn't be practical. So I think this is one one

way one promising optimization and we know that actually Richard Lynn published a paper last year on on bootstrapping which I think it proves a theoretical point that you can do bootstrapping on BG encoding but I think is not practical yet. So maybe we need a more practical uh way to do bootstrapping on BG encoding and I think this would kind of uh make uh bring us closer to to practicality. >> Actually I do think a kind of important part about at least what I understand of your construction is actually this encoding which seems like you take a bunch of small matrices to select which input bits are needed and then evaluate

then add noise. So maybe walk us through what the encoding is and like what the difficulties are because I do think there's some nuance to that that's unique to your construction that like you know the other IO papers don't maybe don't kind of cover as much. So it would be great to kind of understand how the selector matrices work. Yeah. >> Yeah. Yeah. So so like a sector means a section for each input bit, right? >> Yeah. I just mean like Yeah. the small Okay. >> Yeah. Yeah. Yeah. So like uh actually this is like new technique we introduced and uh the section means that uh so like so you can first imagine that like if we have encoding which impropers both of the encryption of the obiscated circuit

and your input bits you can do the similar technique to the functional encryption proposed in the compact random functional encryption paper to aate this private circuit on your input and only recovers the PR text of the socket output. And uh we use this section idea to insert our evalator's input bits to this like encoding which only contains the obiscated circuit. And this section means that you first have the encodings which does not have any of the input bits which contains only obscated circuit. But you can also access to the play mage matrix. Uh each of which correspond to like for example

you have two matrix for first input bit. One is corresponding to input bit zero and the second one is corresponding to input bit one. And if your first input bit is ziller, you choose the zilos one and merge by this matrix. Then like you can insert your input bit zeror to the given encoding. And uh skater provides such matrix for each input index. So that evalator will choose like one of the two matrices for each input index to insert each of the evolators input bit one by one. And finally they can obtain the encoding which contains both the ariscated circuit and all of the evaluators input bit. So one thing I

think I was kind of curious about is like the choice in which you know the permutation in which you evaluate the order of the input sequencing can change the embedding right but then you add this like gausian noise which is like invariant to the permutation. So like I'm kind of curious like is the ordering of the input bit constructions like part of the obuscation or does it actually not matter because like in distribution it's equivalent once you read add the noise at the end like cuz cuz that was sort of sort of my thing you know I think about a lot of like obuscation methods that are like draw a random secret permutation and permute right like is that involved in the security here or >> so in our case in our construction I don't think like we invert some of the

kind random pitition matrix because like this like selection part only depends on the ability input bit so we don't need to randomly like pate like such orders >> oh I see I see okay okay >> maybe you may think is like IO candidates proposed probably in like 201 like 15 or like 2018 like these things are like converts your socket to the blanching problem and which is like a parameation matrices Yeah, it's just a matrix. Yeah, I understand.

>> Yeah, I I I I sort of was reading this and thinking like Bington's ser theorem like that. Exactly that. And that was but because like you know when someone is introducing a new set of assumptions, right? It changes the tools you use to prove the same, you know, you have two different assumptions. You're trying to prove like basically a similar or same security property that like something isn't corruptible or or it's indistinguishable against other adversaries. So but like because you know there's like one set of proof techniques in the theoretical construction another set in the practical construction understanding where they are similar and different is kind of important. So that that's sort of the lens in which I'm asking this.

>> The high level idea of the security our security proof is that first when we use AW we have to prove that all patterns of the product between the AW instances and all of the provided lattice primaries remains random. And in your case, a part of the radis primage corresponds to the matrix which insert or some input bit each of the input bit and the secret corresponding to each input bit to the a given encoding. To prove that this like blemishes will not make our initial encoding are insecure the building some secret we consider two path like n ele instances such that we try all of the

multiplication patterns of the n ply images where n is the input size like we have to prove that like a combinations of the this all of the two part l instances remain summ and uh actually we finally need to write on our old product AW to finally claim that like these of the instances remains to London >> and uh the essence of the old product AW is that if we just use reuse the same secret but with changing some like a public bird it's easy to attack this this ad instances and easy to like distinguish between the two of the like ad instances with some like a random

ones. So the PL condition for EVP LB will not hold. But our assumption introduced in all product LB is that if we insert like input depend or secrets between the initial secret path and the public bird then like it might be possible to say like this like admin instances will be like a looks independent and slanton. So for example, let's say the initial secret is just S and we prepare some secret corresponding to the bit zero for the first input bit and bit one for the first input bit and also like a S and another like two secrets corresponding to zero and one

for second input bit and the public part will will be like a different for every input like 0 0 or 0 1 1 0 and one one and we will like review the encoding which depends on four patterns. So first pattern corresponding to input bits 00 will be will involve some common secret times secret for bit zero for at the first input bit and bit secret for bit 0 at the second input bit and the public matrix corresponding to 0 0. And we do the same things for 01 1 0 1. And we finally write on our assumption to say that all of these four patterns will be

slander. So that the play condition to use this ed assumption will hold. And finally we can say that the initial encoding along with this lot images each of which holds the like each of the secret piece of the secret will remain as London. I do think it's actually kind of it's interesting, right? Because like here you're you care about this like you know I I think like the oversimplified by a long shot and dumbest version of IO is like I take a boolean function that has some boolean expansion and then I take the set of circuits that describe that function up to some constraint and then I randomly sample one of those circuits and evaluate it partially. And that is sort of not at all obvious that

like the the sequence level thing is equivalent to that sort of like very high level view of like how people think of IO. So if we zoom out a little bit, I actually think another kind of important question, this is a question I think that's still open in every field from sort of like ZK all the way to AI in different ways, which is like what is the correct set of benchmarks for IO like what programs should we think about as like this is a good benchmark that we should be targeting, right? that like oh like given this benchmark as we do optimizations we're improving performance or whatever on that you know I think for for ZK like for better or worse in the beginning all the

benchmarks were this like Fibonacci stuff but then eventually once people had VMs they started like targeting real programs and you know for AI obviously they have like there's obviously all this fight over like what eval are correct so in a world where IO becomes fractical like what are the programs you think that are the benchmarks What are the benchmarks you're doing now? Like, you know, you talked about, you know, you gave wall clock times. Well, that had to have been for some circuit. So, like, what circuit were you using? And >> Yeah. Yeah. I think actually we have a a pretty clear answer to this because in this in this future there are I kind of hinted to before in which the whole uh application logic is run by an FH

process pro processor and only the the decryption logic the conditional decryption logic is is handled by an offuscated program. Well, in this world actually we only need to offiscate a single program and we only need to offiscate this program once and then this can handle all this private computation application forever. So really what we need to offiscate is not I think this is also a common misconception when it comes to IO that for each application that you want to let's say have some some privacy or you want to hide secrets you need to offocuscate a specific uh program but actually what and this is also another

paper from Gentry GGH13 in which introduced this concept of uh maybe didn't call it this way but we call it like universal IO. So as long as we are able to offuscate this program, we can kind of handle the security of any type of application really. And the logic of this program is is as follows. So it should take as input a snark a proof together with with a cipher text and there's some verification logic that is uh encoded in the offuscated program that will let's say in a kind of a very simple words saying am I allowed to decrypt this this cipher text and this will be based for example on some

onchain smart contract logic and uh if the verification passes the decryption proceeds. So it's like a I think we can simplify the program as snark verification plus FH decryption and uh as soon as we get to auscate this program we are basically let's say done >> you just have to do that. >> Yes. Yes. So I also have like another about how to benchmark IO for especially for more short time. So I think more concrete way to for benchmarks in short time is obscating your circuit with for example 32 input bits or more because if input bits is like a I think more than

16 or like 18 it's basically impossible in practice to prepare some like a function as a like a truth table. So like if we can make practical obiscation for input size like 30 32 bits this is like a non-trivial result such that we cannot do the same things without IO in a practical way unless uh P is equal to LV. >> Yeah. So actually that's a very salient point because like to me another kind of again I'm oversimplifying in all these descriptions but mainly just so cuz like I do think like IO if you haven't spent a lot of time trying to understand the assumptions can be kind of confusing is IO is very good at taking anything that has a really large gap between the

average case complexity of an instance and the worst case complexity of an instance and it makes everything the worst case complexity right so it's like take these SAT problems where like the worst case SAT problem is like very hard exponential time to find an answer. But the average case is like very low degree polinomial. IO in those problems has to convert the lowderee thing to like close to exponential or at least super polinomial, right? And so I guess the the natural question is like there are a bunch of problems like that that are natural. Well, the SAT is a little bit annoying probably I imagine as your benchmark, but you could imagine other benchmarks that are like the simplex algorithm like in optimization where like it's well known what the worst case instances are and you basically can run

like an average instance which is known to be fast versus the worst case instance and show that it's like the same sort of reduction. Another question that's sort of related to this is the power of IO and you know at least from my perspective is the fact that it's sort of universal in the sense that you can reduce it to if you have it as a black box you can like construct all the other cryptographic primitives you want functional encryption FHE ZK whatever right like all of them are sort of like you know this is the big boss and if you solve the big boss all of them are sort of corollaries without that much work right and so I'm curious how you think about bench benchmarking the reductions like you know if IOIO was sort of a universal computer you had a computer

that had a universal IO thing that was fast how do I benchmark how good the IO is on how well it does at implementing the reductions to these applications because I actually think like the reductions are in some sense the more practical use case right than raw IO itself or that was more a question sorry >> reduction means like reduction so like use using IO for more like simpler applications >> yeah yeah exactly like like all of kind of the known like hey these are known cryptographic applications that if you had IO's a blackbox you could implement quickly or like implement efficiently.

Yeah. Yeah. Yeah. Yeah. Yeah. I see. Yeah. Like like what are those best cuz I feel like those are like the practical applications that people want right to some extent. >> I see. So yeah, I understand like at least for cliptographers like this like a reduction to the like using IO as a blackbox to make like a simpler applications or like extend like a symmetric key encryption to public encryption can be like a like one good applications. But I'm not sure if this is like a how we eventually use IO for like a practical applications because yeah I believe even if we can make ZK or FG by IO like a direct construction of them should be more practical than IO

reduction and uh at the same time I think as an said we will use IO part only for some specific small parts like doing conditional decryption so that I'm not sure if like uh for example for measuring benchmark of like IO based FPG construction or IOB ZKP construction makes sense if our like a wide range of IO which also rely on ZK and FG is like used for this benchmark. >> I was just curious like have you tried implementing any of these reductions like >> no because we can at this time we can support only a few input bits.

>> Okay. Okay. Yeah. Yeah. Sure. I mean, I actually I'm curious like while you're writing the software here, like what gates do you use as your unit tests? Like what are your what are is it just like add and multiply for three bit integers or like are you like doing something you kind of curious like where do you start when you're doing a project like this? >> Yeah, I think like most of the circuits are really just for example multiplying a polomial by a secret bit. So we have a non polomial and our secret is either a zero bit or like a one bit and we want just to make sure that the output is is what we expect. So it's not really any meaningful program that we are testing

out but it's just some really dummy program that is testing out the the functionality that we describe in our paper. I think also something that is worth mentioning is that you know before I I refer to this BG encoding as the core building block for our construction and uh again we are not trying to reinvent the wheel here. There are like known libraries for example like open FH library which is a very popular C++ library already had all the primitives that we needed to handle this BG encoding and uh they tried in the past some some sort of let's say similar construction to IO and therefore that's

how they build this but it's also very similar to like what all the FH people all the let's say latis people are used are more familiar with so I think What we also want to convince people is that the the the jump from FHE to IO is not like a a huge jump like most of the idea the concept and the actual code that we are using is also shared across these two domains in like IO construction level we only evaluated some dummy circuits as allegory explained but after publishing our IO implementation like instead of focusing on directory or improving the efficiency of the our IO

consumption. We are focusing on improving the efficiency of this encoding layer because like this encoding has not been researched to make them really like practical >> in similar to ZKP or FG and they are like researched mainly in the theoretical area. So we have we first need to make this encoding practical and uh for this encoding layer we try to implement our FG evalation over encodings in particular doing some like multiplication some like nonlinear operation over like large modules and so on and we introduced lookup table repolation over this encoding to make them more practical but we still have

some challenges to make them completely efficient. Oh, interesting. You're actually using lookup tables. >> So, after making our IO implementation, we next like focused on like making a lookup table evolution over this encoding because when we see the like history of the ZKP or FG lookup table evolation or play the significant role to make them practical. So we considered if we can make the similar lookup native lookup evolation technique for this encoding so that we can do nonlinear operations more efficiently and uh we actually make such ideas and uh we confirmed the efficiency has been improved but we need more improvements

in the case of this business processings. >> I have a just a quick clarification question about something that was said like I don't know like 20 minutes ago. You mentioned the Gentry paper of 2012, Terrun. I think you had actually mentioned that. >> Oh, >> but I always think of Gentry as like FHE, but you used it in the context of ZK. So now I'm confused. >> A lot of ZK stuff like he's just done stuff and everything. So >> it is actually Gentry ZK. >> Yeah. Yeah. Yeah. There is an old paper of his that like arguably Groth 16 probably owes a lot of the original framing from like >> Groth 16 made this paper practical but he from a theoretical standpoint I think he figured out the right representation or encoding that like made it efficient.

So there's like but he's done something in everything. The best part about Gentry is he's uh he wasn't even like trying to be a cryptographer. He was like a lawyer for 10 years before. >> Amazing. Do you know his story? Yeah, his story is pretty crazy. >> We met at ZKS Summit 13. He popped over and I I definitely pitched him to come on the show and I hope I get to to invite him sometime. I think it would be a lot of fun to have him on. But yeah, I think his his background is amazing. But I actually didn't realize that. I always I always thought of him very much in the world. But that's cool. I do want to say one other thing before we sign off.

I just want to say a quick shout out to one of your colleagues, Pia Park, who kind of brought us together. I had reached out to her. She I think had published something through the Machina project and then she introduced me to the two of you. I'm just curious like what was her work there and just since since she did that intro? Yeah, actually we met with Pia at a residency that we did earlier this year in Taiwan and uh I actually already had a chance to work with Pia before because she audited one of the project that I was working on in the past and uh yeah it was very actually fun because probably in in two days I think I'm not wrong saying that like after 2 days that she spoke to us

for the first time and learn about IO she was already contributing to the to the repo. So we already had the probably she's still like the main contributor and she she was definitely like the the main driving force at the very early stage in which we were kind of building this from scratch and uh yeah I think actually all the result that we mentioned before are are really thank to Pia and her work on the engineering side and especially the the RS side of of our library.

>> Nice. How big is the group that's contributing actually? Is it two of you and then Pia was help was part of it or is it bigger than that? Is it open source and there's lots of people that are kind of adding? >> Yeah, I know I think so. The main the main group is me, Sora and and Pia. But uh I think a big shout out as I mentioned before is on the open FH guys which uh like our old library relies on and which we kind of let's say we we relied a lot on them on like trying to understand how this PG thing work and also on the optimization side but we're also very welcome to have uh new new contributors and we probably should also be more active on the on the

documentation and on the communication side to make it easier for other developers to to jump into that. But I think what I want to make sure that passes as a message from this podcast is that you know IO sounds this kind of a crazy thing that is inaccessible. But it's literally just you know a jump from what some something that already exists. So if you already have some uh some skill in uh in latises and in FH I think that the jump is not is not too long. you you will be very very equipped with everything you need to to start contributing and to start helping us optimizing this BGM coding that we spoke a lot about.

>> This is a very off like left field question but like you mentioned it sort of I mean you've said this throughout the episode that like lises are kind of at the heart of this. Does this make IO postquantum secure or is it like one part is lattises but actually there's all sorts of cryptography that could be broken. Yeah, I think as long as this as long as this security assumption that we added are secure and as long as the learning with our assumption is not broken, I think we can claim that IO is also quantum safe. Yes. >> Okay. I think I should mention that like at this time as far as we know like we only have like a IO construction from standard assumption which is not pro quantum because these kind of things all

of the standard assumption constructions right on balium splings but and there are many proposals of latis based IO constructions >> but like all of them are right on some kind of new latis assumption. So yeah, as Alico says, if these new radish assumptions are really like secure both against classical and quantum adversaries, we can say we will have eventually have post quantum eye or potentially >> sort of answer kind of sort of depending. Okay.

>> Yeah. Yeah. >> Got it. I want to say thank you to both of you for coming on sharing the story of Machina IO and your interest in IO, the work you're doing to implement it, where we're at in practical IO. Yeah, thanks so much. >> Yeah, thank you very much. >> Thanks. Thanks. Good to be here. Thanks for coming on. >> I want to say thank you to the podcast team, Rachel, Henrik, Tanya, and Hector, and to our listeners. Thanks for listening.