Episode 375 - Indistinguishability Obfuscation (iO) with Huijia (Rachel) Lin

Transcript

[Music] 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. [Music] This week, Terrun and I speak with Rachel Lynn, a professor at the University of Washington's Paul G. Allen School of Computer Science and Engineering. We discuss indistinguishability obfiscation or IO, often described as the holy grail of

cryptography. IO is a powerful primitive that if fully realized could have profound implications for privacy tech as a whole. Rachel helped break down the concept for listeners who may already be familiar with ZK, FHE, and TEES, clarifying how IO is different from those constructions, but also some of the similarities in the assumptions upon which these are based. Our conversation covers the history of IO research from the early works happening in 2013 to the key breakthrough that was described in a paper Rachel co-authored in 2021 with Jane and Sahai. The paper introduces a novel construction of IO built on wellfounded assumptions. We discuss the nuances of this paper and what's happened since 2021 in the field of IO

with the reemergence of IO constructions built on lises. Now before we start, I want to just let you know that we've just recently kicked off season 3 of the ZK whiteboard sessions. The first module came out yesterday and in it we covered one of the key components of many modern-day ZK systems that is hash functions. Our guest lecturer was JP Elmas, a previous guest of this show. ZK whiteboard sessions are produced by ZK hack in collaboration this season with Bane Capital Crypto. Every two weeks we have our hosts Nico and Guo going deep into the key concepts in ZK. I've added a link in the show notes. Please do check them out. These are a great resource to learn about the fundamentals and techniques powering the ZK systems

we often discuss on the show. Now, switching back to IO, here's our episode with Rachel Lynn. Today, Trun and I are here with Rachel Lynn, a professor at University of Washington in the Paul G. Allen School of Computer Science and Engineering. Welcome to the show, Rachel. >> Thank you. Nice to meet you, Anna and Toron. >> Hey, nice to meet you. And thanks to Mu for doing this intro. I feel like this is like the fourth or fifth time Mu has done a fantastic intro to a guest in the last like couple months. So I want to say thank you Mu for for bringing these wonderful people to >> us too from me.

>> Hey Trun. >> Hey excited to be back. Yeah, I feel like Tran, you were very excited about this one when we floated the idea of doing an episode on IO and specifically speaking to Rachel. But yeah, so I'm I'm just excited to have you here with me. Personally, IO indistinguishability, obiscation, the topic of this episode, it's something we've never covered in depth. I don't know if I fully know what it is. So, it will be I'll be definitely the beginner of the two of us getting into this topic, but I do feel like we've we've hinted at it or it's come up like in passing a couple times on the show. I'm very curious to hear like if it intersects with ZK and the things that we are like FHE, the things we

already talk about a lot on the show or if it's yeah, I don't know, pie in the sky, something coming up in the future. So, I think maybe we should start with just a very short definition. What is indistinguishability offiscation? We're going to be referring to this as IO going forward. So, what is IO? >> That's a very good question and I'm afraid that I have to tell you a story in order to end up being what is IO. >> Okay, perfect. >> I think maybe we can start somewhere back in time and also in terms of the development of this concept. I mean the first thing to ask is what is a fusgation, right? The indistinguishability of fusation has the

indistinguishability part and also the auscation part. The fusation part is this concept about can I have a compiler that turns clear text program a very complex software and then compile it into a new version. Think of it as a very very scrambled version. It is so scrambled to the point that even when you give it out, you release it to the public that nobody can actually understand what it is doing.

>> But it still works that you feed it an input, it will produce an output and the input output behavior is identical to the original version. >> So this is the basic concept of a fusation or program of fusation. Is this obfiscation done through because we hear about things similar to this like hashing or you add randomness or like what are you doing to create that obfiscation or that sort of like jumbled output >> that is a very grand question what makes >> sounds simple but might be complicated to answer >> I mean anybody I mean it's a very natural concept right in fact that in the software industry as soon as

software existed people were wondering about whether there are ways to scramble the software so that you can gobble as you say the internal working of the software so nobody can understand what's your secret source and people can have intuitions about how they might want to approach this and then the first thing they they might want to do is maybe I can give variables very difficult names to understand >> maybe I can insert a bunch of like no operations that were cancelled themselves out maybe I u do something else I initially that there's a lot of tricks one can play just with program programming techniques.

>> Mhm. >> And this was uh being investigated and explored. But the issue is that all these intuitive methods ends up to be deoffcated. They ends up to be easy to reverse engineer. >> Ah deobiscated too easily. >> Yes. So then cryptography comes into play because in cryptography that we want to build tools that are really bulletproof that we know as long as certain mathematical hard problems remain hard to solve that no one can violate the guarantee that we can prove based on their hardness. So the grand challenge question is that can we build

a program of fusation in a way that is based on solid foundations based on cryptographic hard problems that we have extensively studied and we know that they resist attacks. >> Cool. I want to just ask one more question about the name before we just switch into just saying IO. But when you say indistinguishability, obfiscation, isn't that kind of a double like isn't that saying the same thing twice? Because the offiscation I think we've made clear, but is is indistinguishable here? Like is is it meant in a very specific way?

>> It is certainly meant in a very specific way. And in fact, the indistinguishability of fusgation, this notion itself, this concept itself is a great contribution. And the notion of fusgation actually existed from the genesis of public key cryptography. Okay. >> So this notion was first mentioned in a paper in 1976 >> by authored by diffy and helman in the same paper where they proposed public key cryptography. And what's quite interesting is that when they proposed it, they named this notion called a one-way compiler. As I was telling you that you can think about fusgations of process of compiling program into something hard to understand.

>> So they call it a one-way compiler to indicate that this process is one way and hard to reverse. And funny enough is that back then we didn't believe they were still like the community was grappling about does public key cryptography even exist. It sounds so magical that you can have a public key >> and still encryption remain secure. So defend Helman justified that they argue that this concept should be feasible because if you hire a oneway compiler then all what you need to do is to take a secret key encryption scheme let's say your favorite one that we use AES today.

So now choose a random secret key and now we're going to just auscate the encryption algorithm of AES together with random this randomly chosen secret key >> after agation. Now this aascated program is going to serve as the public key. Why? Because you feed it any message you want to encrypt with some randomness. It's going to produce the cipher text. And because this random secret key is locked inside this offcated program that nobody can learn what it is.

>> Yeah. >> It's just interesting that the public key cryptography we then subsequently know that we can directly construct from a variety of hard problems. >> Yeah. >> But the challenge of fusation lasted for 40 plus years until only recently we managed to have some progress on it. So this indistinguishability is is that the new breakthrough? >> It is one of the breakthrough. Okay. It is one of the milestone because the first milestone is to know what are the security guarantees I can achieve and I cannot achieve. So what I have just described to you is a very easy mental model >> to think about what a fascation could possibly do which is that it's kind of

