[Auto-generated transcript. Edits may have been applied for clarity.] So if you haven't. Uh, welcome, everybody, to this term stretching lecture. So, um, as many of you know, these are named after Christopher Spreadsheet, who was the founder of the programming and research group in Oxford. And this early, um, figure in the theory of science. So before I introduce our excellent speaker, I want to thank our sponsors, Oxford Asset Management. They've been sponsoring this series since 2015.
Um, and they want us to bring some reason to theories. And, and he's doing some research and she wants you to meet them. You, um, are encouraged to do that after good talk. The coffee you think is a table somewhere. Um, so please do that. Uh, the way we're going to do it normally, as you probably know, if you've been here before, we have questions out there and microphones runs around. But I happen to know that rafting, like me, kind of also is very happy to have questions in the middle.
So don't be shy. If you feel like asking questions earlier, that's fine. Okay. Um, and then we'll do the usual thing with the mics at the end. Okay. So it's my new really great pleasure to introduce Rafael Ostrovsky. Oh not yet please, not yet. Uh, I'll do that. Thank you. It's my pleasure to introduce Rafael Ostrovsky, um, who, uh, is a distinguished, uh, professor of mathematics and computer science at UCLA.
And I think many of us in this room know him from his foundational work, both in cryptography in that area and also more broadly on theoretical computer science. Uh, but I wanted to tell you some facts about him that you might not know. Um, so, uh, he's also got a huge kind of practical career as well, about 16 patents. And, um, he's got a bunch of fellowships. And so I'm just going to name a few of them.
So because I work with the ACM and we theatrically the American Association for the Advancement of Science, and also proof that I want to see are um, which is a fractional cryptology research organisation. I thought I'd select two of his many prizes to talk to you about. So he's the recipient of the RSA Prize in 2018, and the citation says that he's awarded the prize for contributions to the theory and new variants of secure multi-party computation.
And another, another really prestigious prize is the um 2022 Bechtel Award of the Entrepreneur Computer Society, and their prize was for visionary contributions to computer security theory and practice, including forcing new cloud vulnerabilities and then funding for corresponding novel solutions. So we're really lucky to have Rossi here, and I'm very glad to introduce. Thank you so much, Leslie. It's an honour to be here. Um, and without further ado, let let me get started. So, um. Uh, okay.
The paradox of privacy is that the way the value of data is in using it, of course, and data is often private, and, uh. The questions that I want to discuss with you today is how can you compute on joint data toward the common goal while maintaining privacy? So you have some data. I have some data and we jointly want to compute on it. But of course, the tension in data sharing is that my data is valuable to me and I don't want to share it, so I want to protect it.
I want to sell it. I don't want to show it to anyone. I want to redacted. On the other hand, in order for data to be useful, we want to analyse it. We want to share it. We want to learn from it. So how do we reconcile this to server tensions is what this talk is about. And there are many examples, you know, passenger manifest, no fly list, you know, to hunt for people who shouldn't be on the flight.
Uh, reproducibility of scientific experiments on private data, genetic analysis, uh, without revealing your, um, DNA. Health care providers, uh, sharing, you know, patient data, longitudinal studies of various forms social, economic, educational, uh, logistics, fraud detection, private machine learning, fintech applications, you name it. And this leads us to a general question, which is can we compute privately owned data sets and by data sets?
What I mean is really siloed data sets that you and I and other people have, but we are not willing to completely share with each other for a variety of reasons. And so here's an outline of the talk. I'll talk about secure computations very broadly and what it means. Then I'll tell you kind of a high level alternative. You know, it's just one of the many techniques I will tell you about alternatives to secure computation.
And then we'll sort of we get to the main course of this lecture which is garbled circuits. And then I want to discuss actually two specific examples of the two systems. One is sort of a was built almost ten years ago. One was built just two months ago. I want to tell you about the actual systems, work on this topic and then finish with a few words of conclusions. So first it will be sort of a very broad discussions and fairly technical discussion on garbled circuits.
So let's start with secure computation. So secure computations and players and they all have some secret input. Think of it as a data sets and they want to compute some function. If Churchill would be around. It's actually easy to do. We all trust Winston, so we all give our inputs to Winston. Winston computes this function f and just gives the output to everyone. And because he is incorruptible and completely trusted, uh, well, at least that's what we believe.
Then basically, he's not going to tell anyone else what their private inputs are. He's just going to announce the result. Okay. And so secure multi-party computation says, well, we don't have Winston around. So how can sort of us display a stock back and forth and emulate as if Winston was still with us and emulate exactly the same functionality? In other words, um, we similarly distrusted third party, even though the trusted third party does not exist.
We through sending messages back and forth, we want to simulate to say, deal functionality. Winston. Um, and you can think of it as a virtual enclave, simulated almost dealer or whatever you want to call it. Uh, so please simulate this virtual dealer that doesn't exist. And it also guarantees robustness against, uh, collusion, cheating, what have you. Okay. So that's basically the goal of multi-party computation.
And multi-party computation is quite successful, where we actually show how to do it and do it efficiently for a variety of this functions. Let's actually concentrate on a two party case. Right now there's only two players, Alice and Bob. And again, let's look at just a few examples. Let's start with a very simple example which is uh an XOR function. Right. So let's say and by the way XOR is just bits right. It's zero and one. And XOR is just some modulo two.
So the two players just want to compute uh sum modulo two uh of the individual bits. How can they do it. How can Alice and Bob do it? As they just tell each other the inputs. Why is this okay? Well, let's just think of what happens. Winston takes this to be its exclusive forces together and gives back to both players. Now that you know the output of the function, which is the sum modulo, do two and I know my own input. Of course I know you input. I just subtract my bit from the sum.
That's your bit. So this is a case where they can just talk freely. They don't need Winston. One player just tells to the other player my input is one, my input is zero because the input of the other guy is implied by the sum. Okay. And the only thing we want to say is we want to simulate Winston, which does whatever he says back to all of us is okay. It's everything else that's supposed to be hidden. Okay, so for XOR, they can just show us the inputs.
It's nothing interesting to do here. What about the name function? Can. They just freely tell the inputs to each other. Depends on the input. Exactly. So if I have a zero, can I tell use that I have a zero? No. Right? Because maybe there's a guy has a zero and then I should keep mum. And if the other guy has zero, of course it does. The guy has one. Then you can freely tell him, oh, I have a zero, because if the other guy has one, it will be deduced that my input is zero.
Zero. Um. And. But who speaks first? Listen, Bob, if both of them have zero, they are kind of stuck because both of them don't want to admit to each other. They have zero in the chance that does. A guy also has a zero. And then I don't want to say if my input is A01. And um, right. So that's a really problem with an end function. And then more generally, what about arbitrary Boolean circuit. Right. You have some complicated function. Maybe something about the input leaks but not everything.
And now how can they compute it. So and and more generally we'll discuss it today as well. What about arbitrary programs. You know written in C plus plus Java have recursion. Uh, you know, pointer jumping, what have you. Um, how can we do this? Okay. And what I'm going to talk about today is some recent talks, uh, recent advances on two party computation. Originally I was planning to talk also about multiparty, but they realised there is no time.
Okay, so before we go there, what are the alternatives? Right. So multi-party computation is all about the secure computation that simulates Winston. And what are the alternatives that we have. And I just want to cover it uh because the alternatives. So what is the alternative. One is trusted platform module right. SGX of the vault and what have you. This is a piece of trusted hardware. And Intel says, hey no one can break into it. And why.
You know, even if it sits on my machine, no one can break into it because it's protected by Intel. And so both you and I send our inputs to this Intel, the, uh, SGX platform, SGX computes an input and just announce it to everyone. So in other words, it it it acts as a trusted broker just based on the hardware is a guarantee from Intel or from other, uh, places that that no one can break inside.
Well, that sounds fabulous. But, you know, even 15 days ago, there was an article in the scientific paper from Georgia Tech saying, hey, if you allowed to instrument your computer with all sorts of sensors around the SGX, you can actually steal the keys. And in fact, if happens again and again, pretty much every couple of months, this is, uh, this is messing with us, seeing this, uh, blunder encrypt the keys. And then there's another, uh, a very recent work called Battering Ram.
In other words, if you are relying on this jokes, you don't sleep well at night. Um, so. But that's one alternative. But, you know, I like to sleep, so. Okay. So that's the option is so-called AWS Clean rooms. So that's a service offered by Amazon. And the idea is that offered for secure collaboration by Amazon. Two more participants give data to this, uh, Amazon clean rooms and they compute and just give you the result.
And of course, we must trust Amazon employees instead of just you and me that that they're not going to take a sneak peek and see what's inside. And, um, in addition, the screen rooms have very strong restrictions. What can and cannot be computed. I'll give you one example. Those of you who heard about private sector intersection, that's a problem where you have an input and I have an input, like you have a list of names and I have a list of names.
And if you want to reveal to each other which names are common, which names are common, and we want to reveal it to each other. This is not something you can currently do with clean rooms because it's not possible. It's forbidden in the clean room kind of semantics to reveal, uh, even partial inputs of individual players. So like PSC, private sir, intersection is not possible in clean rooms. And there are also some restrictions on purpose.
The designed in Amazon clean rooms to make sure that my data doesn't leak to you and your data doesn't leak to me. Right. But that's that's a viable solution. Amazon sells us, you know, for good profit. So nothing wrong with that okay. But that's an option. And that's a option is so-called data lakes Databricks of Cloud Warehouse like snowflake. So here it's sort of a similar to clean rooms. And they say, hey give us all your data and trust us, we are secure. We are completely unbreakable.
And, um, you know, I mean, uh, I'm not, uh, I'm paranoid by training, so, um, but, you know, again, they make a lot of money. Once you give us all your data, we will perform computation for you and just give you, um. That's what they say. And by the way, we stole all of the data and run our secure software in a rented cloud, like, uh, this, uh, Microsoft Azure, Google cloud.
So not only do you have to trust us that our software has not a single bug, but you also have to trust that the clouds that we run to do our computations because we don't wanna run software is also secure. And employees also are not going to break it, which is um, now you have to trust two entities, right? Amazon and this cloud providers again. This people. Snowflake is a is a big company making, you know, billions of dollars. So I'm not plagiarising I'm saying those alternatives. Okay.
So and the last alternative I want to mention is so-called fully homomorphic encryption.
So given an A so that's a cryptographic primitives which says given an encryption of X public key encryption of X and encryption a way you can sort of a without having a decryption key, compute the sum of x and y and multiplication of x and y. And now you can sort of do it, uh, securely, where Alice creates a public key and secret key for this fully homomorphic encryption gives a public key to Bob to to the guy with the security input.
And, um, Bob converts his computation into a circuit that just add does addition and multiplication. It's inefficient, but you can do it with polynomial blow up. And then Bob computes whatever function he wants to do and then gives back the encryption of the answer back. And that is decrypts. So that's certainly a possibility. And in fact it's a possibility that many people in US government are excited about. The problem is works only for circuits cannot do random access without touching.
Basically multiplexing touching every encrypted item unless you assume so-called indistinguishable function and then distinguish ability of escalation, uh, takes, you know, trillions of years to compute a single and, and gate. So, you know, good luck with that. Um, uh, so. Currently, it's 2 or 3 orders of magnitude slower even than MPC or DPC, and like some recent benchmarks, says thousand to 1000 to 3000 times slower and even more expensive if you want malicious security.
I wrote some people on this thing, but it's basically very slow. And by the way, MPC is about 300 to 1 to a thousand times slower is an insecure computation, right? So you're getting a hit of 302,000 for MBC times, enough that, you know, 1000 to 3000 if you want to do FHA. And so, so so it's quite expensive. Um, and so, uh, among NPC here, if you want constant bamboo rounds. The only alternative for so-called garbled circuits, which is a main course.
And so let's dive right into it. But also turn natives that you have even before I get into garbled circuits. Any questions before I get into the main topic of today's talk? Okay. Let's proceed. Okay. Garbled circuits. So let me start kind of slowly and explain what it is. So Garbled circuits involves two players, Gabriela and Evaluator. And what Gabriela does is he is going to take some for now. Boolean circuit and assign two cryptographic keys for every wire.
Right. So he is a, you know, the two keys for the wire label, de two case for Y labelled B, and so on and so forth. Also original case associated with every wire and no. Now what he does is he is going to give one of these keys to evaluator to Eve, but not tell him whether this key corresponds to a zero or to a one. Secretly, of course, what he will do is the two keys are kind of secretly labelled as a zero key and a one key. Let's say zero key is red, and uh, green key is white.
But when he gives it to evaluator, all these keys look alike. They basically look like, uh, keys. And so. No. What he is going to prepare is a cryptographic guard, uh, gadget, which, uh, so, so garble up, creates red and green key for each wire and creates a little gadget that selectively opens, opens an output key based on the provided to input key. So if this is an end gate. And by the way, every key is custom made for a specific keyhole.
So like one red key is going to so. So there is a red key that fits into the left keyhole but not the right keyhole. And another red key and green key that fits into the right keyhole, but not the left keyhole. And what you do is you basically out of the six keys, you create the combination such that if you stick, you know, a particular combination. So here I guess that, uh, green key is a one and red key so zero.
So if you have two green keys and you stick it into this little gadget, you unlock, uh, green key, green output key in all other combinations of a red and green key. And lock the red key as output red key. And as long as we can implement this gadget, we can sort of have kind of a logic of an iron gate where if you have two keys, not knowing what they are, you stick it in a gadget, you unlock the gadget and you get some other key. You have no idea if this key is a 0 or 1.
Okay, so that's a basic building block of of global circuit, which was which in almost 40 years ago came up is. And so how given this gadget. And we'll see a little bit later how you build this gadget. But let's assume we have this gadget. How do you do secure computation. Right. And again here I'm not assuming cheating. Just almost. But curiously, you know, I don't have time actually to talk about malicious behaviour. But let's assume no. Just honest but curious behaviour. So what happens is.
Oops. I'm going the wrong way. What happens is like this. First of all. So if has some inputs to the circuit, let's say the three inputs belong to if and. This circuit with this gadget was generated by Gabriella. So this is another primitive called oblivious transfer where if if has secret inputs 110 for every pair of case, it can select secretly one of the two keys to get without disclosing to Gabriella which key she is getting.
So if her input is 110, she gets, you know, the first, uh uh, green keys, the second green key, and then the red key and the Gabriella doesn't know for every pair which of the two keys, uh, you've got. Okay, then also, there's some way to create this gadget, this digital locks such that the right combination unlocks the right key.
And now you can you can do the computation. So, for example, uh, suppose you have two red keys for uh, A and B. Of course evaluator doesn't know if doesn't know that those, uh, zero keys, it sticks it into the locked box and comes out as a key G on D wire. And again, the evaluator says, okay, it's a key. I don't know what colour it is.
I'm just the key. Right. And then I feed this G and C into this XOR box and comes out some key for e. But again, there is some gadget to to fit it into this log box and get the key for E. And then and then you get the result. So what is the procedure? Using this oblivious transfer is simple E gets evaluated gets here keys that correspond to here. Input F also gets this um um materials this cryptographic sort of encryption of this digital locks.
And for gerbil, uh, uh, for gerbil s keys, you know, hurry input. He just hands here one key without any explanation. Right. And no evaluator can compute to get the right key. And then if the gerbil also says, oh, by the way, if you got this last key, it's a zero. And if you got this key, it's a one.
And that's a secure computation where all the intermediate keys, they don't tell to the wallet or what colour they are, and therefore the evaluator has no clue as I, you know, it's the intermediate values is zero one. Okay. So now let's actually dive in and see how we can build this gadget. Okay. So here's an M gate again. And let's assume that h is a hash function. Uh oh a random oracle. So what we do is we have two keys for zero. Uh, and we have two keys for input. In practice, also as keys.
And by the way, is it isn't garbled circuits are so efficient is that every Intel chip or even AMD chips nowadays have a S accelerator inside on it. So each one of your computers has a chip and it takes 33 clock takes to evaluate this encryption. It's very fast. That's why it's such an efficient technology. So you basically you basically, uh, hash or, you know, think of it as a random oracle A0 and B0 into exclusive of it with C0 and so on and so forth, all the combinations.
And so now if you have, let's say A1 and B1, well you applied here, you get this thing right. And now if you, if you know how to compute this part, you edit again. And if you add something modulo two twice it disappears and you get C1 out. Right. So that's a way that's again original Yao's garbled circuit where this is a way to create, uh, a table of, of encryptions such that you can decrypt only one row. And decrypting this one row gets you one of the output keys not knowing which key race.
So of course, to do it properly you have to scramble the row so you don't know, right? If you just write it, you know 00011011. Then just by figuring out which row you decrypt will leak information, we'll talk about it a little bit more, but you have to scramble the row. And as long as the evaluator can decrypt only one entrance of the row, he gets the key and he says, I don't know what value it is. Okay. All right. So, uh. Now the another idea to come up so called a free XOR.
So let me tell you this idea a free XOR is the following idea. Instead of having two keys on the wire, you create. So this is k bits and delta is also k bits. And what you have is that you have a k bit value for zero and the same value. Bitwise exclusive is delta which is a global parameter for one and delta. You can keep the same throughout the entire execution. The point is, as the evaluator will never know what the delta is because he for every Y he sees only one value, but not both.
So as he says B plus delta ob those are k bit strings and k is like 128 bits. So he cannot figure out what, uh, delta is. But um, it's actually quite useful because think of what happens for the X0 gate. Suppose you have uh a or a plus delta and b plus b plus delta. How do you compute c plus c plus delta. Well you just XOR this two values. And if you check the right things cancel out and you get a exactly C plus C plus delta and therefore XOR gates.
If you represent your digital circuit as M gates, an XOR gates, XOR gates now don't require any communication. I just send you and you know, encryption. This table of n bits and x0 bits you just saw in the clear. And this gives you the right answer. All right. Another thing you can do, actually, before it goes to another thing you can. Okay. Um, another thing you can do is so called authenticated sharing.
So what happens here is that. Gabriela keeps this 128 bit string A, and the value it has has this 128 bits A and this represents a zero. And Gabriella keeps an A and evaluate that keeps a plus delta. That's is that means a one. And Gabriella knows the delta evaluator doesn't know the delta okay. And so that's um, that's how you encrypt the things. Now the other thing you can do is there are two additional tricks.
One is called row reduction. Row reduction is to say what if instead of sending a full ciphertext I want to send only three ciphertext. Well let's make C equal to C is so far just a random string. Let's actually make it equal to hash of a and b. And therefore this is zero. Right now we just have to send three ciphertext notes for a ciphertext. That's that's great. That's that was invented here. And then it's an additional idea called point and permute in their ideas like this.
Uh, um, and this was originally for Beaver, McHale and Rogoway in 1990, uh, we will make the last bit of Delta equal to one. And if you make the last bit of delta equal to one, basically this a value and a plus delta value, the last bit will toggle, one of them will be zero and one of them will be one. Let's assign it colours right. So the zero let's say will be called you know will be called orange. And uh, and uh one will be called yellow have nothing to do with the actual logic of the gate.
But now what you can do is you can actually mark every entry like, uh, like this is an entry if you have an orange key on the left, Y and, uh, red key on the white wire, apply edge to this table and you can just colour code for every entry, which, uh, which combination of this colours you can do. And therefore you don't need to try different entries. You can just decrypt a single entry. So this is a so called point and permute. Uh and it's quite useful.
All right. So. Good. What? And and now I want to bring the main kind of a point of this discussion. What makes garbled circuits different from fully homomorphic encryption? And those are the three observations that sort of what drove the last ten years of research. One of them is that G can selectively reveal semantic value of any wire. In other words, what he can do is he can say, look this wire, if it has the point and permute bits zero, it's a 0 or 1.
And if this point and permute bit is a one, it's a zero, whatever it is, right? So he can just selectively decrypt by selecting like the last bit to tell the evaluator what semantic value, what is the actual meaning of this? Why is it A01? This looks quite stupid because you want to hide stuff, but it turns out that this is incredibly powerful, that you can selectively reveal the values in the circuit. You'll see why.
Uh, the second observation is that the evaluator can evaluate garbled circuits lazily, even if some portion of the circuits are still blocked. And the third observation is sort of a kind of a meta observation. Recall that while labels are strings of k bits, what if we represent this k bits separately as a fresh wires? So k square bits total that we can selectively decrypt. In other words you can have a circuit which operates on this case.
But we can also have like this cake keys that talk about a specific key, sort of a metal abstraction that turns out to be incredibly powerful. Okay. So let's get let's get, um. Uh, let me illustrate to you why, you know, selectively, uh, decrypting some particular value is is useful. This is so-called half gate trick. What if there. Evaluator knows the value on this wire, right? Then it turns out that you can actually send just one ciphertext.
Here's an idea. You make the output wire to be hash of the input wire, and you send just one ciphertext, which is this hint. And what happens? Well, if this value is false, if, if the evaluator knows that he has a and it's false, just hash it and end of zero output zero. You already know the output. It's a zero. If you know that this value is true. So the evaluator has h plus delta. Then given this hint you can compute hash of h plus delta.
And what are you left with. You add this hash of h plus delta to this hint that h h of is a plus delta goes away. You get h away plus a b, and now you also have B, so you have B and you end up with a. Right. So it's just one ciphertext. You can always compute. You can always compute basically c plus a b times delta just by this trick. So that's that's amazing. And now you can actually do two half gates um what you do. So so this is just an abbreviation.
This is a secret sharing of B ray, secret sharing of B and secret sharing of bits C and this is what I already explained. So now what you do. But you say, wait a minute. In the end gate you cannot reveal one of the wire. So I want to have an M gate where both wires are hidden and you sort of a do you introduce additional random variables? Lambda subway, lambda sub B you reveal, you reveal a lambda sub lambda sub B to the evaluator.
Right by just by telling him if it's an orange, if it's a zero in the it's, you know, red, it's a worm. And there's a point this what you reveal is blinded by this random value. So it doesn't tell the evaluator anything. But the point is now you can sort of evaluate two half gates twice and uh, multiplies a. So to also send separately like a cross term and everything sort of a beautifully cancels out and you get, uh, the end of two wires with just sending two ciphertext.
So this is your kind of a new definition of a y value. And just by staging sending two ciphertext, you can do it. All right. So. Let me know. Star. Uh, star two random access memory. Right. So the picture now looks like this. So far, it's a virus. Virus? A sort of a fixed in advance. And what if you want to do random access, right. You have a CPU that we simulate as a random circuit, and it wants to read and write into this, uh, memory.
And this is a decision which items you read is decided at runtime as you execute the CPU stuff. So this CPU starts a model, this yells garbled circuits. But now what happens is you can sort of decrypt and say, hey, I want to read location J, right, reading location J. So I want to get location J. And now what you want to do is you want to take the value stored in location J and feed it into the next CPU step. What does it mean? G code at runtime.
You know, decrypt runtime j I want to read j, and that means that I want to, uh, have a value which is stored in this location and somehow translated to is a key, a key, a plus delta, because this CPU sort of wants to feed the value stored him to the next CPU step. But the problem is this J is revealed ahead of time. So how can you do it? So, um, what does Gabriella knows at compile time when he creates the circuit, it notes the actual B's representation of L in data.
It also notes, uh, it also knows that at runtime it will decode some address J and now want to translate it here. So, uh, the original paper, this, uh, one of my students at the time, Steve Lu, was like this, uh, it's a language translation problem. Runtime translate this value of w w plus delta to a. And so what you do. But but you don't know, uh, what w is that location? J so, uh, our original idea was to store, uh, the language of this location would be pseudorandom function.
Think of like a yes of of with a secret key of this specific location. And if you do it, you can actually you can actually do it using, you know, if you, you, you when you found out J you evaluate proof of J exclusive for A. And this allows you to translate the value stored here to a value stored here. Okay. So there are a couple of limitations. One is it's horrendously inefficient. You have to execute Pierre circuit which is like 6000 M gates inside every memory read.
That's terrible. And the second limitation is have to assume circular security because the pref depends on gobbling, and gobbling depends on PLF. So there was quite a bit of work in in getting rid of this limitation. The idea is to get a binary tree where every node here is a garbled circuit.
And you sort of the idea is you have this value, a z. The next step of the CPU wants to read, and you pass it as a function argument to this garbled circuit that talk to other garbled circuits all the way down to the memory location to pass as an argument. The encoding of a. Okay. And if you do it right, you can sort of do it. And. Uh uh. So you do a bit of work. This sort of a works puzzles a way down and then replenish burnt sort of a circuitry, because you can use the circuitry only once.
Uh, and, uh, then, uh, you use oblivious Ram compiler to compile publicly to private read, uh, whatever that means. You can basically compile, because here's the evaluator. You switch locations, you read, you can sort of a compile your program into another program where region locations still hide which real locations you read. That's a subject for a different talk, but that's basically it. And, um. There was, uh. How much time do I have? Ten minutes.
Okay. So I want to get to applications. So maybe oh, maybe I should skip all of this. This, uh, more recent work that gets it even faster. But for the purpose of time, I want to maybe skip all of this because that's quite involved. Let me. So let me go to here. So, so in this paper, we sort of, uh, uh, improve the overhead to lockscreen parade, right?
Never mind how. And, um, in fact, we actually also showed this way to sort of a very compact way to swap this languages around, to swap keys around. And in fact, in the, uh, two years ago, we also showed how you can create garbled circuits where kind of a function calls could be commutative. You can either execute, you can first execute some function f and then function g. And with the same circuitry you can execute it in reverse order.
You can first execute g inf or f and g and it's, it's um, uh, using tricks called tri state circuits. But I don't have time to do it, but it's sort of a speed things up where this thing is practical. Okay. Because I have only ten minutes. I want to tell you, uh, and there's a lot of activity in garbled circuits beyond random access, conditional branching, malicious security. More than two parties. Blackbox use, uh, only of cryptographic assumptions. Gambling with specific algebraic assumptions.
It's a very rapidly moving field, but I want to sort of switch gears now and tell you about applications. Okay, so two examples. One example is very simple is from almost 11 years ago. The idea is like this. Suppose you have your cell phone on which you want to compute some function, and your cell phone is not powerful enough to compute it.
What you can do is you can give to Amazon a function f, and if you want to write the function f, you can actually give a universal function in the seed s to a pseudorandom generator, which the idea is that from small amount of randomness, you can generate as much randomness as possible. But this f is like, hey, I want to compute this function. And then what you tell Thomson to do is to garble this function into a huge, garbled circuit and hand it over to say, Microsoft Azure Microsoft Azure.
What you do is you take your secret input X, you garble it, and this is just turning every bit into, you know, one of these two keys. And just give this keys to Microsoft Azure which, which evaluates this function f gives you your function back and you just decrypt. You check for every key if it's A0Q1 key. So how much work is this guy doing? Well, he just hints f the functions that he wants to compute to one service.
And then he gets he gets an encoding, you know, just keys to the other service. They sort of do all the heavy lifting, including all that heavy computation. And then he just gets the answer, which is a few keys. And he checks the colour of these keys and he gets an answer. So this is a very cheap alternative to FSI where you can delegate any computation to two clouds. And as long as these two claw clouds are not in collusion with each other, this is secure.
And what I want to leave the time for is the second application called Secure Agent. It's on the internet. Came out only like two months ago, is a paper. Let me tell you what. What's going on here. And because it's a it's a story actually, which I am excited about. So here's Alice and Bob. They have X and Y in typically the way you run MPC is Alice and Bob print two servers on Amazon.
And we assume that Amazon servers, you know, even though we both pay money to Amazon, they're not going to look at our individual accounts. And then you run MPC. There's also kind of a variant of MPC called the active functionalities. Reactive functionalities means that not only can we compute some function, but after this function is computed, we can keep some secret state which is not known, neither to Alice know to Bob.
Right? So it's a secret state. And now we can compute additional functionality which updates sort of its states. And I must stress that this state is not known, neither to Alice, not to Bob. Okay. And not so, uh, what we want. And so motivation was like this. Suppose you want to do AI training, right? So AI training is right. Large language model training on two data sets. If those data sets are big, even without security, it takes 2 to 3 days to train your data on the data set.
So even if using the most efficient MPC, if you want to do it securely, you know, let's say it's a 300 times slower, you're not going to wait half a year to to do your training. So what is the alternative? And the third initiative that we came up with is like this. We are going to create an MPC that simulates a virtual browser between Alice and Bob. This virtual browser doesn't exist. It's just simulation using secret sharing.
The secret browser is going to first go ProtonMail and create an account where neither. Alice. No. Bob. No. What is the account name? Was a password then this browser, this virtual browser is going to create an account on Amazon such that the login credentials, the login name, the password, everything is not. No, neither to Alice, not to Bob. It's kind of secret shared between the two of them.
And then this virtual browser is going to create the VM virtual machine, which will say, if both of you send me the same instructions on the data, I will compute it and then give you both the results and the actually and they actually showed that this is possible to do. How do you do it. Well. Let's say it's Alice who connects to Amazon. So what we do inside this NPC is we actually simulate the virtual browser, including TLS encryption.
And so what comes out from this MP from this NPC is still this traffic which is encrypted as if it's somebody sitting on the outside that goes from Alice to the Amazon. And because it's TLS encrypted traffic, Alice looks at this traffic that comes out from the MP. I have no idea what's going on. It's just TLS traffic, right? TLS traffic is kind of, uh, a traffic between you and your bank. So that and this drop in the middle cannot understand it. So we simulate it inside MBC, the TLS traffic.
So what comes up is already is encrypted with the keys that are shared between Alice and Bob. So what Alice traffics Thomas, um, is basically already completely encrypted. You know, standard TLS traffic. And so even if it tries to intervene, it cannot do it. And so what we created is actually kind of where a virtual virtual clean room. But the who control this clean room. You and I know Amazon. We can run any sets of rules or whatever it is.
And because this is done where we first create this, uh, VM virtual VM, we're not you and not I know the credentials. We can have this VM room run, let's say machine learning training in a clear because. Right. Just by by let's say I have lost my data to Amazon. You upload your data to Amazon, we create two links and then create this virtual build this virtual machine. Hey uh look at these two links. Do the computation, do the training that's done in a clear.
But because neither you nor me have access to this virtual account, it's basically as if it's done in secure computation. And so here we are sort of a cryptography on its head. And we created out of cryptography this virtual, uh, um, uh, accounts that neither you nor I can access, but jointly we can control. Okay. So conclusions protocol, uh, protocol for part is not so features of MPC protocol for parties to interact open only the output and nothing else.
But it's quite powerful, as I have seen. If I. As I have shown you, it doesn't release faster, uh, corpus of data like, uh, you know, differential privacy. It basically outputs the exact value. Highly controlled release. It's simulates virtual and play for we this almost broker no fuzzing or noise. Right. It's distinct from, uh, other privacy mechanism like anonymity in differential privacy. I believe there was a talk here about differential privacy. So you guys know all about it.
But the point about MPC is that you can combine differential privacy and other techniques with MPC. So those are orthogonal issues and you can combine them together. And it's a very active research area both in theory and practice. Uh, the last example is to illustrate that MPC is a great API because you can run cryptography in general to create this virtual enclave.
So virtual accounts where Thomas and it looks like a regular account, but in reality is controlled by you and me together with neither of us have access to it. And as are many Start-Ups, it's a rapidly evolving field, and I think I finished on time. So let me stop here and take questions.