Latest / Strachey Lectures / Advances in Garbled Circuits

Transcript

Advances in Garbled Circuits · Strachey Lectures

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