like a mathematical blackbox. Yeah. You put a program inside. Now you can call this blackbox anytime as you want and it doesn't leak anything about the software inside. >> Unfortunately this is ideal fusation. >> It turns out that this notion is impossible. >> Oh in general and this relates to the unlearnability in complexity theory that discovered around 2000. And then the question is like then what notion is it possible? Do we just give up fusation at all? M >> and then researchers proposed this new notion called indistinguishability of fusation. It's saying that it's not going to act like a mathematical

blackbox. But the formal guarantee is that if I started off with two different implementation of the same functionality then you cannot tell from the scrambled version which version one started with. >> I see that's the indistinguishability. You have these two that look identical. Exactly. Yeah. So if you started with two original program, they are different implementation of the same function, >> you will end up with something that are hard to tell apart.

>> Cool. >> So for for audience who are familiar with the zero knowledge language, I would say indistinguishability of fascation is kind of the analog of witness indistinguishable proofs whereas the original ideal of fascation is the analog of zero knowledge proofs. Interesting. Cool. >> I guess one interesting thing is like there's a lot of things that IO sort of implies like you get hardness of oneway functions. You get this kind of like average case NP problem to worst case NP problem reduction type of thing. It's it's like if you can achieve it, you can achieve all of these other things as a as a consequence. So it like has this little sort of holy grail theory of

everything type feeling to it because it's like you can derive a lot from it. So maybe it would be great to just talk about some of the primitives that you can derive from IO why it is sort of a little bit more powerful as a blackbox than some of the other things. And I think, you know, to your point about defining indistinguishability in terms of circuit representations, I guess being able to kind of compare why you needed to do things at the circuit representation level versus at sort of a tape level or as a function, you know, like like there is a sense in which I feel like the circuit aspect is important in the way it is in MPC and and ZK versus like other representations of of a state machine. So, sorry,

there's a lot of questions here. That is a lot of questions. Okay, we can we can deal with them one after another. >> Yeah, I think in terms of power of IO for sure. This is why that this fusation in general is such a fascinating concept. First of all that the ideal fusgation is so powerful. Let's to understand the power of IO. Let's first understand the power of ideal fusgation. Why do people want it? Why we have tried so hard for it? and what is it good for?

So I give you an example about how to use the mathematical blackbox to turn a secret key encryption scheme into a public key encryption scheme, >> right? Which is just to agate this encryption algorithm of the secret key encryption scheme with a random secret key >> and because it's now put in this mathematical blood box. So the secret key now is hidden and it's safe to just give give away this blood box. So essentially that it almost give you a software version of a trusted hardware. >> Oh yeah. Yeah.

>> Right. So any problem that you might hope to solve using a trusted hardware which is you have secrets that you want to protect but you also want to use the secrets through a limited interface or you have program that you want to make sure that the internal logic remains hidden. intuitive solution is put in the trusted hardware. Now cryptography is all about using mathematics to replace administration or replace hardware. So now we can wrap it inside the ideal fusation and that is going to be secure.

You can imagine I give you only the input output behavior. So that's why it's very easy to use like I would say that in the fields that crypto engineer or crypto researchers have a feasibility question that oh can I achieve this cryptographic goal they can first think about can I achieve it using secure hardware if they can achieve it using secure hardware likely that they can achieve using ideal fuscation not always but it approaches it yeah >> now we're we're going to ask what's the power of indistinguishable ability of fusation then it's it isn't ideal right ideal doesn't exist. So it turns out that thanks to a lot of techniques that

have developed in a large body of work something called a punctured program technique that was first introduced in a paper by Amed Shahai and Brent waters that with this technique in a lot of the ideal ofation applications we can actually replace this ideal fusation with IO. So that requires understanding of some cryptographic technique and there's another layer to answering this question which is that if we are comfortable with using huristics it turns out that this mathematical blackbox analog even though is impossible in general it is still

possible it's not ruled out completely. Okay. So there is a slightly weaker variant called the virtual black box which approaches this ideal ofation >> and it's impossibility. It's also shown to be generally impossible. >> Okay. >> But impossibility is demonstrated using certain complex and kind of pathological example to show that this notion is impossible. So you might be wondering like oh then for a natural program that isn't designed to build adversarial against this notion of mathematical blackbox can this blackbox security guarantee still be possible? So at a huristic level we now have some evidence

that this is possibly true. And what evidence do we have is that this heristic that for natural program we cannot fascate in a mathematical blackbox way connects with this random oracle heristic that we in cryptography love. And in fact if you think about the random oracle heristic which is says that you know give me a the code of a real world hash function say sh >> and by looking at the code having access to this code still an attacker has no more power than just treating the input output of this hash function like a random function. So if you think about

it's effectively saying that the code of the hash function is a mathematical blackbox for a pseudo random function >> h >> because even with access to the code even seeing the code you don't have any more power than just quiry input output and the input output behaves like random. >> Huh? So huristically this notion is possible and from this heristic we can actually justify that for natural programs that mathematical blackbox security might still be possible.

>> One quick question when you say natural program do you mean like in the relativization sense like that type of like like what what do you mean by natural program? I guess >> oh wow I'm so glad you brought it up because there's so much overlapping of terminology. Now by natural program I really meant in the sense similar to in the random oracle heristic >> we know that random oracle heristic isn't true mathematically there are also counter examples on applications in which it is secure when accessing to a blackbox random oracle but isn't secure no matter which hash function you use to instantiate this random or code. However, those

examples are typically pathological, typically mathematically constructed so that we can show a separation between oracle access versus code access. H >> so then the random heristics about for natural applications of the random oracle heristic natural meaning isn't constructed adversarily to create a separation. this instantiation of the random function or the random oracle using a real world hash function is going to be secure. So in the same sense natural in the sense that it isn't a program created in order to prevent mathematical blackbox of exist

>> maybe to zoom out a little bit you know if I compare IO and FHE and functional encryption I'm ignoring the the fact that you one of your constructions uses FHE to construct IO >> but that's like a devil in the detail I think maybe describing how they're different in the sense of like I can obuscate the input I can obuscate the output I can obuscate the circuit or function the program that computes something and how those are all different in these in IO versus FHE >> oh so FH is in some sense advanced version of encryption so what it says is that if you give me encryption of the input without ever decryting ever be

able to derive encryption of the output So we do the computation over the cipher text but it is in some sense following the traditional all or nothing security guarantee in cryptography. What do I mean by all or nothing? The security guarantee is that either you know the secret key therefore you know all information you know all the inputs you know all the intermediate computation results you know all the outputs or nothing means if you don't have the secret you learn nothing >> and a big theme in cryptography even since the 80s and then a lot of different object we're building is to go beyond this all or nothing guarantee that what we really want is that I want

to have very precise ize controlled information release. I have this sensitive information sensitive data X. I want to learn some function evaluated on it and I actually want to learn it in the clear. I want to learn f ofx and that's the only thing that is revealed. >> So it turns out that if you want to reveal zero information, it's actually easier to achieve. If you want to reveal to say exact information it's a little bit harder to achieve >> in FHE you're saying >> yeah in FH it's it doesn't have any we don't have any way of doing that in FH >> and in IO is there the chance to do that >> IO if you think about it is one such

