Indistinguishability Obfuscation iO | Devcon SEA

okay all right everybody let's get started you okay so this is the the final session of the day um so the session is broken up into well I was originally broken up into like three distinct pieces but we changed it recently so like first we're going to talk about I'm going to introduce like what IO is and why we want it then AR is going to talk about some of the definitions of IO and then Jay is going to talk about this specific scheme that we've implemented called local mixing and he will describe the Bounty and talk about that and this is supposed to be and then TI is going to talk about uh uh oblivious RAM and and how you can build memory to work with IO um so that you don't have to use a circuit model you can use like a more computer model um and that's our plan and then I was supped to finish about like halfast 3 3:45 and yeah so this is supposed to be interactive we have whiteboards and like some slides but mostly whiteboards so please ask questions are we're going our T run around with a mic if you put a hand up or you can just shout things out and we'll repeat the questions uh the most important thing is that we have like a dialogue so we're able to explore these things together um so that's our that's our plan for today so let's get started cuz we're a little bit tight on time it seems okay so let me start with my piece about like iio and and why it's useful um so I I kind of talked about this a little bit earlier right so so what do we want to do when we we do IO so we want to take we want to take like a a circuit some kind of computation that we want to do that has some inputs and some outputs like imagine that this is like an and gate where you have like two ins and one out okay merge these together and then the truth table of an and gate I know is this uh uh yeah anyway so like we have some kind of like circuit that we want to execute so the people over there are able to see is everyone to see the is it better like this is that good Alex can you see this yeah yeah it's okay okay um okay so this is this is what we start with right this is the like kind of the input that we want to OBS for skate and then we have some process here this is the OBS fation step and you can think of this like encryption that we want to encrypt this program such that on the other side we get something that preserves the functionality of the program but has a different uh it preserves the input output map but it has a different all of the intermediate steps are hidden so all that I can learn from this program is what I can get from like a blackbox access to the program so imagine that I'm able to like imagine I put this on a server and I'm able to execute this circuit on a server I'm all I'm able to do is learn like for what input I get what output but I'm not able to learn anything about what's happening internally so that's that's the goal of that's what we're looking for here and let me explain why we're looking for that okay so uh uh the reason that we're looking for that is we want to do things like we want to make an IO box yeah we want to make this like encrypted box that I can send to you and you're able to like execute the Box you're able to give inputs and get outputs but not able to learn what's going on inside but and specifically what we want to do is we want to have a signature and we want to have an encrypt and a decrypt happening inside this box and then we also want to have like just general compute we want to have all of these things happening inside this IO box such that you're able to encrypt decrypt sign uh sign things but you're not able to see the private key that's doing this you're also not able to see the intermediate steps so like imagine that I have a here's a simple IO box we would like to make right you give an encrypted input input one and and I give an encrypted input two two right and iio box takes the inputs it decrypts input one it decrypts input two it adds input one plus input two and it Returns the result right or like let's say instead of add it it multiplies and this this is really powerful like if you can do this then you're you're able to you're able to do like all of the stuff you can do with f and all the stuff you can do with NPC you basically but you're able to do it in a non-interactive way that I can encrypt my thing and I can just give it out to the world then my the world is able to take my thing it's able to do like arithmetic to my thing or it's able to execute any program on my thing and just return the output that that that that just return the output transparently so that's our goal right because like last year I talked about like two PC is for Lovers which was talking about like NPC applications and how you can build things with NPC but like the problem is that it's interactive you have all of the you all have all of this all of this power but like you're really limited because of the interaction the the key to the interaction is not the annoying user experience it's the upper bound that it places on the size of the computations that you can do because if you need to have an interaction to the Crypt that means that the maximum number of participants is bound it's bounded by the maximum number of people that can be online at the same time and that means that like you're just you just have this upper bound that you're not able to get over like you can have a hallucinated server with like 10 people maybe 100 people but you can have one with a million people and that's the that's that's what we want to do here we want to be able to make these these hallucinated servers with millions of participants but and that's why we need I so this is this is the motivation for iio now I'll pass over to who or to J what is hallucina server what's hallucinated server ah thank you for the question so hallucinated server is like uh is like an abstraction for like a group computation so like imagine that like normally when you do a computation you send it to like a server you send it to AWS AWS takes your thing and it does the computation hallucinated server is a server that no one can see inside that that like it it it it it maintains the authenticity and the reliability of a like Amazon web services server but it it also has the extra guarantee that like no one is able to see the intermediate steps no one is able to fake what's happening inside the server so like it's it's kind of like a like another way to think about this is that like what iio lets you do is it lets you to simulate like a a trusted third party it lets you to to make up this trusted third party such that you're able to uh such that it can do anything that a person can do yeah do you want to go into the difference between IO and virtual blackbox officiation which is like this is something you're planning to do or no that's I okay yeah yeah do you want to take it sure so okay so the next five minutes or so are going to be a teeny bit more Tech hello okay is that better the no no okay the next five minutes or so are going to be a teeny more technical how's that okay um but the take is if if uh if you zone out for the next five minutes and you wake up at the end of it you won't miss anything important so the thing we want is called blackbox off maybe virtual blackbox obfuscation and the punch line is you can't have virtual blackbox sisc but I'm going to tell you about it anyway because it's a useful thing to keep in mind so what does this mean blackbox obfuscation means I have some some program let's say I've implemented some function call it f maybe it's computed by some circuit or some some piece of code or something and so I have this this function f which has some functionality if you feed in these inputs it gives you these outputs and I also have kind of my implementation of f which maybe it has some Secrets inside I mean maybe f is some sort of cryptographic thing and you know maybe it issues signatures and the implementation of f hides inside it has inside it a a private signing key for example so blackbox alisation if it existed would be an algorithm that takes the source code for f and obfuscates it so you get some OB fiscated F and this is another I don't know it depends what you want if F was if you want to think about circuits f is a circuit and the obfuscation is another circuit if you want to think about programs in your favorite language f is some source code and the out fiscated thing is some some some source code again so whatever it is it gives you another program that has exactly the same functionality but with the prop that you can't learn anything about F you can't learn anything about the original implementation just from looking at the OB fiscated implementation except for of course what you can learn just from feeding in inputs and outputs so for example if F was a digital signature issuing program well you can't learn the private signing you can't learn a private signing key just from a lot of uh a lot of digital signatures even if you have blackbox access to a signing machine and you can you know adversarially make up as many messages as you like you still we assume can't learn the private key so if blackbox alisation existed then the the security condition I require is that you can't learn the private key from the OB fiscated code either okay this is what we want and we're going to pretend we have this this is called blackbox sisc the fact of the matter is you don't and there's a proof of impossibility you can write down there's some sort of silly diagonalization argument thing you can write down a very contrived example of a program F that can never be Al fiscated because there's some argument involving you you feed F its own source code or something there's there's very contrived example that rules this out but let's pretend we um let let's not think about that for a minute and I'll say why there is a weaker a weaker version of obfuscation which we think is probably achievable called indistinguishability IND distinguish ability obfuscation so sorry so blackb box off fisc was the OB fiscated program teaches you nothing about f indistinguishability alisation is is a weaker requirement it says if you have two implement the func two implementations the fun AP so you know there's a function there you could imagine there's many ways you could you could achieve this functionality there's many ways you could code it up but if you have any two any two implementations as long as they do the same thing when you obfuscate them you can't you can't tell them apart anymore okay so that's maybe interesting I don't know I mean a question for you can you think of anything exciting you can do with IND distinguishability alisation yeah if you have an example of a noning system we have a loop a function in which we are calling a loop and let's say it's a smart contract and it is just keep on going and we will have like two smart contracts with similar function so will this IO can distinguish or maybe we go with blackbox in this approach I don't know uh say again you have two smart contracts that both do something in a loop do they do the same thing um I mean okay it seems to me if you had two smart contracts that did exactly the same thing and they both OB fiscated their code then you wouldn't be able to tell which code is which is there any reason you want that yeah I I want if let's say a smart contract in Loop is keep spending gas and it's like this it's not finished then we are able to distinguish because it's not complete it's just keep running the loop so maybe let me try and repeat to see if I understand what you mean so you have this kind of like auction thing that's running and like the auction thing is inside a a while loop and like you don't want to anyone to know when the auction is about to finish because if someone knows when the auctions about to finish then they'll be able to like gain some kind of Advantage so you obate the program such that the auction keeps running and running and running but like no one knows when it's about to end so they can't put the like bid of like 0.1 more than the previous bit or whatever I mean very better example than me yeah if if you can follow up with that so okay yeah I think that's I think that's a like like spiritually what you're trying to get out here yes yeah yeah yeah um sure I mean okay this is the sort of thing you want to do it's definitely the sort of thing you could do with black box confiscation um there's yeah but coming back to I like the definition of I makes it seem kind of useless but in practice there's a trick that whenever you have something you can do with blackbox aisc that you can also achieve the same sort of thing assuming I so there's some sort of trick involving I don't know some sort of punctured pseudo random functions or something I don't want to get into it but um we're going to we're going to sort of do a bait and switch and say okay we want Black Box alisation we're going to talk about applications of Alis as if we had blackx offc but then when we construct something of course the only you can construct is I and so yeah so it means for practical purposes you don't you you would say the differentiation between the two is not important like the usability of IO like I know a bit about I I've seen some of the proofs and it seems quite technical to make it work in the end to to get these constructions to work and I would I was surprised to hear that it's sufficient to actually build practical things in the end but it seems like maybe not an issue or like like you can actually use it as a tool immediately that's what you're proposing IO or or not no we not proposing that we can use it right away what we saying is there are new approaches to program iio um which lie on under the spectrum of let's just say this is this is a spectrum less practical more practical less secure more secure we are at this enter of the moment um what we've done is like we've taken a practical scheme of which the security is not that um we are not able to speak much about the security of that scheme but it's practical um we can go the other round as well where we going and go to the standard assumptions um and that becomes not practical I was not even worrying about the assumptions or the security more about actually the usability independent of whether the implementation is secure but maybe you can when you say go ahead I see I so assuming you have iio the question is what can you build on exactly because for me it wouldn't be like I have a a relatively clear idea of the formal definition but for me it's not so clear what you can actually build with it if you have it like of course you can you can like make these constructions work but as you said the technical uh details that you need to go through to make it work is is not like trivial to me so I was surprised to to Aha no no no okay but I I I I agree with you I mean I think I think the situation is if you could do it with black box offis you can probably do it with iio as well there's a bunch of technical details that are difficult that we're not talking about is your question like in general if we could like what would we do with it oh well there's so much stuff that we could do with it yeah it's it's like the final piece of cryptography like yeah it's a technical argument they're the same thing it's just this weird technicality let's just do one thing let's just give an example um you want to go ahead or not he's not asking about like what would we do he's is saying that like well blackbox obervation is clearly useful but I'm not sure about IND disting of obervation um I I I agree it's not obvious to me either ah I disagree I think it's just a technicality between the two I just want to see if I can clarify the question so I'm it's not really my question I'm trying to clarify this one um if I have blackw off everyone agrees that's pretty obvious if I have this ability to do this IO thing I'm going to need two different circuits and both of them like if I'm trying to do this with something that can do a signature both of them are going to reveal this the um the private key right so now I can prove oh I've made some uh I can use an IO version of this uh to get an obfuscated version of each of these two things oh they get the mood lighting nice um and uh now I have have two different versions of a circuit that have been obus skated and I can't tell which one is which but I'm not I'm still not mapping it to an actual useful C the point is that you have two versions of the same thing and you can't tell the difference between the two it's a definition like it just it's trying to show you like how this is useful but like the point is that like the two things are not like oh you can't tell the difference between the two the point is that you can see inside what's happening like like for me the the io thing is just like a definitional [Music] right so we need to let's just let's just stick to like a few minutes more to this let's just try to stick to few minutes more to this what we can try to do is um okay what are the what are the two properties that iio sort of guarantees it's like if you if you take a circuit and you have offc of function and you produce an output circuit you take the same circuit again do the second time produce another output off circuit these two circuits must be indistinguishable that's so oh oh you you had a different question okay different question yeah so they're indistinguishable it also guarantees that it is in distinguish from the original circuit right yes okay okay okay yeah can I can I maybe try saying like one thing about like a hand wavy mental model that I have so like I think the claim is that if you have some obfuscator that feel that that satisfies those properties of indistinguishability off fisc it quotequote basically acts as a blackbox obfuscator like it you can use it with the same API as a blackbox obfuscator if there is something that satisfies that definition it's like more or less a black box off theator and here's like one way to sort of hand wavely see this so imagine all of the circuits that you could possibly write down that are equivalent to the function that you're trying to write like most of those circuits are actually like really complicated and nonsense looking and it's like really hard to derive the functionality like just try to imagine like all the py all the strings that would interpreted as a Python program Implement a given function so most of those strings are going to like look like really really crazy so if you have indistinguishability obfuscation then what that's sort of saying is that if I run the Python program through an offis Gator I'm going to get just like one of those strings and I'm not going to be able to tell which one of it it is and if we believe that most of those strings are really hard to back out the original program um from then I'm I'm basically happy with this as approximately thinking about like a black box obfuscator does that sort of s has a question uh yeah so um intuitively I see the value of the indistinguishability ofation although there is some vagueness of what exactly we Define as IND distinguishable between what exactly because like doing the same thing is like on the level of design it can be like if it's a very very same thing then it's a very very same way of doing it but if you're doing it differently it's slightly different thing right achieving the same goal but like it's a level of definition but anyways like my question was uh do we have an idea how to get IO the short answer is yes yes uh yes the short answer is first of all we have U we have a precise definition you might not like our definition but if you have I me when I say you have a function a function takes some input you know maybe it takes bit strings of length a thousand and give some output maybe a bit string of length 20 and if to say it does the same thing really literally means whenever you feed in the same bit string to two fun to two functions you get exactly the same output there's no wiggle room and so and so fine so that's the definition is that when you obis a program you can't tell the obfuscated code from an obfuscation of any other program that does exactly the same thing as far as how to get IO there are a bunch of um there are a bunch of approaches in the literature there are some that are proven secure but are too slow for practical use there are some that the security is kind of an open question but that to be practic but then you have this this question it or not so that's sort of in a n all the state of things right now can I give an answer to your question earlier about like two programs that that you would put in and just get a little more practical here um so uh let's say I have two programs and let's say that uh uh one program uh takes as the input uh like some string and then add adds some secret value to it hashes them together and outputs the hash and uh let's say the second program um uh takes as input the string and then like iterates like a billion times until it finds the thing that matches the hash and puts it out so those are going to have the same inputs and the same outputs but one of them has like this observable property that if you could see it then you could do the computation more easily I disagree because how did you implement the second the second program does did you just say it kind of does random gues until it happens to upon the hash and then it Compares each it iterates over a a sequence of numbers that would it's a long list but how does it know the second program how does it know when to stop it it it has a a a matching like it it it has half the hash that it's matching against or something like the example is not important the point is like you can you can write an example that one version is like the trapdoor function that has the easy way to do it and one is the Brute Force version that takes longer but gets the exact same output I see and the indistinguishability property is interesting amongst these because in real life if we could observe the internal difference between these two functions that have the same input and the same output we gain insight into something I see okay cool more specific with that can I say that U it becomes interesting when you're having some cryptographic function inside it right um and eventually that gives you something like a blackbox sophistication because now you have a fun you have a function inside this thing that is that that still preserves information but it structurally destroys it right I think yeah U does that make sense does that sort of like comp the answer yeah like the point being that that if you're feeding in the one that has the the like easy code that does it the really easy way um it's that result is going to be indistinguishable from having fed in the code that does it the really hard way so the that's the the computational edge of of of the aisc compared to somebody who doesn't know what you put in yeah thank you I think so sorry yeah go ahead sorry so from let's say very practical point of view if I want to explain to someone what's possible to do with uh with the tech could I informally say imagine you have a cryptographic version of a te and that's pretty much what you can do like some Hardware that you really and there is not even a side Channel anything that's possible to do just put the inputs it's something's going on it's going to spill out outputs yeah I I would say that I would call it a mathematical thank you can thank you so is it correct uh you claim that uh even if IND distinguish the oration uh does not or Dory guarantee blackbox security or IND definition uh you think or this can be iio can be uh in practice regarded as a kind of blackbox oration right as long as you have something like as long as the function inside this is cryptographic function something that of like hard to reverse from input outut so you may like or if the function is like such that if the given input satisfies the some or condition uh this is signed by the embedded hardcoded private key so do you think or such function can be also IU for such function can be also regarded as a blackbox as a black so I think or there a uh so I don't think IU directory implies the blackbox or conditions even for cryptographic functions because uh there is an uh construction called I kind of overation called ideal overation which achieves the blackbox ass blackbox security or formally but assuming the holistic assumption like hash function is a kind of random or things uh so uh when say ideal iio do you mean same size not same size because uh in the AIO oration uh we also have to compute the kind of has uh so it's rly increase the size and the competition cost from I and uh this hash function is necess to achieve the blackbox security for I okay uh probably okay um I I would say that I still don't understand what you mean by ideal iio um we should take this technical discussion offline I feel like it's not it's useful for like a small group but it's not useful for everybody so let's talk with the general goal of this is like to get an interior understanding of how can you use it for a blackbox thing I think using like putting cryptographic algorithms inside the I Box gives you something like virtual blackbook it may not satisfy cryptographic U definitions but intuitively you can use it as a blackbox like when you think of like apis it's like a black box like a mathematical te um I think OS had a question of that yeah so my question so from bar presentation yesterday mine is saying is that there are different assumptions and the most extic assumptions are basically something that makes some IO kind of feasible so first question is like what is the nature of those assumptions like I have no understanding of that like that will be first question and second question is like what is it about the more ex exotic assumptions that makes it that we can actually start to work on these things repeat the second question H so what is it about the mo more exotic assumption that allow us to sort of start to construct these things that is not possible with more standard assumptions okay um I I think sorry okay so the first question question is what are what are what are the properties of these new assumptions and the second question is just just correct me if I'm wrong uh the second question is what what in these assumptions allow you to achieve practical the moment right okay um I would answer those questions right like after this once we done with you know understanding examples um I think that we should move on to that now because it's five to three okay um cool um you you done or do you have something more oh you're done okay cool H okay let's just let's just try to erase this thing and then let's get started okay so uh I would be talking I I would essentially be answering this this those two questions directly and what and to do that I would be describing you one way of uh achieving something like indistinguishability officiation one way of achieving that um and I just to reduce the complexity of the entire explanation I would be restricting myself to just a very specific class of functions um and those class of functions are random permutations it's a random permutation you think of a bit string which is like 0 1 0 1 01 you perform some function on this bit string and this is the function I'll be describing to you now but like and you get an output I'm claiming that the output bit permutation is in distinguish from a truly random permutation and what do I mean by truly random permutation well a truly random permutation is like the permutation you get from a bit string that you get from entropy Source like you know some sort of heat or something like that from laptop okay makes sense permutation makes sense so I will be restricting myself to building question the string yes like permute it somehow so permute means mix up yeah makes up yeah uh yeah um and um I would beting this class of function and you know later we can talk about how this is useful and how we do apply for getting General class of functions uh like getting iio for General class of functions okay it's good cool for this I'll have to first introduce a bunch of Concepts uh bunch of words that I'll be using throughout and if I miss explaining some words just raise your hand and sort of like answer those questions directly um and the scheme is called local mixing the first thing that we need to learn about local input to the scheme what's the input to the scheme yeah what do you what what do you start with you start with a bit string a bit string yes what does bit String mean like what is that useful for uh bit string is the input like I'm restricting myself to this specific CL so you're I thought we were trying to obate programs well you're talking about bit strings as an example yes I'm restricting my to a specific class of programs that works with bit strings while while any input to any function is a bit string right right like bunch of 0 one 01 01 01 yeah yeah um so that it's the input that you're trying to obate now I'm trying to obate a a function that performs random permutation on these be bit strings oh so you have a random shuffle you're trying to obate random shuffle yes okay so the the so the bid string is the input the program is the shuffle yes what's the output another bit string okay so the output is another bit string yes but like you're trying to obfuscate the the the random yes yes yes yeah okay uh doesn't make it clear um thank you bu okay um this is called local mixing before I sort of like talk in depth about local mixing the implementation itself I need to introduce to something called reversible circuits how many of you guys are familiar with reversible okay uh I think I think I need to explain reversible circuits uh okay uh reversible circuits okay fine a slight deviation from the main thing a reversible circuit is a way of expressing a computation such that it can be reversed okay uh let's just say A+ b equal to C I write a bullan circuit for for calculating a plus b equal to C if I give you C can you find what A and B are from C no oh yes it depends I've only given you c yeah yes yeah you you can never figure out what A and B are if I just give you C but if I give you so this is a irreversible computation okay now if I give you c and b you can find What A and B are because already given B you can find what a is this is reversible computation and you know people started investigating reversible computation and they came up with a way of expressing General reversible computation why something called reversible circuits okay what are reversible circuits uh okay uh I'm going to draw a bunch of things over here and then I'm going to expl explain what it is okay minutes left yes okay so let's just say we have a function and the function is Gates these are the gates okay we have got let's say for Gates this function this function computes on a 4bit input four wires okay a reversible circuit is defined by number of input bits number of wires and number of gates each gate permutes the vires in a certain way and I would restrict myself to a specific Ty type of gate which is usually referred to as a Toof gate a toofly gate takes let's just say there are many wires it takes three of those wires the difference between these two wires and this wire is that these two wires are called control wires and this wire is called the target wire okay so it can select randomly a tough gate sort of select among all the nend wires three wires two of them are control wires and the third one is a target wire what it does is a let just say this wire is a this is B this is C what it would do is that it will take A and B perform some Control Function on these on the on these two wires what is a Control Function could be and or and any arbitrary bullion function you want on two bits it performs some Control Function and zores it with sorry zores it with c and sets c as that okay so you realize that this particular gate a single gate only mes one wire it is only mutating C based on the values on A and B okay and you have a bunch of these wires like many of them to compute any function clear huh now what local mixing approach does is that it observes one special thing about these functions it observes that if you have many gates let's just say you have n Cub Gates well now let's just n square if you have n Square gates with three bit permutations what essentially happens is that the input and output are sorry the the output is a strong sud imp peration um so let's just say we have a reversible circuit with many many gates and each gate is a tool gate which is like three this gate that are described if you have a bunch of them then the output that is computed on a given input is indistinguishable from a 2d random permutation okay that's what and this is the basic property local mixing approach leverages to build program officiation okay is this clear because this is the key point in this entire approach um and the entire paper or the entire approach can be described as you know making assumptions to make this work for programation honestly they're making a bunch of assumptions based on this property and they're trying to um and they're constructing and and they're trying to use this property and make BS of assumptions to build program OB for any arbit thing okay but this is the key thing sounds good permutation function looks like like a single gate or the entire okay let's just say uh you have this as the reversible circuit and you have let's just say four wires here five wires here uh now let's just say this is M which is equal to n² and we claiming that uh this is enough to build a reversible to this is enough to make this reversible circuit suud and permutation okay so what it would look like let's just say you have a bunch of inputs 0 1 0 1 01 it will produce some output 0 0 0 1 1 it should this is indistinguishable from a random permutation that you choose from entropy when I say IND distinguishable let's just say the distance when you measure the distance between the two strings um the the the distance would be less than certain value so overload in the word permutation here okay because like you originally started to trying to make like a random permutation like to mix up the inputs but you also when you talked about the to fly gate they that does a permutation too and I feel like this might be some confusion here that like the gate itself does a permutation but all the gates together do another kind of permutation yeah uh which is induced by the gates themselves um okay uh so first thing to note is that the authors use of this this paper sort of like you this this particular approach sort of uses this pseudo Randomness property of reversible circuits okay long enough GES pseudo random now what did the do is they sort of like Express their entire compute they express their entire compute um let's just say h okay let me do this uh let's just have circuit C what is circuit C again a reversible circuit and this is again with m is equal to n² and N is like number of wires what essentially the approach does is that it takes a local subsection of the circuit now this imagine this this particular circuit is very big there many gates it it'll take a small subsection that can be replaced uh when I say replac just intuitively understand like you can take it out and replace it with something else okay it takes a small section of the circuit and then replaces that particular small section with another reversible circuit that has more gates so let's just say it takes out sorry with the same functionality okay so it takes out let's just say this subsection we call it circuit out and then with v Brute Force comes up with another circuit CN let's just say this has three gates that scene may have depending on the parameters let's say five gates okay so Cene has like five gates but it is functionally equivalent to C out and with f of v i mean functionally equivalent okay so it takes the subsection out replaces with replaces it with CN which is functionally equivalent now think of this as introducing redundancy to the Circuit we adding more redundancy to this particular circuit because we're replacing we're taking small subsections at random and we're adding we replacing it with more gates okay so let just do let's just say that we are we do this for many many times you know 100,000 times 200,000 times depending on the parameters uh is this enough to off skate like is it enough is it easy for you at the moment to reverse this operation until now can you say that again what have you done up until now you've just taken like just take pieces of the circuit and replace them with like really big other pieces yes I've just introduced same functionality so I've selected local subsections and replace them with bigger circuits yeah but surely you could just go the other way like you just kind of like recompress it right you take all the big sections and you replace it with smaller sections right you can just go through and see like oh what's the small possible section I could replace this with you can just go the other way around right what B is trying to say is that you know that I've taken C out with three gates I've replaced it with C in with five gates what you can do is that you can find uh random subcircuits random local subsections with five gates try to brute force and find their their equivalent circuit with three regates and reverse the operation okay uh I'm I'm sort of like okay go ahead known by the attacker so the attacker is supposed to know that like your I don't know replacement rule is that you're going from C5 sorry from C3 to C5 uh well yes uh but not necessarily that's not necessary even if you hide it I think there's an attack because let's say the the attack is not five and C intuitively if you if you know about a complexity obviously the class of functions that see out computes like with like any class of function with three gates um they're easily computable by five gates but it's it's always not the other way around like class of functions computed by five gates may not be completed by three gates so why why while while you introduce the redundancy uh you're adding these redundancy parts and you're making you sort of like U introducing hotpots where attacker could root force and find the subsections that compute class of functions compartible by three gates with five gates and figure out what the what the what the values are so I think there's an attack without that as well the questions there um in the expanded bits of circuits like shouldn't you be able to identify well shouldn't you be able to recognize when there's some like trivial stuff happening like like multiplying by identity and things like that and just kind of like Whittle it down until you get back to the original small circuit right that's a good point um yes I think uh that's an attack as well and I I'll describe you how to get around that there was another question I guess it's a pretty much the same question that uh I think Barry mentioned it as well like to me intuitively it seems to be compressible back because if we iterate through a set of gates like this uh circuit we could identify parts of the circuit that could be implemented identic with the ident iCal function like inputs outputs identical with less Gates and if we do that c enough times then we would end up with the presumably I guess the original circuit right okay um right so just for everyone what they're saying is let's just say you have gate one let just okay sorry um I should not be erasing this otherwise I need it again um okay what do I do let's see let just say C out is see out as G1 G2 G3 okay G1 G2 G3 sorry you have 10 minutes left um well I need to explain all these things otherwise I it's it's really hard to make a jump I understand I just telling you the time okay uh I'll quickly go through this okay okay um see if C out G1 G2 G3 if I come up with C in with high probability what's going to happen is um that I'll come with a circuit something like G1 G2 G3 and another another gate that is like I and I inverse right with high probability come with something like this and that's the exact attack that you were describing that with high probability replacement operation would be like a bunch of the same gates with identity inverses or some inverses like gate inverse gate inverse is that correct but in general but like um if we do not you know have a way of getting around this problem then with high likelihood our most of a circuit would look something like this right um and essentially the introduced Rundy would be useless um the way we get it on this problem is that uh H we come up with the way to we do not okay so the way we get out of this problem is like it's it's quite simple you just come up with a way to represent the selection algorithm such that these cases are avoided um like you come up with a new type of representation of this reversible circuit um and the way you represent it is why dependency chains among the no among the gates and you take okay this might not be clear but like you take convex subgraphs of this dependency chain um and then and then replace it with something else but I suppose explanation cannot be done in like 10 minutes for this um uh but like we get around this problem by coming with the chronical representation of the reversible circuit so that we get around this Edge case where we are just coming with inverses in the same Gates okay now essentially probably in the representation that I have implemented uh in the actual implementation of this for the Bounty this might exist and probably there's a chance for you to figure out whether this exists or not um cool so what do we do we've introduced a bunch of redundancy uh which is uh which is okay oh there's a question over there hello yeah so um just going down to the very Basics and I'm assuming that we are talking in a theoretical sense here in terms of what attacks are possible so if someone has access to the circuit and they know what how many inputs there are and how many like what the entire circuit and if you're just talking about Gates it is possible to construct the Boolean expression for the entire circuit and then you can just use Boolean algebra to deconstruct it into the simplest form possible um and then wouldn't that be equivalent to the functionality that was originally intended no uh well it depends on the number of inputs so basically we're we're talking about cases where you have like 256 inputs binary inputs and in that case it's not possible to come up with the whole F stable um I think this is what we were getting at earlier when you were talking about cryptographic yes it's like it's really hard to so let's just say your function is very trivial let's just say your function is a plus b then obviously it's reversible right like the moment you have input output map you can re run buan Optimizer and get back the function but let's just say a function is start to six well it wouldn't be sh to six otherwise it would know it but uh it's some sort of like a cryptographic function then you cannot find the what the function is right yeah yeah um at a certain scale I mean you can like the only the it is only useful for class of functions where you can learn the function only by have brute force uh and for brute force to be you know feasible like for this to be anything interesting you require the input Break String to be really big like say 64 70 or 80 or 256 whatever that is okay yeah yeah um maybe again a basic question but does per does um practicality also take into account the performance of the OB the obos skated program or not like does the literature ever analyze what is the code size of the or the memory footprint or the execution time of the opos program because I want if I want to deploy that on AWS but it uses 100 terabytes of ram then maybe I'm going to pay a lot like right um that is true so if you go to the Y which is more secure way of doing a program officiation it is is literally 100 terabytes but when you go to the this this more sketchy side of program officiation where we're using some sort of like complexity arguments to officiate a program and you know output something that cannot be reversed then it becomes more practical uh for example the the obate circuit that we have published for the Bounty it executes within milliseconds um it is it's not that big it's roughly at 200 Gates 200,000 Gates sorry so it's it has roughly a blow up of 200x which is depending on which where you like if you're coming from you know normal software engineering probably that that sounds not that good but like in cryptography that's good uh um yeah so just to get in the the right mood if I understand correctly the extra assumptions you have on top of the standard ones are related to the fact that you can make this exact transformation that extends the circuit no way that it [Music] canot example like could set problems to solve something similar to this okay uh okay so what if [Music] and uh and then after that we can start offline um okay so trust me at the moment that I am going to there is a way to represent this reversible circuit as a dependency chain a dependency graph okay what I mean dependency graph a dependency graph has a bunch of nodes and an edge represents some information well that information is Collision but I there's there's not enough time to love to explain Collision but there's a way to transform this graph to this graph where each node is a gate and a dependency is collision between Gates okay now if you're familiar with normal compiler engineering you understand what a chain is like a package depends on another package another package that's what it is a gate depends on another gate depends on another gate another gate that's how we create this dependency graph okay cool uh so this dependency graph could be really big right by introducing redundancy we have made hotspots in this graph right because you've taken subsections of them out let's let's just say we take this out and we we replace this particular subgraph with a bigger graph right that's how we introduce redundancy after introducing redundancy what I'm going to do is like I'm going to make it harder for you to find any redundant path for example if I just give you this particular circuit after introducing redundancy for you it to be easy to find a local subsection that is a hot spot where Rundy exists and reverse it what I'm going to do is that I'm going to try my best best like literally what they do like try my best to spread the redundancy over the other parts of the graph like I I try to diffuse it out to other parts of a graph so that with feasible with with you know with polom Pol resources you cannot find an Hotpot and the way I'm going to do that is I'm going to randomly pick a subsection of let's say five gates I'm going to replace it with five gates now instead of in introducing rcy I'm just going to diffuse it a larger and larger part of circuit and the and and the intuition behind this is that since I'm selecting random subgraphs and I'm replacing them them with functionally equivalent with same number of gates other circuits it somehow diffuses uh other parts it somehow diffuses the redundancy to other parts of the circuit okay and that's what that's what they do the two stages inflation redundancy and then taking away the redundancy by needing okay now um and that's it like you do this many many times the claim is that this is secure you will not be able to reverse it and if you able to reverse is uh it's really nice because now you have the Bounty um okay I think that's it uh can I learn more about the Bounty uh go to of futopia doio it has all the information where you can learn more about this bounty and if you do not do you know do you know what is off estopia uh just a DA track we living in off estopia by the way um um anyways everything is possible okay thank you J Ard and me great hi um I'm T from obl Lab uh next I'm going to introduce to you something uh much more efficient than IO called oblivious Ram or o RAM for short so first let's take a look at an example in web 2 so usually when you register a messenger app the app would require you to upload your contacts so that it can match you with your friends uh but as the user who cares about privacy this immediately raises a red flag so signal uh messenger app that advertise privacy in the value proposition said no worry we will keep your contacts private in our T so basically we will have this secure processor if you trust the Intel uh that will process your context and match it with our users data in our encrypted database okay so everything's encrypted what can go wrong the main issue here is that encryption doesn't hide your access pattern so an attacker say a malicious operating system can guess who is in your contact list by just looking at which disk pages in this encrypted database is accessed even if you put the entire DB into the memory it's still vulnerable to many side Channel attacks so and naive solution would be to scan the entire database for every batch of queries and this is apparently apparently not scalable uh by the estimation of signal this will require them 500 servers to support the business luckily we have Oram to the rescue so first proposed in 1987 Oram can be viewed as a compiler that abates the access pattern of the program unlike I maybe I can explain it a bit more so basically the attacker learns nothing except like how many access you make from your access pattern okay so unlike IO in which we are satisfied with polinomial overhead for Oram we can achieve poly logarithmic overhead and it is also practically efficient so for Signal it reduce the operational cost from 500 servers to just 6 servers and unlike many people thinks Oram itself does not involve any cryptography so it is so simple that we can try to build an Oram together in the next few minutes okay let's build an Oram so recall that our goal is to obate the access pattern so a a first attempt might be to just put these entries at random locations in the database so this would work if you just act access each entry once but once you access the same thing twice the attacker will know it because you also access the same physical location so a slightly smarter approach would be to move the entry to a random new location after access it but it still doesn't work because the attacker can trace where you move the entry to right but we are getting close to a working solution so the high level idea is instead instead of moving the entry directly from here to there like taking a taxi we like these entries take buses so the nice thing about bus is that it always has a fixed route and schedule no matter where you want to go so to make yourself untraceable you only need to hide whether you take this bus or not and this can be guaranteed by say the sematic security of the underlying encryption scheme so to make this idea work we change the structure of the database from a vector into a tree so each entry is assigned a random Leaf node in this tree but it is allowed to stay anywhere on the path between the leaf and the root node so after we access an entry we move it to a random new location but instead of directly moving there we first put it to the root uh to the root node so this is like a central bust this way the attacker does not know where we want to go to next right and afterward we perform this maintenance operation called eviction so this eviction is uh this operation will allow all the it is performed on the entire tree so its goal is to move the entries closer to the assigned leaves and this EV eviction process can have fully deterministic access pattern so the attacker has no idea about what their locations are and with a carefully designed eviction algorithm we can prove that our data structure will not overflow except with negligible probability so here's the animation for the eviction so the last problem we need to solve is how do we know where the entry is in this tree this is actually very simple we just use another orm to store all the locations and because this orm is smaller in size than the previous orm we can keep doing it recursively until the orm size is small enough for just doing naive linear scan so there are many works all based on this Paradigm uh so most of the work focus on how to make this eviction more efficient uh notably circuit is the first work that achieve all log Square and overhead um and it remains an open question whether we can have a all log one log log and statistically secure Oram uh which is the best lower Bond we can prove so for etherum orm could have many potential applications generally speaking you should consider using an orm whenever you need to private privately access a large set of data so a special a specific use case could be this uh private blog Builder uh to protect against M attacks so the goal is to keep the transactions private before they actually got included in the block so flash BS their solution is just to put the builders in tees but they actually also have the same issue as the as signal because the blog builder needs to access the state of the chain to check check the validity of these transactions um I apologize that I have been always talking about tees for those who don't like it um but so the reason why we need a t here is that the or is designed for to light a single trusted client to Outsource the storage to an untrusted server so te here acts as this trusted single client and it proxies all other users requests but if if you think about it you can achieve the same with MPC in fact because the orm does not our orm does not involve running any cryptographic functions it can be easily integrated into existing Frameworks like MP speeds but an issue with these existing Frameworks is that they're interactive basically to make each Ram access you need to have many rounds of communication between the parties uh which is not scalable so there is this more recent line of work called Goble Ram which directly plug this Oram data structure into a large Goble circuit so this will allow us to get constant run to PC or NPC with slightly larger communication cost so I think this is a potential solution for the fra game and if you have check it check it out um if the private State they need is not just like 500 bits but 500 million bits okay um finally let me give you some concrete numbers about the our current implementation of or so first for the te scenario to access uh 100 gigabyte key value database the latency is about five uh 50 microc and uh for the Goble Ram scenario I just mentioned uh for two semi honest 2pc it takes about 15 megabytes to access uh 128bit word in a memory space of two to the 20 in comparison if you do linear scan this will cost about 8 gigabytes so that's all for my talk uh thank you for for your attention this is a QR code you can check for the implementation oh Al so by the way thank you yeah so by the way if you want to learn more about Oram this this uh four easy pieces thank you okay so any questions so I don't know who this question goes to rather to you or to the previous speaker but if you off get a program with IO is it still attackable by observing the memory access patterns oh so I so basically Oram provides like a weaker guarantee than IO so if if you have IO it by the definition it should already hide the access pattern okay yeah but but it is it is a good question so for many schemes like f or like NPC this cryptographic protocols so they also need to have this like memory access pattern issue so um so so in many cases it is not considered right now because these cryptographic schemes are already so slow so if you add an Oram to it it adds more overhead but for like te because te itself does not have much overhead so so the first use case of over happens at te but yes you're right so like for all other cryptography protocol whenever you need to privately access a large State you should consider using an Oram all right uh any other questions I guess we're running out of time yes please um so a very fundamental question um I uh so you mentioned that when you are using Oram and you are in a tree structure you are moving the data from first from the leaf node to the uh root node and then you do a maintenance operation which redistributes it so can a attacker not and because that is deterministic can a attacker not track uh like the what root root node had access to like uh if you in in the example you had db2 moving to the root node so if it was monitoring that location for db2 and it now knows that it moved to the root node and now it can deterministically know where the next location is isn't that again a reversible uh path so are you talking about like when you access this entry you reveal from which Leaf you access it yes yeah this is fine because whenever an entry is accessed it's moved to a random random independently random new location so so it's fine to reveal to the attacker where you read this entry from it's just you cannot tell the attacker where you where the new location is so to do that we first move it to the rot Noe which doesn't reveal anything right you always move to the root node and then you do these eviction so like is the moving to the root node randomized because if it's just after the access then the attacker knows right that this was accessed and now it has been moved to the root node well you can reveal that this Leaf node is accessed okay it's fine so so basic it's like a onetime pad in some sense so you because you only access it at this location once so okay it's fine okay if there's no question I think it's the end of this Workshop thank you for attending yeah amazing to have you here