primitive because that I have a program that is secret and what I allow to be revealed is for any input you are able to learn what's the output for that input Okay, >> so it reveals a truth table >> and by truth table I just mean the entire function table and I can easily program it to achieve something like what I just said and you're touching on the concept of functional encryption right functional encryption is kind of the encryption sounds a little bit similar like FG but it allows precise information re revelation.

>> Wow. So you can encrypt the data like in FG and if you're given with one secret key and this secret key is kind of we can create the secret key that are tied to a particular function that's called secret key for function f if you have such a secret key when you decrypt this cipher text of the input x what you learn is not x itself all what you learn is f ofx you only learn the output so the output is reveal and nothing else about axis revealed.

>> But in nothing it's encrypted on both sides, right? So you don't get any info. You get all or nothing. Yeah. >> Yeah. You get all or nothing. And functional encryption is about precise revelation of information. I also as you were speaking about like this black box and all of these things I had echoes also of FHE because I'd always heard like you have trusted execution environments and if you wanted a software version of that or cryptographic version you do FHE but >> but what you're saying is like IO offers first of all you can like have some re revelation you can reveal certain things do TE's also have that feature normally >> yeah I think IO is the direct act analog

of te when people say that once you have f you can kind of remove te what they're talking about is that it's only for a single user who knows the secret key >> ah >> for that single user who knows the secret key of the f now they can delegate whatever computation on their input to the trusted environment now doesn't need trusted environment because everything is encrypted and then they will get back an encrypted output if they know the secret key they will be able to decrypt and learn the output.

>> Cool. >> But the point is that if I want to reveal information to the public, this is not going to work. >> Ah, >> unless I reveal my secret key to the public, then everybody learns every information, all of the information. >> Yeah. >> In functional encryption, I can reveal a secret key for the function f and everybody will be able to learn f ofx. >> But not the things you don't want them to learn. >> Exactly. not the things you don't want them to learn about X. >> One thing I think that might be worth adding here is functional encryption and IO are very closely related like one implies the other. So maybe talking through that cuz like I think that you know functional encryption is actually easy to understand in some ways easier I feel like but the fact that they're

equal is kind of a a sort of notion of of equal under some extra kind of assumptions like may maybe like walking through that and like the history of how people search this space you know cuz like it feels like a lot of these notions for IO and and functional encryption from the 2010s to 2020s like evolved a lot right like people found these special cases pieces and then they like prove them. And then of course you in 2021 kind of wrapped it all together and figured out how to take a bunch of well understood assumptions and build the whole thing. But it felt like almost like watching someone build something out of Legos, right? They like figured out like a brick here, a brick there and then like someone had to figure out how to like put it together. So like the history of this stuff is also kind of

interesting of like how people found it. So >> yes, so functional encryption turns out to be very related to IO. So first of all, let's see that with IO, I can easily build a functional encryption. That's also cute. So first of all, I want to encrypt private information. So let's take a normal public key encryption so that I can encrypt my input X. Now this public key encryption has a secret key. That secret key is all or nothing secret key. Once you reveal it, everything is going to be revealed. So we would in functional encryption I would like to create partial decryption key right this decryption key that are related to a particular function f that's like a decryption token I allow

you to compute f so what I can do is that I can now create a mathematical blackbox which now again is going to have this secret key hardcoded inside and when I'm creating it I will also hardcode the logic function f because I'm trying to create a partial decryption key only for function f. So what this blackbox is going to do if you feed it a cipher text an encryption of X it's going to internally kind of decrypt it and to reveal X but then it's not going to output X it's going to evaluate f on X and only output f ofx >> right so once I have this box I can make

the box output partial information f ofx and nothing else and If it's an ideal fusation then this is really secure. Hence you learn f ofx. It turns out that with IO using what I mentioned is punctured the program technique and also a few other techniques that we can also make this paradigm to work. So that's how IO implies functional encryption. >> Cool. And hopefully you also see that this mathematical version of a trusted environment is really really powerful because it just makes a very hard challenging problem super easy to solve.

>> Interesting. I just wanted to ask something because we didn't do a background on sort of you and where your research has led you but tran you just mentioned this 2021 paper. Is it in that paper that you sort of put those things together? Can you just describe a little bit about what you covered in that? >> In that 2021 paper, this is a joint work with Amed Shahai and Aush Jen. The three of us >> give a construction of IO for the first time based on hard cryptographic assumptions that are well understood, okay, that have been studied for a long time and that we know resists attacks.

And this is kind of the culmination of a long journey of many people the the entire community's efforts of trying to realize IO and what's different in this 2021 paper from prior work is that before we need to rely on some kind of magical unvetted assumptions >> that were invented so that we can have a huristic and candidate construction of IO. I see. And in this paper, you kind of hardened it. You're using like proven parts to like prove that this is actually possible.

>> Yeah. So in this paper that we managed to prove that it can be based on more solid grounds on assumptions that the community um have been studying and they have deep connection with other aspects of mathematics and the theoretical theory of computing. So this for the first time that I think give us a lot of confidence that the concept of IO is not just a magical imagination but really it is something to be trusted. Cool. Because we didn't do your backstory now I'm kind of curious like were you working towards this? Had you been working on this IO problem for a long time before or were you coming from a different part of cryptography?

>> Oh yeah totally. I mean I started working on the problem of IO around 2015. Oh wow. >> And uh at that point I would say personally it had been a a long five six year journey until that 2021 paper I have not been so excited about a topic >> other than this >> that time period. Yeah. >> Oh wow. And when I entered the era in 2015, it was IO was in a very interesting junction I would say the development and it's a concept that dates back to 1970s.

really people were imagining it when we started imagining public key cryptography. But for a very very long time, nobody had any grasp on it until I would say 2013 that came also a breakthrough which is the first work that attempted to construct IO based on a mathematical object called multilinear maps except that we didn't have it's kind of a generalization of pairing groups. In fact, you kind of like inject a steroid into pairing group. Imagine that it can go beyond just doing one pairing but it can do many many pairing as you want. So that's what we call the mult linear map.

If we have that object then we can build IO. >> So that work really took the community by a storm >> except that we didn't really have good candidate of multilinear map because imagining pairing it's not people didn't want to generalize pairing over the past decades. uh we didn't know how to generalize pairings. So they give a huristic lattice based candidate for these multilinear maps and it turns out that it then had been subsequently attacked. >> Okay. It was the wrong candidate I guess >> it was an imperfect candidate. let's say yeah it leaves much I think that work is

still very influential very very important kind of restarted the surge of research on IO and around the same time I think also um the 2014 paper by high and brown waters where they introduced the punctured program technique >> was also a milestone because that really opened up application using IO because I as we are imagining about how to use program fusation. Our natural instinct is using ideal fusation the mathematical blackbox. >> What they showed is that this way of thinking is not wrong when we use IO.

It's just that we need a few more tricks. >> And they introduced these tricks and then really opened up a floodgate of application based on IO. >> Cool. >> And because of those two things, we started to looking into IO again. But then the big challenge and the big question is can we base it really on solid foundation or are we just you know proving everything is possible based on some assumption that is faulty to start with. >> Yeah. So from 2015 when you sort of joined this problem space to 2021, did you know right away that you wanted to focus on that particular problem that it was like you were looking for ways to prove the validity of this that it was

actually it could be based on on concrete proven things or or did it evolve into that? >> I think that I was just taken I was just taken by IO. It was like an obsession and it was also love at first sight in 2015 when I saw all those applications of IO. The fact that it really acts like holy grail or you call it or call it a master tool of cryptography. It is convincing. the evidence was convincing that it is such a powerful tool and also I think the long-term objective vision is also really convincing because we have we now have these like you know

mathematical box huristic even if you if one day this object were to be practical I really believe that engineers will be able to create their own cryptographic tools by using this tool in an easy way instead of relying on the research community which the progress is after all slow. >> Sure. >> So when I saw it I was just taken and at that point that 2015 there were a lot of attacks on those initial huristic candidates and what I felt was that I felt that we need to diversify our approach instead of only focusing on those heristic candidates. the direct

construction we need to have some different strategy. So when I entered my first paper was 2016. The strategy kind of I took was based on at that time a very important work by two sets of researchers which they showed functional encryption actually implies IO >> and that was my initial inspiration which is that can we actually use provable security you know security reduction these modern techniques to first try to understand IO this object by narrowing down to weaker and weaker object object that perhaps will tell us first of all what IO really is and

second what is the hardcore task that we need to achieve. >> So this is a more sort of like a complexity theoretic approach. I thought that if we could narrow it really down to the hardcore it'd be easier no matter we want to instantiate from heristic or maybe we will have the luck of basing it on solid assumptions. So that was my angle and then in the 2016 my first paper on IO construction I showed it can be based on constant degree multilinear map which is still a generalization of pairing except it doesn't need so many number of pairings it just need a constant number of pairings >> sorry is that like AC0 circuit or NC0

circuit >> NC0 circuits exactly yeah it's exactly NC zero circuit so from that point on I was just obsessed about the object and then keep trying to reduce it onto weaker and weaker things and from the other end keep trying to attempt to like instantiate these you know minimum hardcore objects and really I would say it's kind of a struggle from the both ends like from the complexity theoretic angle as well as from the algebraic and assumption angle >> and eventually they fortunately met in the middle in 2021.

>> Cool. So actually I think maybe it would actually be good to kind of talk about the formal definition for indistinguishability in the sense of like for any pair of circuits any PPT like pol proistic polinomial time adversary can't distinguish is sort of like a core thing and like I think maybe first let's talk about the definitions like the the the things we want like you know like the soundness completeness etc. And then maybe we'll talk through the assumptions in your first paper and then how that kind of changed because because I do think understanding the assumptions is actually the key thing because because obviously it's taken people a long time of searching through the space of assumptions, right? And so like understanding the ones that worked and why I think is like would be be

great. But but maybe let's just start with the definition of indistinguishability and and how you can compare it to sort of the zero knowledge guarantees that people succinctness guarantees that people are used to. >> Okay. So let's try. So formally indistinguishability of fusation actually has a really simple definition. The definition says that for any two circuits let's say C 0 and C1 that has the same input output behavior. So they for every input X they evaluates to the same output. And furthermore they have the same size. Okay. So they have the same number of gates. Then what IO guarantees is that if I feed C 0 through

the compiler of IO and I produce C 0 prime versus I put C1 into this compiler and it produces C1 prime. No PPT attackers or probabilistic polinomial time attackers knowing C 0C1 is able to differentiate C 0 prime from C1 prime. So in other words, C 0 prime and C1 prime are computationally indistinguishable for any PPT attacker even if they know C 0 C1 in the clear text.

>> Could that be defined as a form of soundness? Is there a terminology for what that guarantee is? >> I think you could think about it as a term of soundness. And in this definition, it's actually quite remarkable and also connects to our earlier discussion about cryptography moving from all or nothing towards partial revelation of information. >> So what would it take what are the properties that this aasticated program needs to have in order to make sure that they hide it's coming from C0 or it's coming from C1.

>> Right? So there are two elements to it. Obviously there's some privacy, right? because it needs to at least hide which circuit if it gives out the circuit in the clear it's clearly there's no privacy you can easily tell apart >> but there's also what I would call integrity >> okay >> and what does integrity mean is that given this aascated program that I am able to evaluate it on arbitrary input and it's supposed to produce an output now an attacker what an attacker can do it really has this program at its hand it can actually See you know this program is also going to turn itself into a circuit right how else how are you going to execute it so as the

attacker has this program at hand it's going to observe all the intermediate values that this program is computing hopefully they're all going to be scrambled and does not reveal information about the circuit inside and additionally that it could in fact flip right it's in the circuits execution it could even temper with its execution. It says, "Oh, I see this wire now evaluates to one. Let me flip it to zero and see what it continue to execute out.

>> So, it can do a lot because this is direct access to the code. The attacker can do a lot. So, what does integrity mean? The integrity means that this program no matter what the attacker does, it needs to make sure that given me X either produces garbage if it's too much tempering or it needs to produce the right Y. It should not produce you know Y prime which is evaluation of X on some related circuit. Right? So that's what I call integrity. There's a building soundness to it. you need to make sure that it's really executing the right program inside.

>> So, actually a kind of related thing I guess maybe slightly before we go to the assumptions, but since we're continuing to make the the connections to ZK, I might as well bring these up. So like I have a function I've represented it as you know a multi-linear polinomial like it's boolean expansion and I arithmetize it like you do that in ZK you do that in IO. in both cases you construct kind of these polinomials but the difference in IO and and sort of it took I think I had to really read your paper a couple times before I understood this is that basically for a given boolean function there's a set of circuits and in theory that that have the same truth table in theory right I should be able to just if I had a PRG that could sample those

circuits and I could random like I could randomly sample a circuit for a given function it seems like that's like a naive obvious way to get IO, right? But that obvious that doesn't work until you, you know, when you go into the details. So like why should we not expect something like that? If I was able to enumerate all the circuits that represent a single truth table, why could just choosing a random one not work or like why is it hard? Because that sort of has always that was sort of the naive thing at first, right? It's like oh imagine I could write out the set of circuits, but there's some complexity reasons for why you can't do that. Yeah, I mean that's a fantastic question and in fact that's why IOIO is such a fascinating object because you know in most of the cryptography that if

P equals to MP then the cryptography doesn't exist like if P equals to MP we don't have one function we don't have public key encryption nothing right so we we better be living in the world where P doesn't equal to MP but actually if P equals to MP IO exist >> exactly for the reason that you're mentioning because now what would I do my compiler given me a program what it's going to do is it's going to try to find either as you say a random circuit that a random circuit that implements the same program or it could find a lexical graphically first one that implements this program because P equals to MP this

process is going to be efficient and this is actually statistical IO this a statistic it's going to give me perfect indistinguishability not just computational indistinguishability the only problem is that this approach isn't efficient in the word of P not equal to MP right it is hard to given two circuit to identify whether they implement the same function let alone to say that give me up one circuit I want to find all possible circuits or the first circuit that implement the same function By the way, the reason I bring this up is I think in ZK people always think of like I made a single circuit. I don't care about the set of all circuits that could give me

the same input and output, right? It's just like which one did my compiler give me or like which pol multilinear polinomial did I construct, right? Like whereas in IO you actually do care about the comnatorics of like how many of these circuits are there? How randomly can I can I kind of like give you one without you you being able to infer which one I chose. And and to me that always seemed like the gap like of why it was stronger. is like you somehow have to deal with the set of all possible circuits that do the same thing versus just like a single circuit that does something. Do do you agree that that's sort of like the where the gap comes from?

>> Oh yeah, definitely that's exactly the gap that comes in that kind of reflects itself in the difference between ideal fusation and indistinguishation. Ideal fusation is like zero knowledge. You don't have to care about >> how many different implementation of the same circuit. you just a fascated it's a black box right and the indistinguishability of fusation however you when you want to use its security guarantees in honest environment I can always just fusk it comes as a compiler I can always just feed my circuit into it will produce something that at that moment I don't have to care how many different implementation there is but if I want to reason about would guarantee

this aas could the program give me then I have to start thinking about oh another implementation and based on what other implementation there is I reason about what's a security that is why IO isn't obvious it isn't obvious why IO is powerful and that is thanks to the large body of work that we now have that give us these additional tricks to get around this difficulty >> I was hoping to continue kind of on a story from your 2016 paper. They're like functional encryption around that era.

Functional encryption allows for IO. You just mentioned these tricks like maybe you can share a little bit more of what those are. It sounds like that's kind of what you compiled in those years until 2021. >> Right. So I think I think I can tell you that one very powerful trick which is functional encryption implies IO and there is also a notion which is called exponential efficiency IO which is very related to functional encryption. It kind of captures what the functional encryption is doing. Why is it related to IO uh in the language of IO? So what is it? Like if you think about an IO at the core of it, it has this ability to

compress a very large truth table or the input output behavior into this canonical circuit, right? this canonical circuit from which you can no matter which implementation of the truth table you started with you're going to end up with this canonical kind of representation except it's it's not a single representation it's a kind of you know computationally indistinguishable so it's like a sudo canonical representation so it has like a gigantic compression right from the true state table which is exponential size to this sudo canonical version which has polinomial guys.

And what is the notion of exponential efficiency IO? It's saying that okay, maybe I just look at a little bit of compression. What if I just have a tiny tiny truth table? Not so tiny, but it's not exponential size. Exponential is hard to deal with, but I just have a polomial size truth table. And if I have polinomial size truth table, technically I can compute this truth table and just publish it. This is actually perfectly indistinguishable of fascation by itself.

>> Huh? >> Because any two circuits that computes this polinomial size truth table is going to be end up with the same table. So obviously you have lost any information about which circuit you came from. Now what we exponential efficiency IO or we call it X IO says is that I just want to compress this polinomial size to stable by a little bit. You know if I started having size M I want to have the aascated circuit having size M to the 0.99 for example. So any sublinear compression is enough. That's what XIO give me. What we turn out can show is

that XIO implies full-fledged IO. As soon as I can compress the truth table just sublinearly, I will be able to compress exponentially large truth table back to polinomial size. >> H >> and XIO is essentially functional encryption. An object that is even weaker than functional encryption. it gets close to functional encryption and the reason is because as I mentioned functional encryption allows you to reveal f ofx but for every such revelation in some sense that it needs a token so in other words it's kind of like once I offcate

my input x I can reveal a polomial number of outputs different f ofx for different f as long as I can give out prenomial number of tokens >> but they cannot go to revealing exponential number of outputs because for that I will have to reveal an exponential number of tokens that is not feasible. >> So the cipher text for x can be expanded into polomial arbitrary polinomial number of outputs that is the connection between functional encryption and xio.

Now the magic is in the functional encryption to IO transformation. In the language of XIO to IO transformation there is a connection which is that in cryptography maybe some of you know that there is a transformation from pseudo random generator to pseudo random function. A pseudo random generator is something that says I can produce from a short seed. A polinomially longer pseudo random string. Whereas a pseudo random function is that I can start from a short seed and produce an exponentially long sudo random output. And similar to this sudo random generator to s the

random function transformation almost the same paradigm I can go from Xio to IO. And the key idea is use recursion. >> Oh, >> which is that as soon as I can compress by a sublinear amount, a little amount. >> Yeah. >> Then I just keep compressing, you know, I keep keep compressing until I ended up with tiny one. >> Were you borrowing that idea then? Like you saw the pseudo random generator to pseudo random function happening and then you you realized you could like kind of borrow that technique. I think this is a very much um kind of a viewpoint in a hindsight.

>> Okay. >> So when uh the first two works by two sets of researchers showed the functional encryption to IO transformation and then later on we proposed this notion of Xio and show that the similar transformation goes through >> and in the hindsight that we saw the similarity >> it looked similar. So you had sort of on a parallel track discovered a similar technique. >> Uh I guess so. Yeah. I guess people had this you know as researchers that we are nourished by all the different ideas.

Sometimes you don't know where this inspiration come from. >> Yeah. >> Yeah. >> Cool. So I think that's one very important step in the development of IO that we're able to reduce it down to just you know look at the polomial size truth table that makes it a lot manageable. Another very important step is that we realized if we have one of the assumption which is sudo random generator that are computable in NC0 circuits meaning that every soda random output is depending only on constant number of elements in the input C. If I have that kind of simple sud random

generator then not only I care about these truth table that are polomial size I only need to care about these truth table that are computed using NC0 circuits. So this not only that I don't need to care about exponential number of outputs I also only need to care about very very simple circuits. That's another kind of important step. H actually on that point, you know, I I think there that main breakthrough paper had four main assumptions. So like PRG and NC0 was sort of one. I know I guess I know that one is like a a kind of mixed assumption like we know there exist PRGs in NC0,

but they're kind of very annoying versus NC1 like the logarithmic depths ones. But >> yeah, I understand >> because at the end we will talk about like what does practical IO look like? And I know this type of stuff and all the blackbox reductions in XIO and stuff like that like add up a lot of complexity but >> so so PRGS and NC0 you can you know pseudender number generator with constant when I expand it learning with errors so that's you know common to FHE >> learning parody with noise so it's like sort of like a sparse field version of LWE in some ways except you have some extra conditions and then like a bilinear Din type of thing. So maybe let's talk through those assumptions. Why were they

necessary? What does each one give your construction? And I know you wrote some later papers that remove some of those. But just to >> we'll wrap up on the 2021. >> Yeah, the 2020. uh I think eventually that we show that LWE isn't needed but I think that the two assumption that are really needed is one the learning parity with noise assumption which is kind of as you mentioned uh for people familiar with LWE it's almost like LWE except that it's not using small noise to perturb a linear system it's using sparse but large noise to perturb linear system. It's closer to the coding theory

because in coding theory we usually think about a code word being corrupted with sparse corruption but whenever a corruption happens that that location of the code word is completely gone. So that's the assumption and the other assumption is bilinear pairing with a dealing type of assumption. So what bilinear pairing is really needed is really comes from the genesis of IO where the first heristic construction is that if I have bilinear pairing on steroids which is I don't just have one pairing I have like so many number of pairings I can keep going each pairing is a kind of corresponding to one multiplication on secret values right we

know that the groups usually allow you to have addition over secret values And that's just a general like discrete log hard group and pairing gives you one more computation which is one multiplication. But the problem is once you've you've done one multiplication you end up in a target group. You cannot continue multiplication anymore. >> Well I guess actually one quick question though because in FHE you have the sort of reenrypt type of thing of like I multiply I add noise I reduce. It seems like you don't have to do that here in how you've constructed things or am I mis misinterpreted?

>> Yeah. So the the the big distinction is that in FH everything is always hidden. Like you can do more multiplication in FH but you never reveal like there's never any reveal of information. But what's interesting in pairing is that even if you think about just group not pairing an elliptic curve group that it has both privacy and it also allows some revelation of information which is if I have a random value and I put it in the exponent G to the R. We know that this is hidden and we can leverage this privacy to build encryption. At the same time, this mathematical structure also allows me to test if g to the x is where

x is zero or not because I can just compare g to the x with the identity. So that's a tiny puncture of a hole that allows some revelation of information that FH doesn't have >> and it's an art to build on top of this tiny puncture of hole of revelation of information. From pairing we can build what we call functional encryption for quadratic functions because it allows for one multiplication. So you can evaluate a quadratic function on secret input x and you are allowed to learn whether the output is zero or not. So, so, so actually this this brings us to a

good point which is, you know, I think a key construction in this paper and and maybe it wasn't the first place that this was done, but for certainly the first place I ever saw this of like arbitrarily high degree on public values, but degree two on secret values like you you you somehow were able to factor the the secret versus public data and that allowed you this kind of thing. Like how did you come up with that construction? because I think that that that to me that felt like there are two things in this paper that seemed very like not very obvious. Well, first was that you could split this thing into this like low degree and highderee thing and then a very low degree like two and then the second was that you did this like sort of like almost like Johnson Linden Strauss compressed sensing thing

where you made these matrices that you expanded and compressed, right? I'm just kind of curious like how what were the inspirations because there were like so many different things I feel like that went on into this construction that this had to have taken a long time to to come up with putting all these things together. >> It it certainly had taken a long time. It certainly had taken a long time. >> Well, just cuz they seem very desperate. You you took a lot of things from many disperate parts of cryptography. I felt like >> I I mean that's the that's the beauty of research. Sometimes I don't even know where the next paper is going towards and I think that what you are describing is we say we can have functional encryption for quadratic function and

this was actually shown a much earlier work where um I build uh in fact I said if you have k pairing available then you can build functional encryption for degree k polinomials and if k equals to two then you can only have quadratic function and that was in earlier work that was more sort of direct followup to initial attempts of building IO based on multilinear maps but we formalized it and we can show this primitive can be done and later on initially we were trying to just reduce the degree needed from K being constant in my first work to down to five and then down to three and then we even made

like you know we also conjecture new sudo random generator assumption which turned out to be true. At some point we had candidates to the random generator that are just degree two. Why degree two is because that we wanted to evaluate those student random generator just inside the pairing. >> Yeah. >> What we realized if we could evaluate the student random generator inside the pairing then I would be good right except that we didn't find a good candidate for it. Until this day we don't have a good candidate for it. So it was an effort trying to seek alternative approach. What if my student random generator is not going to have degree 2? It just have constant degree

and I only have pairing that only evaluates degree to sacred evaluation secret computation. So one thought was to seek the help of fully homorphic encryption. You know, if I have homorphic encryption, maybe I can evaluate the s random generator in a fully homorphic encryption. >> Oh wow. >> Or it doesn't need to be fully homorphic. If I have a simple enough s random generator, I just need a homorphic encryption for constant degree, right? And then maybe the degree 2 isn't going to be used directly to compute the S random generator itself, but it's just for decryption because homop encryption's drawback is that it

has powerful evaluation, but it never reveals any information. So I have to decrypt it in some way and I can only decrypt it inside the pairing because that's a way that I can control what information is revealed. But the soundless property is important because homophy encryption doesn't have any soundness property. Once you I'm given with an encryption of the input you can evaluate any function you want. Right here I only want to evaluate the s random generator on the encryption of my seed. That's why this idea about enhancing the pairing group construction not just do secret quadratic function

but also have a public part of the computation which has a higher degree but the benefit that public part doesn't need to be hidden because it's protected by the functional encryption. So that that's the idea where this partially hiding functional encryption came about. So this is at least a framework where we can put together a homorphic encryption with this partially hiding functional encryption in order to evaluate a higher degrees of the random generator. >> I'm going to kind of rewind a little bit. You guys used an acronym that I actually just don't know which is DIN.

You did define LWE was learning with errors. LPN was >> learning parody with noise. >> Exactly. So you defined those ones but Dlin you didn't. So I'm sort of I've been a little stuck on that acronym. Can you just share what that stands for? >> Decision linear. >> Okay. >> It is a standard assumption over pairing groups. >> I see. >> Yeah. I think the concrete assumption is not that important because we can also build this partially hiding functional encryption using different assumptions over parenting groups. M >> decision linear is one of them. Another is called SXDH

and I am blanking on the full name of that assumption myself. So >> symmetric something diffy helmet right I don't know >> but Anna this is used in a lot of ZK and kind of BLS. >> Why didn't I ever see it? I don't know. >> This is just like in the formal guarantees you make assumptions like this. So this is actually more like the very standard. The other ones are a little more like FHE like LW is FHE. LPN is like actually when we we talked about watermarking and error correcting codes like that's an assumption you make there.

>> This is sort of what I mean like the proof relied on like a lot of different sub fields that had to come together which is like kind of I think what what certainly was was interesting me. So we've talked a lot about the construction the candidate construction and a lot of the details used right like there's a lot of composition theorems like the going from x IO to full IO right where you have to recurse things which can blow up constants and make things expensive practically or you know a lot of the assumptions that are made maybe like the the PRG and NC0 the circuit is really wide and it's expensive to compute or something right like I'm I'm just trying to to say there's if we want to get IO that is, you know, developed. Like it seems like there's like a a long way to go. But I'm

just curious like how you think the world gets there and how this this has happened from like people finding new new constructions that are maybe more direct a little bit like how FHE started with RingLWE and then moved to integers and then all the practical ones are in integers or is it like you know it has to be a totally new thing because I know from our side we we've definitely like heard of like Ethereum Foundation trying to fund people building implementations. I mean, they're using kind of non-ypical assumptions, so I'm not sure how well they'll go, but I'm just curious like how you think about the the how this gets out in the world.

>> That's a very very good question. And I would say that is the next challenge that the next mountain to climb and if we have to make some analogies, I would say that I is an infant at this point. >> Okay. Not even walking towards the mountain, just growing and developing. Yeah, it's a it's like developing. Yeah. So, the research is really I think still in its infancy that there's so much we need to do, right? It will be great just to have alternative constructions.

That's number one. It will be great to have heristic constructions based on principle new assumptions and towards the practice. And I think that the current construction is very far because of several different efficiency bottlenecks. What you mentioned about this bootstrapping sometimes we call or this FE to IO or Xio to IO transformation uses recursion is by itself too expensive. But on every such a front that we we need completely new ideas and in this particular one that one can potentially think about the direct algebraic constructions which may still

be under the hood be viewed as using recursion. However, because of the direct algebraic construction, it might be much more efficient. So the analog I would make is that when we first had the gold rock mali sud random generator to s the random function transformation that one wasn't >> in a blackbox way that one wasn't usable either however subsequently we had a direct algebraic constructions for example like now wrangled p random function construction from the groups and those you can in some sense see the structure of the original GGM transformation inside. However, it's

algebraic. Being algebraic makes it much more direct and much more efficient. And in fact, there has been attempt trying to create algebraic versions of this transformation that could potentially be more efficient. And in terms of XIO itself, I think there are also attempts trying to have direct lattice based candidates. We're trying Lattis again. They started with Latises and we're still trying Latises. attempts of directly using fully homorphic encryption to build XIO candidates and this line start around 2021 or 2020 that the key technical barrier here is to overcome the fact

that fully homorphic FG does not reveal any information and we want to create a new way of control decryption that I want to give you an encryption ion of the circuit allow you to evaluate on input one to 100 and reveal only the outputs for inputs from one to 100 and this revelation as I mentioned it's important that this this token that allows me to reveal these outputs these 100 outputs is going to be shorter by itself than 100 and that is the key technical challenge >> and there are some recent works including my own trying to do this.

However, it is at a stage where we are making new lattice based assumptions. >> Okay. >> So, I would say it will still be a while before we stabilize in terms of assumption trying to attack it. either we will reach some kind of hopefully we will reach some kind of stable state that there is a new assumption that we're willing to kind of go forward with >> or maybe we were if we're really lucky manage to build it from standard latis assumptions >> actually out of curiosity like what is the non-standard like what is the thing that you're you're assuming here I guess >> yeah so if you think about it for the homop encryption will allow me to from

an encrypted circuit because I want to hide the circuit. Yeah. To evaluate an arbitrary number of outputs. So from input one to 100. Let's use this as the example. So I will get outputs. I'll get encryption of the outputs for input one to 100. Now the question is how do I reveal these outputs? So this seems to require me to give you a decryption token that is going to break the output cipher text. However, I want to make sure it doesn't break the input cipher text because the input cipher text hides my circuit. So, I want to have these decryption tokens that is powerful enough to open up certain cipher texts

that I wish but do not open up do not hurt the security of other cipher texts. So, what is this decryption token is going to be? I mean what's even worse is this decryption token has to be shorter than 100 because otherwise what's the point right the most powerful decryption token is the secret key itself it's certainly shorter than 100 but you know it's going to reveal everything so it has to be some kind of leakage information about this secret key and the leakage information that is tied to the input one to 100 and this is really difficult to come up with some leakage

that is powerful enough to open some cipher text but not all. So that's where the new assumption comes in. >> It is in the ballpark. The type of assumption we're exploring is what we call LWE with hints. With hints, huh? It it's like the way you're describing this actually reminds me of some like old school complexity theory things like the the switching switching lema type of stuff where you randomly restrict a circuit and then suddenly it's depth is much smaller. >> Oh interesting >> like like like it sounds like something like I I got to read this paper but anyway I that sounds interesting. I I didn't realize that this is a >> yeah I want to also shout out that there are completely different ways using completely different mathematics for

building directly building IO for example there's recent research on using local mixing of reversible circuits and there is the work on huristic IO candidates for fascating a fine determinant programs so in those efforts we're not working with circuits We're thinking about the different models of computation like a fine determinant program which is somewhat closer to branch program and also reversible circuit is kind of like uh a computation model which is closer to what used in quantum computation.

>> Whoa. So for different model of computation there might be easier ways to scramble them and have some like heristic candidates but those are fairly kind of also in its infancy. >> Well those sound like they're newborns. >> They're newborns. Yeah they're newborns >> indeed. So I would say at this point we're wcoming any idea any idea to come into the field. >> Cool. And we're staying optimistic because as soon as we have algebraic construction whose security is relatively safe optimization over algebraic and direct construction, our

field has now such an expertise that since we're enter the realm of the exponential improvement pipeline hopefully. Right. So that's that's where we are. I I mean it does feel a little bit like ZK in the 2000s before you got all the like R1CS and things that like people finally were like I can implement >> like pre203 you mean >> like even pre like I mean more like 2000s like when it was like ZK was like >> you know very tiny programs right you could do >> yeah we need new ideas yeah but the the beauty with research is that you you never know we never know whether we're

completely stuck or we're just a few ideas away. And once we have the right idea, things may jump. >> Amazing. >> And that's what I also love about theoretical research is that sometimes it can create these long jumps. >> So cool. So we talked, you know, earlier about your 2021 work and how you had been able to collect these proven assumptions from different spaces to bring them together to sort of prove that this thing is possible. since then I mean you've just shared like some of the ideas but your own research like your own work what have you been focused on like have you touched on some of these things have you started to explore the lattice stuff I'm just curious what your work is on >> yeah so I have been exploring the

lattice stuff together with my co-author and Aush Jen is a long-term collaborator also an author on the 2021 paper and high so Aush and I have been exploring all latis based construction. So earlier that I mentioned that there was a new approach that was proposed in 2020 and 2021 and that approach generated some new avenue and then initially we were really focusing on crypto analysis because there's always that component of new assumption and unfortunately that we we showed through cryp analysis that these assumptions have counter examples right we can create counter examples to

contradict predict a certain version of their assumption. So it's not completely broken but I would say that this journey is very much in coming up with a huristic we can crystallize where the heart we can put our finger on where the hardness is coming from >> and even if this hardness is not going to be in the end a standard well studied assumption we would like to be able to say that we can digest this hard problem in a human way and have some reasonable confidence. So I think formalizing this crystallizing this harness is an essential part of this journey. So more recently we also had our own proposal of

assumption for a lattice based candidate and we are going to continue >> our attack and crystallizing the hard assumption. So it's it's very interesting. That's one aspect. Outside IO, I also work on other kind of cryptographic object. In fact, I work on garbling. I have a recent interesting take on garble circuits. And I had a question I actually asked you before the interview started, but but I'll ask it now, which was like I had always heard IO and garbled circuits used together, >> but you informed me that they're actually they're not that close to each other, but like I thought it was like I

thought IO was the technique of garbled circuits originally. So yeah, tell tell me what a garbled circuit is. How is it different? How is it how is it related? Yeah, GA circuit is one of the essential tools in cryptography and you can think about it as since we've been talking IO so much, you can think about it as one time one time evaluation. So what it allows me to do is to hide a circuit. However, to evaluate it on a particular input, I need to first get the token for that input. M >> once I have gotten the token for that input I can evaluate with this scramble circuit and obtain the output in the clear. It will give me the output in the

clear unlike fully homorphic encryption. >> But it's only one time. >> Okay. >> Once I have gotten the token you know that go circuit is it can only be evaluated once. Yeah. >> Whereas IO is perpetual. I guess >> IO is perpetual. Yeah. And you don't need you don't need a token for any input. you just evaluated. >> Cool. I see the difference. >> Yeah. So, gamble circuit is one of the early kind of a concept and it's related to it's used for building um two-party computation and also used in multi-party computation. Mhm.

>> It's kind of our traditional way of achieving this partial revelation of information where each output requires you to do something whereas in IO once I give you something you can do it's perpetual you put it so nicely it's perpetual. So that's a big distinction. Nice. So therefore, gabble circuit is one of the earliest realized crypto which can be based on just one way functions and you can build it using random oracle for example and whereas IO has to rely on much more harness problems.

>> But but there is some some notion of like succinctness versus not succinct in garbled circuits, right? >> Yeah, you're spot on. What these two objects we seemly at the two end of the spectrum share is that they can both reveal partial information. >> And in order to reveal partial information, unlike fully homorphic encryption, integrity is very important. You want to make sure that once this encoded stuff is given out, no matter what the attacker can do, it's always guaranteed that the right circuit is evaluated on allowed input.

>> So that is in the integrity part, the soundness part, right? And now the soundness part actually share across the spectrum. There are techniques that we use and there are also many intermediate object in cryptography. For example, attri attribute-based encryption. Is this attribute-based encryption? Is that how you say? >> Yes, attributebased encryption, which is another object kind of in the middle. People think of it as more powerful than gobble circuit. There's no direct comparison, but it's an object that sits kind of more powerful than gobble circuit but much weaker than IO. It also has this integrity component. So what's interesting is that the techniques for integrity can actually float about.

>> Cool. >> So if I use the more powerful tools such as attribute based encryption or IO, I can build way more fancier versions of the gabble circuit. For example, I can build those gabble circuits where the gabble circuit itself is a small size. It's very succinct. It's much smaller than the circuit itself. that is called a succinct goble circuit. I can even create this goble circuit which are reusable in the sense that the same goble circuit can be used with different input tokens.

>> You still need to obtain input tokens in order to evaluate >> but it can be reused across multiple input tokens. So this notion itself is actually getting closer to functional encryption and indeed it is related. >> Oh cool. So in that sense that the whole spectrum connects to each other and as a researcher you can like swim around in these different >> notions and upstream and downstream sometimes it's a lot of fun. Yeah. I've been like through this conversation just like because it was a lot of kind of like piecing together assumptions and techniques but like do you develop some of those like or do you ever prove those

assumptions like who or who's doing that when you say like you know you wanted to build like a proof that these things had been proven who's building those proofs and like could there be new proofs emerging or new assumptions being proved that you can then incorporate and it would help you explain that like something is actually secure. >> Whenever I talk about assumption, the image that comes up in my mind is a volcano. >> Okay. >> And assumptions are the lavas. On one hand, it's extremely dangerous. >> Yeah.

>> Because they're not proven. If I conjecture that a problem, a mathematical problem is hard for polinomial time computer to solve, I'm making an assumption. And I might be making the assumption that pigs can fly. I don't know ultimately because it's not proven. >> Yeah. >> So that in that sense that the volcano is very very very dangerous >> but at the same time the volcano makes new land on which that life can grow. >> Wow. >> Assumptions is where cryptography comes from. It is it is >> you know it has this duality.

>> It's beautiful. It is it is what we need and then it can take us to places that we we didn't know how to do and then we whenever we have a good new assumption a secure one so much grow out of it. Yeah. >> You know just think about the story of lises it didn't exist until RV's paper in 2005 I think. >> Okay. >> And look how much cryptography has advanced because of this assumption. But on the other hand, if our crypto business every day is I want to achieve a goal and I make a new assumption. I want to achieve a goal and I make a new assumption, then we don't know if we're just, you know, pro proving every possible statement based on false

assumptions. >> Well, then we know we can't do that, right? >> Well, well, no, no. Yeah. In in your in your analogy, are crypto analysis equivalent to like people who like to climb volcanoes when they're erupting and like watch Yes, they are. They're absolutely warriors. They're absolutely warriors and requires a lot of skills and that is what is an important aspect of cryptography. So you are absolutely right that the new assumptions do come about once in a while and the ones that the people usually use are typically those ones at the tip of the iceberg >> because they are the ones that actually are elegant you know and they are simple

to state. They are having structures that people have studied a lot. We have good confidence about their security. So those are what we prefer to use and what we encou we're encouraged to use for very good reasons. M but where do this assumption ultimately come from where people have to try right taking nourishment from different mathematical fields looking at the cryptographic goals that we want to build but actually fail and try to bridge the gap and make variations of existing assumptions in order for favor of practicality or sometimes functionality and lots of people are doing that and that by itself

sometimes is going to bring us new assumptions. Cool. >> Yeah. I mean, I I do think the one thing that's to me the most interesting about IO, and maybe this was like sort of true for ZK and like the 80s, is just like how close it is to complexity theory in the sense that like the assumptions are you're like right really dancing on the edge of like of complexity theory type of stuff. It feels like if you can do IO, you've turned every average case problem into like a worst case instance for like the inverted and like that seems like just like a generically very strong thing. So it just seems so much harder than something where you're like I I only need to be worst case sometimes >> if that makes sense. It's like I always

have to be worst case is like sort of a very high standard. >> Yeah, it is a very powerful concept indeed. Yeah. >> Cool. All right. On that note, I really loved this conversation. Thank you so much for coming on, Rachel, chatting with Tun and I. I didn't know much about this at all, so it's been wonderful. >> Oh, thank you so much for inviting me, Anna. And thank you so much, Ter, for asking so many questions, and you are so knowledgeable. >> I don't know. I mean, I'm reading your papers. It's not It's not You're the knowledge source. I'm just a a learner.

>> Cool. Thank you so much, Rachel. >> Thank you. Thank you. I want to say a big thank you to the podcast team, Rachel, Henrik, Tanya, and Kai. And to our listeners, thanks for listening. [Music]