1
00:00:01,170 --> 00:00:05,310
[Auto-generated transcript. Edits may have been applied for clarity.]
So if you haven't.

2
00:00:14,510 --> 00:00:17,329
Uh, welcome, everybody, to this term stretching lecture.

3
00:00:17,330 --> 00:00:24,260
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.

4
00:00:24,260 --> 00:00:27,620
And this early, um, figure in the theory of science.

5
00:00:28,100 --> 00:00:34,399
So before I introduce our excellent speaker, I want to thank our sponsors, Oxford Asset Management.

6
00:00:34,400 --> 00:00:37,760
They've been sponsoring this series since 2015.

7
00:00:38,090 --> 00:00:43,920
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.

8
00:00:43,940 --> 00:00:47,360
You, um, are encouraged to do that after good talk.

9
00:00:47,360 --> 00:00:51,530
The coffee you think is a table somewhere. Um, so please do that.

10
00:00:52,220 --> 00:00:59,360
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.

11
00:00:59,390 --> 00:01:05,450
But I happen to know that rafting, like me, kind of also is very happy to have questions in the middle.

12
00:01:05,450 --> 00:01:10,220
So don't be shy. If you feel like asking questions earlier, that's fine.

13
00:01:11,090 --> 00:01:14,900
Okay. Um, and then we'll do the usual thing with the mics at the end.

14
00:01:15,590 --> 00:01:19,850
Okay. So it's my new really great pleasure to introduce Rafael Ostrovsky.

15
00:01:20,090 --> 00:01:24,200
Oh not yet please, not yet. Uh, I'll do that. Thank you.

16
00:01:25,360 --> 00:01:35,030
It's my pleasure to introduce Rafael Ostrovsky, um, who, uh, is a distinguished, uh, professor of mathematics and computer science at UCLA.

17
00:01:35,420 --> 00:01:39,800
And I think many of us in this room know him from his foundational work,

18
00:01:40,130 --> 00:01:45,350
both in cryptography in that area and also more broadly on theoretical computer science.

19
00:01:45,800 --> 00:01:49,940
Uh, but I wanted to tell you some facts about him that you might not know.

20
00:01:50,450 --> 00:01:58,110
Um, so, uh, he's also got a huge kind of practical career as well, about 16 patents.

21
00:01:58,580 --> 00:02:02,690
And, um, he's got a bunch of fellowships. And so I'm just going to name a few of them.

22
00:02:03,050 --> 00:02:09,830
So because I work with the ACM and we theatrically the American Association for the Advancement of Science,

23
00:02:09,980 --> 00:02:16,190
and also proof that I want to see are um, which is a fractional cryptology research organisation.

24
00:02:16,610 --> 00:02:20,390
I thought I'd select two of his many prizes to talk to you about.

25
00:02:20,930 --> 00:02:25,760
So he's the recipient of the RSA Prize in 2018,

26
00:02:26,420 --> 00:02:34,820
and the citation says that he's awarded the prize for contributions to the theory and new variants of secure multi-party computation.

27
00:02:35,480 --> 00:02:42,860
And another, another really prestigious prize is the um 2022 Bechtel Award of the Entrepreneur Computer Society,

28
00:02:43,250 --> 00:02:48,440
and their prize was for visionary contributions to computer security theory and practice,

29
00:02:48,830 --> 00:02:54,740
including forcing new cloud vulnerabilities and then funding for corresponding novel solutions.

30
00:02:55,010 --> 00:02:59,480
So we're really lucky to have Rossi here, and I'm very glad to introduce.

31
00:03:08,450 --> 00:03:11,840
Thank you so much, Leslie. It's an honour to be here.

32
00:03:12,980 --> 00:03:16,730
Um, and without further ado, let let me get started.

33
00:03:17,450 --> 00:03:26,710
So, um. Uh, okay.

34
00:03:27,370 --> 00:03:35,770
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.

35
00:03:36,720 --> 00:03:46,100
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?

36
00:03:46,110 --> 00:03:50,580
So you have some data. I have some data and we jointly want to compute on it.

37
00:03:50,910 --> 00:03:59,370
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.

38
00:03:59,370 --> 00:04:03,210
I want to sell it. I don't want to show it to anyone. I want to redacted.

39
00:04:03,510 --> 00:04:06,870
On the other hand, in order for data to be useful, we want to analyse it.

40
00:04:06,870 --> 00:04:14,130
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.

41
00:04:14,550 --> 00:04:21,270
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.

42
00:04:21,870 --> 00:04:30,540
Uh, reproducibility of scientific experiments on private data, genetic analysis, uh, without revealing your, um, DNA.

43
00:04:31,020 --> 00:04:39,419
Health care providers, uh, sharing, you know, patient data, longitudinal studies of various forms social, economic,

44
00:04:39,420 --> 00:04:46,920
educational, uh, logistics, fraud detection, private machine learning, fintech applications, you name it.

45
00:04:47,900 --> 00:04:56,300
And this leads us to a general question, which is can we compute privately owned data sets and by data sets?

46
00:04:56,360 --> 00:05:00,260
What I mean is really siloed data sets that you and I and other people have,

47
00:05:00,500 --> 00:05:04,310
but we are not willing to completely share with each other for a variety of reasons.

48
00:05:04,910 --> 00:05:12,140
And so here's an outline of the talk. I'll talk about secure computations very broadly and what it means.

49
00:05:12,650 --> 00:05:16,700
Then I'll tell you kind of a high level alternative.

50
00:05:16,910 --> 00:05:22,970
You know, it's just one of the many techniques I will tell you about alternatives to secure computation.

51
00:05:23,390 --> 00:05:28,310
And then we'll sort of we get to the main course of this lecture which is garbled circuits.

52
00:05:28,820 --> 00:05:35,140
And then I want to discuss actually two specific examples of the two systems.

53
00:05:35,150 --> 00:05:38,370
One is sort of a was built almost ten years ago.

54
00:05:38,390 --> 00:05:46,250
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.

55
00:05:46,640 --> 00:05:52,460
So first it will be sort of a very broad discussions and fairly technical discussion on garbled circuits.

56
00:05:52,700 --> 00:06:01,529
So let's start with secure computation. So secure computations and players and they all have some secret input.

57
00:06:01,530 --> 00:06:05,130
Think of it as a data sets and they want to compute some function.

58
00:06:05,490 --> 00:06:12,390
If Churchill would be around. It's actually easy to do. We all trust Winston, so we all give our inputs to Winston.

59
00:06:12,540 --> 00:06:16,980
Winston computes this function f and just gives the output to everyone.

60
00:06:17,250 --> 00:06:25,020
And because he is incorruptible and completely trusted, uh, well, at least that's what we believe.

61
00:06:25,260 --> 00:06:29,639
Then basically, he's not going to tell anyone else what their private inputs are.

62
00:06:29,640 --> 00:06:36,629
He's just going to announce the result. Okay. And so secure multi-party computation says, well, we don't have Winston around.

63
00:06:36,630 --> 00:06:47,670
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?

64
00:06:47,970 --> 00:06:54,540
In other words, um, we similarly distrusted third party, even though the trusted third party does not exist.

65
00:06:54,540 --> 00:06:59,400
We through sending messages back and forth, we want to simulate to say, deal functionality.

66
00:06:59,790 --> 00:07:06,929
Winston. Um, and you can think of it as a virtual enclave, simulated almost dealer or whatever you want to call it.

67
00:07:06,930 --> 00:07:11,280
Uh, so please simulate this virtual dealer that doesn't exist.

68
00:07:11,700 --> 00:07:17,220
And it also guarantees robustness against, uh, collusion, cheating, what have you.

69
00:07:17,340 --> 00:07:21,210
Okay. So that's basically the goal of multi-party computation.

70
00:07:21,510 --> 00:07:29,340
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.

71
00:07:29,910 --> 00:07:35,100
Let's actually concentrate on a two party case. Right now there's only two players, Alice and Bob.

72
00:07:35,460 --> 00:07:38,520
And again, let's look at just a few examples.

73
00:07:39,330 --> 00:07:44,550
Let's start with a very simple example which is uh an XOR function.

74
00:07:44,760 --> 00:07:48,839
Right. So let's say and by the way XOR is just bits right.

75
00:07:48,840 --> 00:07:52,890
It's zero and one. And XOR is just some modulo two.

76
00:07:53,190 --> 00:07:59,880
So the two players just want to compute uh sum modulo two uh of the individual bits.

77
00:08:00,480 --> 00:08:03,480
How can they do it. How can Alice and Bob do it?

78
00:08:14,910 --> 00:08:19,690
As they just tell each other the inputs. Why is this okay?

79
00:08:20,080 --> 00:08:27,310
Well, let's just think of what happens. Winston takes this to be its exclusive forces together and gives back to both players.

80
00:08:27,610 --> 00:08:33,970
Now that you know the output of the function, which is the sum modulo, do two and I know my own input.

81
00:08:34,210 --> 00:08:38,140
Of course I know you input. I just subtract my bit from the sum.

82
00:08:38,140 --> 00:08:43,290
That's your bit. So this is a case where they can just talk freely.

83
00:08:43,300 --> 00:08:44,440
They don't need Winston.

84
00:08:44,440 --> 00:08:53,710
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.

85
00:08:54,780 --> 00:09:01,920
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.

86
00:09:02,490 --> 00:09:09,000
It's everything else that's supposed to be hidden. Okay, so for XOR, they can just show us the inputs.

87
00:09:09,030 --> 00:09:13,410
It's nothing interesting to do here. What about the name function?

88
00:09:14,500 --> 00:09:19,220
Can. They just freely tell the inputs to each other.

89
00:09:22,940 --> 00:09:30,050
Depends on the input. Exactly. So if I have a zero, can I tell use that I have a zero?

90
00:09:31,240 --> 00:09:35,560
No. Right? Because maybe there's a guy has a zero and then I should keep mum.

91
00:09:35,980 --> 00:09:39,730
And if the other guy has zero, of course it does. The guy has one.

92
00:09:39,880 --> 00:09:47,560
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.

93
00:09:47,950 --> 00:09:51,690
Zero. Um. And. But who speaks first?

94
00:09:51,760 --> 00:09:58,839
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.

95
00:09:58,840 --> 00:10:02,530
They have zero in the chance that does.

96
00:10:02,530 --> 00:10:06,100
A guy also has a zero. And then I don't want to say if my input is A01.

97
00:10:06,640 --> 00:10:11,230
And um, right. So that's a really problem with an end function.

98
00:10:11,680 --> 00:10:14,829
And then more generally, what about arbitrary Boolean circuit.

99
00:10:14,830 --> 00:10:20,889
Right. You have some complicated function. Maybe something about the input leaks but not everything.

100
00:10:20,890 --> 00:10:26,920
And now how can they compute it. So and and more generally we'll discuss it today as well.

101
00:10:27,070 --> 00:10:32,500
What about arbitrary programs. You know written in C plus plus Java have recursion.

102
00:10:32,920 --> 00:10:35,920
Uh, you know, pointer jumping, what have you.

103
00:10:36,360 --> 00:10:39,580
Um, how can we do this? Okay.

104
00:10:40,330 --> 00:10:46,990
And what I'm going to talk about today is some recent talks, uh, recent advances on two party computation.

105
00:10:47,410 --> 00:10:51,430
Originally I was planning to talk also about multiparty, but they realised there is no time.

106
00:10:51,550 --> 00:10:54,970
Okay, so before we go there, what are the alternatives?

107
00:10:54,970 --> 00:11:01,240
Right. So multi-party computation is all about the secure computation that simulates Winston.

108
00:11:01,630 --> 00:11:07,870
And what are the alternatives that we have. And I just want to cover it uh because the alternatives.

109
00:11:08,200 --> 00:11:12,220
So what is the alternative. One is trusted platform module right.

110
00:11:12,550 --> 00:11:16,720
SGX of the vault and what have you. This is a piece of trusted hardware.

111
00:11:17,110 --> 00:11:21,280
And Intel says, hey no one can break into it. And why.

112
00:11:21,280 --> 00:11:26,920
You know, even if it sits on my machine, no one can break into it because it's protected by Intel.

113
00:11:27,100 --> 00:11:37,419
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.

114
00:11:37,420 --> 00:11:44,650
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,

115
00:11:45,040 --> 00:11:49,270
uh, places that that no one can break inside.

116
00:11:49,600 --> 00:12:01,629
Well, that sounds fabulous. But, you know, even 15 days ago, there was an article in the scientific paper from Georgia Tech saying, hey,

117
00:12:01,630 --> 00:12:08,110
if you allowed to instrument your computer with all sorts of sensors around the SGX, you can actually steal the keys.

118
00:12:08,500 --> 00:12:12,850
And in fact, if happens again and again, pretty much every couple of months,

119
00:12:12,850 --> 00:12:18,190
this is, uh, this is messing with us, seeing this, uh, blunder encrypt the keys.

120
00:12:18,190 --> 00:12:22,540
And then there's another, uh, a very recent work called Battering Ram.

121
00:12:22,750 --> 00:12:26,590
In other words, if you are relying on this jokes, you don't sleep well at night.

122
00:12:27,340 --> 00:12:32,620
Um, so. But that's one alternative. But, you know, I like to sleep, so.

123
00:12:32,890 --> 00:12:36,940
Okay. So that's the option is so-called AWS Clean rooms.

124
00:12:37,150 --> 00:12:42,910
So that's a service offered by Amazon. And the idea is that offered for secure collaboration by Amazon.

125
00:12:43,120 --> 00:12:51,340
Two more participants give data to this, uh, Amazon clean rooms and they compute and just give you the result.

126
00:12:52,000 --> 00:13:01,990
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.

127
00:13:02,500 --> 00:13:07,180
And, um, in addition, the screen rooms have very strong restrictions.

128
00:13:07,180 --> 00:13:10,360
What can and cannot be computed. I'll give you one example.

129
00:13:10,480 --> 00:13:16,270
Those of you who heard about private sector intersection, that's a problem where you have an input and I have an input,

130
00:13:16,630 --> 00:13:19,270
like you have a list of names and I have a list of names.

131
00:13:19,270 --> 00:13:24,610
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.

132
00:13:24,880 --> 00:13:29,530
This is not something you can currently do with clean rooms because it's not possible.

133
00:13:29,980 --> 00:13:37,420
It's forbidden in the clean room kind of semantics to reveal, uh, even partial inputs of individual players.

134
00:13:37,600 --> 00:13:41,770
So like PSC, private sir, intersection is not possible in clean rooms.

135
00:13:41,770 --> 00:13:44,770
And there are also some restrictions on purpose.

136
00:13:44,770 --> 00:13:51,550
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.

137
00:13:51,700 --> 00:13:57,400
Right. But that's that's a viable solution. Amazon sells us, you know, for good profit.

138
00:13:57,410 --> 00:14:06,130
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.

139
00:14:06,430 --> 00:14:09,610
So here it's sort of a similar to clean rooms.

140
00:14:10,000 --> 00:14:13,899
And they say, hey give us all your data and trust us, we are secure.

141
00:14:13,900 --> 00:14:15,400
We are completely unbreakable.

142
00:14:15,880 --> 00:14:26,050
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.

143
00:14:26,320 --> 00:14:30,610
Once you give us all your data, we will perform computation for you and just give you, um.

144
00:14:31,490 --> 00:14:32,480
That's what they say.

145
00:14:33,080 --> 00:14:42,230
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.

146
00:14:42,470 --> 00:14:47,840
So not only do you have to trust us that our software has not a single bug,

147
00:14:47,990 --> 00:14:54,559
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.

148
00:14:54,560 --> 00:15:00,670
And employees also are not going to break it, which is um, now you have to trust two entities, right?

149
00:15:00,680 --> 00:15:05,290
Amazon and this cloud providers again. This people.

150
00:15:05,290 --> 00:15:09,009
Snowflake is a is a big company making, you know, billions of dollars.

151
00:15:09,010 --> 00:15:12,520
So I'm not plagiarising I'm saying those alternatives. Okay.

152
00:15:13,300 --> 00:15:18,700
So and the last alternative I want to mention is so-called fully homomorphic encryption.

153
00:15:19,030 --> 00:15:25,290
So given an A so that's a cryptographic primitives which says given an encryption of X public

154
00:15:25,290 --> 00:15:29,499
key encryption of X and encryption a way you can sort of a without having a decryption key,

155
00:15:29,500 --> 00:15:33,370
compute the sum of x and y and multiplication of x and y.

156
00:15:33,880 --> 00:15:37,510
And now you can sort of do it, uh, securely,

157
00:15:37,510 --> 00:15:46,990
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.

158
00:15:47,380 --> 00:15:56,260
And, um, Bob converts his computation into a circuit that just add does addition and multiplication.

159
00:15:56,470 --> 00:15:59,560
It's inefficient, but you can do it with polynomial blow up.

160
00:15:59,860 --> 00:16:05,860
And then Bob computes whatever function he wants to do and then gives back the encryption of the answer back.

161
00:16:06,220 --> 00:16:09,790
And that is decrypts. So that's certainly a possibility.

162
00:16:09,790 --> 00:16:13,840
And in fact it's a possibility that many people in US government are excited about.

163
00:16:14,170 --> 00:16:20,499
The problem is works only for circuits cannot do random access without touching.

164
00:16:20,500 --> 00:16:25,809
Basically multiplexing touching every encrypted item unless you assume so-called

165
00:16:25,810 --> 00:16:30,220
indistinguishable function and then distinguish ability of escalation,

166
00:16:30,610 --> 00:16:35,050
uh, takes, you know, trillions of years to compute a single and, and gate.

167
00:16:35,060 --> 00:16:38,290
So, you know, good luck with that. Um, uh, so.

168
00:16:39,530 --> 00:16:47,999
Currently, it's 2 or 3 orders of magnitude slower even than MPC or DPC, and like some recent benchmarks,

169
00:16:48,000 --> 00:16:55,219
says thousand to 1000 to 3000 times slower and even more expensive if you want malicious security.

170
00:16:55,220 --> 00:16:59,060
I wrote some people on this thing, but it's basically very slow.

171
00:16:59,060 --> 00:17:06,400
And by the way, MPC is about 300 to 1 to a thousand times slower is an insecure computation, right?

172
00:17:06,410 --> 00:17:14,720
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.

173
00:17:15,170 --> 00:17:24,600
And so, so so it's quite expensive. Um, and so, uh, among NPC here, if you want constant bamboo rounds.

174
00:17:24,930 --> 00:17:29,690
The only alternative for so-called garbled circuits, which is a main course.

175
00:17:29,700 --> 00:17:36,600
And so let's dive right into it. But also turn natives that you have even before I get into garbled circuits.

176
00:17:38,030 --> 00:17:42,170
Any questions before I get into the main topic of today's talk?

177
00:17:47,950 --> 00:17:51,220
Okay. Let's proceed. Okay. Garbled circuits.

178
00:17:51,550 --> 00:17:59,020
So let me start kind of slowly and explain what it is. So Garbled circuits involves two players, Gabriela and Evaluator.

179
00:17:59,590 --> 00:18:03,790
And what Gabriela does is he is going to take some for now.

180
00:18:03,790 --> 00:18:09,280
Boolean circuit and assign two cryptographic keys for every wire.

181
00:18:09,520 --> 00:18:17,430
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.

182
00:18:17,500 --> 00:18:22,260
Also original case associated with every wire and no.

183
00:18:22,820 --> 00:18:35,620
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.

184
00:18:35,800 --> 00:18:43,770
Secretly, of course, what he will do is the two keys are kind of secretly labelled as a zero key and a one key.

185
00:18:43,780 --> 00:18:48,429
Let's say zero key is red, and uh, green key is white.

186
00:18:48,430 --> 00:18:51,819
But when he gives it to evaluator, all these keys look alike.

187
00:18:51,820 --> 00:18:55,180
They basically look like, uh, keys. And so. No.

188
00:18:56,270 --> 00:19:04,780
What he is going to prepare is a cryptographic guard, uh, gadget, which, uh, so, so garble up,

189
00:19:04,820 --> 00:19:14,440
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.

190
00:19:14,450 --> 00:19:20,690
So if this is an end gate. And by the way, every key is custom made for a specific keyhole.

191
00:19:20,930 --> 00:19:28,850
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.

192
00:19:29,060 --> 00:19:33,740
And another red key and green key that fits into the right keyhole, but not the left keyhole.

193
00:19:34,130 --> 00:19:42,140
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.

194
00:19:42,140 --> 00:19:47,150
So here I guess that, uh, green key is a one and red key so zero.

195
00:19:47,150 --> 00:19:51,320
So if you have two green keys and you stick it into this little gadget, you unlock,

196
00:19:51,320 --> 00:19:56,629
uh, green key, green output key in all other combinations of a red and green key.

197
00:19:56,630 --> 00:19:59,720
And lock the red key as output red key.

198
00:20:00,020 --> 00:20:06,829
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,

199
00:20:06,830 --> 00:20:12,139
not knowing what they are, you stick it in a gadget, you unlock the gadget and you get some other key.

200
00:20:12,140 --> 00:20:14,630
You have no idea if this key is a 0 or 1.

201
00:20:14,690 --> 00:20:23,210
Okay, so that's a basic building block of of global circuit, which was which in almost 40 years ago came up is.

202
00:20:24,310 --> 00:20:29,470
And so how given this gadget. And we'll see a little bit later how you build this gadget.

203
00:20:29,480 --> 00:20:33,190
But let's assume we have this gadget. How do you do secure computation.

204
00:20:33,610 --> 00:20:37,030
Right. And again here I'm not assuming cheating. Just almost.

205
00:20:37,030 --> 00:20:41,950
But curiously, you know, I don't have time actually to talk about malicious behaviour.

206
00:20:41,950 --> 00:20:46,000
But let's assume no. Just honest but curious behaviour. So what happens is.

207
00:20:47,490 --> 00:20:50,940
Oops. I'm going the wrong way. What happens is like this.

208
00:20:51,330 --> 00:20:59,200
First of all. So if has some inputs to the circuit, let's say the three inputs belong to if and.

209
00:20:59,200 --> 00:21:02,290
This circuit with this gadget was generated by Gabriella.

210
00:21:02,560 --> 00:21:10,660
So this is another primitive called oblivious transfer where if if has secret inputs 110 for every pair of case,

211
00:21:10,660 --> 00:21:17,970
it can select secretly one of the two keys to get without disclosing to Gabriella which key she is getting.

212
00:21:17,980 --> 00:21:25,240
So if her input is 110, she gets, you know, the first, uh uh, green keys, the second green key,

213
00:21:25,240 --> 00:21:32,230
and then the red key and the Gabriella doesn't know for every pair which of the two keys, uh, you've got.

214
00:21:32,950 --> 00:21:41,620
Okay, then also, there's some way to create this gadget, this digital locks such that the right combination unlocks the right key.

215
00:21:42,220 --> 00:21:52,270
And now you can you can do the computation. So, for example, uh, suppose you have two red keys for uh, A and B.

216
00:21:52,270 --> 00:22:03,940
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.

217
00:22:04,270 --> 00:22:07,840
And again, the evaluator says, okay, it's a key. I don't know what colour it is.

218
00:22:07,850 --> 00:22:16,180
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.

219
00:22:17,200 --> 00:22:22,120
But again, there is some gadget to to fit it into this log box and get the key for E.

220
00:22:22,510 --> 00:22:25,600
And then and then you get the result. So what is the procedure?

221
00:22:25,900 --> 00:22:34,840
Using this oblivious transfer is simple E gets evaluated gets here keys that correspond to here.

222
00:22:34,840 --> 00:22:42,670
Input F also gets this um um materials this cryptographic sort of encryption of this digital locks.

223
00:22:43,180 --> 00:22:49,270
And for gerbil, uh, uh, for gerbil s keys, you know, hurry input.

224
00:22:49,270 --> 00:22:52,660
He just hands here one key without any explanation.

225
00:22:52,930 --> 00:22:56,800
Right. And no evaluator can compute to get the right key.

226
00:22:57,010 --> 00:23:01,510
And then if the gerbil also says, oh, by the way, if you got this last key, it's a zero.

227
00:23:01,510 --> 00:23:03,100
And if you got this key, it's a one.

228
00:23:03,370 --> 00:23:11,320
And that's a secure computation where all the intermediate keys, they don't tell to the wallet or what colour they are,

229
00:23:11,470 --> 00:23:17,110
and therefore the evaluator has no clue as I, you know, it's the intermediate values is zero one.

230
00:23:18,010 --> 00:23:23,950
Okay. So now let's actually dive in and see how we can build this gadget.

231
00:23:24,310 --> 00:23:29,380
Okay. So here's an M gate again. And let's assume that h is a hash function.

232
00:23:29,920 --> 00:23:36,940
Uh oh a random oracle. So what we do is we have two keys for zero.

233
00:23:39,510 --> 00:23:44,720
Uh, and we have two keys for input. In practice, also as keys.

234
00:23:44,970 --> 00:23:54,720
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.

235
00:23:54,720 --> 00:24:01,050
So each one of your computers has a chip and it takes 33 clock takes to evaluate this encryption.

236
00:24:01,320 --> 00:24:04,650
It's very fast. That's why it's such an efficient technology.

237
00:24:04,860 --> 00:24:09,450
So you basically you basically, uh, hash or, you know,

238
00:24:09,450 --> 00:24:16,680
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.

239
00:24:17,070 --> 00:24:25,190
And so now if you have, let's say A1 and B1, well you applied here, you get this thing right.

240
00:24:25,200 --> 00:24:29,939
And now if you, if you know how to compute this part, you edit again.

241
00:24:29,940 --> 00:24:34,320
And if you add something modulo two twice it disappears and you get C1 out.

242
00:24:34,890 --> 00:24:41,190
Right. So that's a way that's again original Yao's garbled circuit where this is a way to create,

243
00:24:41,220 --> 00:24:48,030
uh, a table of, of encryptions such that you can decrypt only one row.

244
00:24:48,240 --> 00:24:54,209
And decrypting this one row gets you one of the output keys not knowing which key race.

245
00:24:54,210 --> 00:24:57,660
So of course, to do it properly you have to scramble the row so you don't know, right?

246
00:24:57,660 --> 00:25:01,080
If you just write it, you know 00011011.

247
00:25:01,260 --> 00:25:08,220
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.

248
00:25:08,460 --> 00:25:16,260
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.

249
00:25:16,440 --> 00:25:20,920
Okay. All right. So, uh.

250
00:25:23,910 --> 00:25:29,430
Now the another idea to come up so called a free XOR.

251
00:25:29,430 --> 00:25:32,430
So let me tell you this idea a free XOR is the following idea.

252
00:25:32,730 --> 00:25:37,580
Instead of having two keys on the wire, you create.

253
00:25:37,600 --> 00:25:41,430
So this is k bits and delta is also k bits.

254
00:25:41,760 --> 00:25:47,159
And what you have is that you have a k bit value for zero and the same value.

255
00:25:47,160 --> 00:25:52,319
Bitwise exclusive is delta which is a global parameter for one and delta.

256
00:25:52,320 --> 00:25:55,469
You can keep the same throughout the entire execution.

257
00:25:55,470 --> 00:26:03,090
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.

258
00:26:03,240 --> 00:26:09,990
So as he says B plus delta ob those are k bit strings and k is like 128 bits.

259
00:26:10,170 --> 00:26:13,350
So he cannot figure out what, uh, delta is.

260
00:26:14,280 --> 00:26:21,630
But um, it's actually quite useful because think of what happens for the X0 gate.

261
00:26:22,590 --> 00:26:27,719
Suppose you have uh a or a plus delta and b plus b plus delta.

262
00:26:27,720 --> 00:26:31,950
How do you compute c plus c plus delta. Well you just XOR this two values.

263
00:26:31,980 --> 00:26:40,170
And if you check the right things cancel out and you get a exactly C plus C plus delta and therefore XOR gates.

264
00:26:40,170 --> 00:26:46,740
If you represent your digital circuit as M gates, an XOR gates, XOR gates now don't require any communication.

265
00:26:47,010 --> 00:26:53,969
I just send you and you know, encryption. This table of n bits and x0 bits you just saw in the clear.

266
00:26:53,970 --> 00:27:03,230
And this gives you the right answer. All right. Another thing you can do, actually, before it goes to another thing you can.

267
00:27:05,070 --> 00:27:11,640
Okay. Um, another thing you can do is so called authenticated sharing.

268
00:27:11,850 --> 00:27:23,940
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.

269
00:27:24,660 --> 00:27:29,250
And Gabriella keeps an A and evaluate that keeps a plus delta.

270
00:27:29,250 --> 00:27:35,520
That's is that means a one. And Gabriella knows the delta evaluator doesn't know the delta okay.

271
00:27:35,880 --> 00:27:40,230
And so that's um, that's how you encrypt the things.

272
00:27:40,560 --> 00:27:45,450
Now the other thing you can do is there are two additional tricks.

273
00:27:45,450 --> 00:27:53,580
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.

274
00:27:53,940 --> 00:27:59,340
Well let's make C equal to C is so far just a random string.

275
00:27:59,580 --> 00:28:03,300
Let's actually make it equal to hash of a and b.

276
00:28:04,080 --> 00:28:09,569
And therefore this is zero. Right now we just have to send three ciphertext notes for a ciphertext.

277
00:28:09,570 --> 00:28:13,380
That's that's great. That's that was invented here.

278
00:28:13,860 --> 00:28:19,470
And then it's an additional idea called point and permute in their ideas like this.

279
00:28:19,500 --> 00:28:29,340
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.

280
00:28:30,060 --> 00:28:36,060
And if you make the last bit of delta equal to one, basically this a value and a plus delta value,

281
00:28:36,070 --> 00:28:39,960
the last bit will toggle, one of them will be zero and one of them will be one.

282
00:28:40,290 --> 00:28:46,110
Let's assign it colours right. So the zero let's say will be called you know will be called orange.

283
00:28:46,500 --> 00:28:53,130
And uh, and uh one will be called yellow have nothing to do with the actual logic of the gate.

284
00:28:53,310 --> 00:29:01,990
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,

285
00:29:02,040 --> 00:29:08,730
red key on the white wire, apply edge to this table and you can just colour code for every entry,

286
00:29:09,000 --> 00:29:13,350
which, uh, which combination of this colours you can do.

287
00:29:13,650 --> 00:29:17,820
And therefore you don't need to try different entries. You can just decrypt a single entry.

288
00:29:18,030 --> 00:29:22,590
So this is a so called point and permute. Uh and it's quite useful.

289
00:29:23,370 --> 00:29:27,090
All right. So. Good.

290
00:29:28,290 --> 00:29:33,770
What? And and now I want to bring the main kind of a point of this discussion.

291
00:29:33,780 --> 00:29:37,950
What makes garbled circuits different from fully homomorphic encryption?

292
00:29:38,430 --> 00:29:43,290
And those are the three observations that sort of what drove the last ten years of research.

293
00:29:43,740 --> 00:29:48,300
One of them is that G can selectively reveal semantic value of any wire.

294
00:29:48,600 --> 00:29:57,150
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.

295
00:29:57,540 --> 00:30:01,530
And if this point and permute bit is a one, it's a zero, whatever it is, right?

296
00:30:01,620 --> 00:30:12,239
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?

297
00:30:12,240 --> 00:30:18,870
Why is it A01? This looks quite stupid because you want to hide stuff, but it turns out that this is incredibly powerful,

298
00:30:18,870 --> 00:30:22,510
that you can selectively reveal the values in the circuit.

299
00:30:22,530 --> 00:30:23,310
You'll see why.

300
00:30:24,720 --> 00:30:32,490
Uh, the second observation is that the evaluator can evaluate garbled circuits lazily, even if some portion of the circuits are still blocked.

301
00:30:33,000 --> 00:30:36,930
And the third observation is sort of a kind of a meta observation.

302
00:30:37,170 --> 00:30:44,490
Recall that while labels are strings of k bits, what if we represent this k bits separately as a fresh wires?

303
00:30:44,670 --> 00:30:48,090
So k square bits total that we can selectively decrypt.

304
00:30:48,120 --> 00:30:51,570
In other words you can have a circuit which operates on this case.

305
00:30:51,750 --> 00:31:00,780
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.

306
00:31:01,380 --> 00:31:04,570
Okay. So let's get let's get, um.

307
00:31:05,220 --> 00:31:13,350
Uh, let me illustrate to you why, you know, selectively, uh, decrypting some particular value is is useful.

308
00:31:13,350 --> 00:31:17,270
This is so-called half gate trick. What if there.

309
00:31:18,560 --> 00:31:23,210
Evaluator knows the value on this wire, right?

310
00:31:23,480 --> 00:31:26,840
Then it turns out that you can actually send just one ciphertext.

311
00:31:27,200 --> 00:31:37,460
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.

312
00:31:37,970 --> 00:31:49,820
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.

313
00:31:49,880 --> 00:31:56,570
You already know the output. It's a zero. If you know that this value is true.

314
00:31:56,570 --> 00:32:04,639
So the evaluator has h plus delta. Then given this hint you can compute hash of h plus delta.

315
00:32:04,640 --> 00:32:13,100
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.

316
00:32:13,250 --> 00:32:20,420
You get h away plus a b, and now you also have B, so you have B and you end up with a.

317
00:32:20,750 --> 00:32:24,320
Right. So it's just one ciphertext. You can always compute.

318
00:32:24,800 --> 00:32:31,490
You can always compute basically c plus a b times delta just by this trick.

319
00:32:31,820 --> 00:32:39,980
So that's that's amazing. And now you can actually do two half gates um what you do.

320
00:32:40,580 --> 00:32:43,240
So so this is just an abbreviation.

321
00:32:43,250 --> 00:32:50,210
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.

322
00:32:50,630 --> 00:32:53,959
So now what you do. But you say, wait a minute.

323
00:32:53,960 --> 00:32:57,020
In the end gate you cannot reveal one of the wire.

324
00:32:57,020 --> 00:33:04,580
So I want to have an M gate where both wires are hidden and you sort of a do you introduce additional random variables?

325
00:33:04,970 --> 00:33:12,049
Lambda subway, lambda sub B you reveal, you reveal a lambda sub lambda sub B to the evaluator.

326
00:33:12,050 --> 00:33:17,750
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.

327
00:33:18,230 --> 00:33:23,900
And there's a point this what you reveal is blinded by this random value.

328
00:33:23,900 --> 00:33:34,190
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.

329
00:33:34,190 --> 00:33:40,519
So to also send separately like a cross term and everything sort of a beautifully cancels out and you get,

330
00:33:40,520 --> 00:33:46,200
uh, the end of two wires with just sending two ciphertext.

331
00:33:46,220 --> 00:33:49,820
So this is your kind of a new definition of a y value.

332
00:33:49,940 --> 00:33:52,970
And just by staging sending two ciphertext, you can do it.

333
00:33:53,870 --> 00:33:57,969
All right. So. Let me know.

334
00:33:57,970 --> 00:34:01,990
Star. Uh, star two random access memory.

335
00:34:02,290 --> 00:34:07,509
Right. So the picture now looks like this. So far, it's a virus.

336
00:34:07,510 --> 00:34:13,180
Virus? A sort of a fixed in advance. And what if you want to do random access, right.

337
00:34:13,180 --> 00:34:19,960
You have a CPU that we simulate as a random circuit, and it wants to read and write into this, uh, memory.

338
00:34:20,440 --> 00:34:27,430
And this is a decision which items you read is decided at runtime as you execute the CPU stuff.

339
00:34:27,440 --> 00:34:30,730
So this CPU starts a model, this yells garbled circuits.

340
00:34:31,210 --> 00:34:38,800
But now what happens is you can sort of decrypt and say, hey, I want to read location J, right, reading location J.

341
00:34:38,820 --> 00:34:49,030
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.

342
00:34:49,420 --> 00:34:52,570
What does it mean? G code at runtime.

343
00:34:53,050 --> 00:34:58,920
You know, decrypt runtime j I want to read j, and that means that I want to, uh,

344
00:34:59,050 --> 00:35:04,670
have a value which is stored in this location and somehow translated to is a key,

345
00:35:04,760 --> 00:35:11,740
a key, a plus delta, because this CPU sort of wants to feed the value stored him to the next CPU step.

346
00:35:12,070 --> 00:35:16,090
But the problem is this J is revealed ahead of time. So how can you do it?

347
00:35:16,570 --> 00:35:27,310
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.

348
00:35:27,670 --> 00:35:37,450
It also notes, uh, it also knows that at runtime it will decode some address J and now want to translate it here.

349
00:35:38,140 --> 00:35:47,620
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.

350
00:35:47,620 --> 00:35:52,660
Runtime translate this value of w w plus delta to a.

351
00:35:53,440 --> 00:35:59,079
And so what you do. But but you don't know, uh, what w is that location?

352
00:35:59,080 --> 00:36:10,510
J so, uh, our original idea was to store, uh, the language of this location would be pseudorandom function.

353
00:36:10,510 --> 00:36:17,110
Think of like a yes of of with a secret key of this specific location.

354
00:36:17,500 --> 00:36:22,120
And if you do it, you can actually you can actually do it using, you know,

355
00:36:22,440 --> 00:36:29,620
if you, you, you when you found out J you evaluate proof of J exclusive for A.

356
00:36:29,620 --> 00:36:34,480
And this allows you to translate the value stored here to a value stored here.

357
00:36:35,430 --> 00:36:40,630
Okay. So there are a couple of limitations. One is it's horrendously inefficient.

358
00:36:40,650 --> 00:36:47,370
You have to execute Pierre circuit which is like 6000 M gates inside every memory read.

359
00:36:47,400 --> 00:36:55,560
That's terrible. And the second limitation is have to assume circular security because the pref depends on gobbling, and gobbling depends on PLF.

360
00:36:55,830 --> 00:37:00,720
So there was quite a bit of work in in getting rid of this limitation.

361
00:37:01,110 --> 00:37:07,470
The idea is to get a binary tree where every node here is a garbled circuit.

362
00:37:07,860 --> 00:37:12,959
And you sort of the idea is you have this value, a z.

363
00:37:12,960 --> 00:37:19,410
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

364
00:37:19,410 --> 00:37:25,230
garbled circuits all the way down to the memory location to pass as an argument.

365
00:37:25,360 --> 00:37:28,420
The encoding of a. Okay.

366
00:37:28,600 --> 00:37:31,720
And if you do it right, you can sort of do it. And.

367
00:37:32,860 --> 00:37:36,309
Uh uh. So you do a bit of work.

368
00:37:36,310 --> 00:37:45,100
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.

369
00:37:45,580 --> 00:37:56,620
Uh, and, uh, then, uh, you use oblivious Ram compiler to compile publicly to private read, uh, whatever that means.

370
00:37:56,620 --> 00:38:00,690
You can basically compile, because here's the evaluator.

371
00:38:00,900 --> 00:38:02,320
You switch locations, you read,

372
00:38:02,650 --> 00:38:09,640
you can sort of a compile your program into another program where region locations still hide which real locations you read.

373
00:38:10,030 --> 00:38:14,080
That's a subject for a different talk, but that's basically it. And, um.

374
00:38:15,450 --> 00:38:20,610
There was, uh. How much time do I have? Ten minutes.

375
00:38:20,640 --> 00:38:25,860
Okay. So I want to get to applications. So maybe oh, maybe I should skip all of this.

376
00:38:26,190 --> 00:38:31,409
This, uh, more recent work that gets it even faster.

377
00:38:31,410 --> 00:38:37,680
But for the purpose of time, I want to maybe skip all of this because that's quite involved.

378
00:38:38,190 --> 00:38:48,510
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?

379
00:38:48,900 --> 00:39:00,210
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.

380
00:39:00,720 --> 00:39:09,750
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.

381
00:39:09,750 --> 00:39:14,160
You can either execute, you can first execute some function f and then function g.

382
00:39:14,460 --> 00:39:17,850
And with the same circuitry you can execute it in reverse order.

383
00:39:17,850 --> 00:39:26,339
You can first execute g inf or f and g and it's, it's um, uh, using tricks called tri state circuits.

384
00:39:26,340 --> 00:39:30,930
But I don't have time to do it, but it's sort of a speed things up where this thing is practical.

385
00:39:31,290 --> 00:39:32,939
Okay. Because I have only ten minutes.

386
00:39:32,940 --> 00:39:41,340
I want to tell you, uh, and there's a lot of activity in garbled circuits beyond random access, conditional branching, malicious security.

387
00:39:41,670 --> 00:39:47,220
More than two parties. Blackbox use, uh, only of cryptographic assumptions.

388
00:39:47,610 --> 00:39:50,190
Gambling with specific algebraic assumptions.

389
00:39:50,400 --> 00:39:56,670
It's a very rapidly moving field, but I want to sort of switch gears now and tell you about applications.

390
00:39:57,600 --> 00:40:03,690
Okay, so two examples. One example is very simple is from almost 11 years ago.

391
00:40:03,900 --> 00:40:04,960
The idea is like this.

392
00:40:04,970 --> 00:40:11,880
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.

393
00:40:12,180 --> 00:40:19,169
What you can do is you can give to Amazon a function f, and if you want to write the function f,

394
00:40:19,170 --> 00:40:23,970
you can actually give a universal function in the seed s to a pseudorandom generator,

395
00:40:24,300 --> 00:40:29,760
which the idea is that from small amount of randomness, you can generate as much randomness as possible.

396
00:40:30,000 --> 00:40:32,970
But this f is like, hey, I want to compute this function.

397
00:40:33,330 --> 00:40:44,810
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.

398
00:40:44,850 --> 00:40:53,220
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.

399
00:40:53,460 --> 00:41:01,950
And just give this keys to Microsoft Azure which, which evaluates this function f gives you your function back and you just decrypt.

400
00:41:01,950 --> 00:41:06,750
You check for every key if it's A0Q1 key. So how much work is this guy doing?

401
00:41:06,990 --> 00:41:11,190
Well, he just hints f the functions that he wants to compute to one service.

402
00:41:11,520 --> 00:41:17,700
And then he gets he gets an encoding, you know, just keys to the other service.

403
00:41:18,060 --> 00:41:21,950
They sort of do all the heavy lifting, including all that heavy computation.

404
00:41:21,960 --> 00:41:27,180
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.

405
00:41:27,390 --> 00:41:33,480
So this is a very cheap alternative to FSI where you can delegate any computation to two clouds.

406
00:41:33,720 --> 00:41:39,030
And as long as these two claw clouds are not in collusion with each other, this is secure.

407
00:41:40,260 --> 00:41:45,240
And what I want to leave the time for is the second application called Secure Agent.

408
00:41:45,420 --> 00:41:49,380
It's on the internet. Came out only like two months ago, is a paper.

409
00:41:49,890 --> 00:41:55,290
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.

410
00:41:55,650 --> 00:42:05,580
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.

411
00:42:05,970 --> 00:42:12,480
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.

412
00:42:12,750 --> 00:42:18,600
And then you run MPC. There's also kind of a variant of MPC called the active functionalities.

413
00:42:18,930 --> 00:42:25,620
Reactive functionalities means that not only can we compute some function, but after this function is computed,

414
00:42:25,620 --> 00:42:30,839
we can keep some secret state which is not known, neither to Alice know to Bob.

415
00:42:30,840 --> 00:42:37,740
Right? So it's a secret state. And now we can compute additional functionality which updates sort of its states.

416
00:42:37,950 --> 00:42:42,630
And I must stress that this state is not known, neither to Alice, not to Bob.

417
00:42:43,020 --> 00:42:48,290
Okay. And not so, uh, what we want.

418
00:42:48,300 --> 00:42:53,459
And so motivation was like this. Suppose you want to do AI training, right?

419
00:42:53,460 --> 00:42:58,470
So AI training is right. Large language model training on two data sets.

420
00:42:58,800 --> 00:43:05,310
If those data sets are big, even without security, it takes 2 to 3 days to train your data on the data set.

421
00:43:05,580 --> 00:43:11,250
So even if using the most efficient MPC, if you want to do it securely, you know,

422
00:43:11,460 --> 00:43:17,630
let's say it's a 300 times slower, you're not going to wait half a year to to do your training.

423
00:43:17,640 --> 00:43:22,770
So what is the alternative? And the third initiative that we came up with is like this.

424
00:43:23,340 --> 00:43:32,280
We are going to create an MPC that simulates a virtual browser between Alice and Bob.

425
00:43:32,760 --> 00:43:36,900
This virtual browser doesn't exist. It's just simulation using secret sharing.

426
00:43:37,200 --> 00:43:44,099
The secret browser is going to first go ProtonMail and create an account where neither.

427
00:43:44,100 --> 00:43:46,499
Alice. No. Bob. No. What is the account name?

428
00:43:46,500 --> 00:43:56,320
Was a password then this browser, this virtual browser is going to create an account on Amazon such that the login credentials,

429
00:43:56,340 --> 00:44:01,050
the login name, the password, everything is not. No, neither to Alice, not to Bob.

430
00:44:01,200 --> 00:44:03,780
It's kind of secret shared between the two of them.

431
00:44:04,230 --> 00:44:15,030
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,

432
00:44:15,030 --> 00:44:22,649
I will compute it and then give you both the results and the actually and they actually showed that this is possible to do.

433
00:44:22,650 --> 00:44:28,440
How do you do it. Well. Let's say it's Alice who connects to Amazon.

434
00:44:28,710 --> 00:44:36,060
So what we do inside this NPC is we actually simulate the virtual browser, including TLS encryption.

435
00:44:36,300 --> 00:44:42,420
And so what comes out from this MP from this NPC is still this traffic which is encrypted

436
00:44:42,660 --> 00:44:47,430
as if it's somebody sitting on the outside that goes from Alice to the Amazon.

437
00:44:47,670 --> 00:44:52,860
And because it's TLS encrypted traffic, Alice looks at this traffic that comes out from the MP.

438
00:44:53,220 --> 00:45:01,460
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.

439
00:45:01,470 --> 00:45:07,860
So that and this drop in the middle cannot understand it. So we simulate it inside MBC, the TLS traffic.

440
00:45:07,860 --> 00:45:13,140
So what comes up is already is encrypted with the keys that are shared between Alice and Bob.

441
00:45:13,350 --> 00:45:18,060
So what Alice traffics Thomas, um, is basically already completely encrypted.

442
00:45:18,090 --> 00:45:24,300
You know, standard TLS traffic. And so even if it tries to intervene, it cannot do it.

443
00:45:24,780 --> 00:45:32,040
And so what we created is actually kind of where a virtual virtual clean room.

444
00:45:32,400 --> 00:45:37,020
But the who control this clean room. You and I know Amazon.

445
00:45:37,200 --> 00:45:40,080
We can run any sets of rules or whatever it is.

446
00:45:40,410 --> 00:45:50,580
And because this is done where we first create this, uh, VM virtual VM, we're not you and not I know the credentials.

447
00:45:51,000 --> 00:45:57,299
We can have this VM room run, let's say machine learning training in a clear because.

448
00:45:57,300 --> 00:46:00,660
Right. Just by by let's say I have lost my data to Amazon.

449
00:46:00,660 --> 00:46:06,210
You upload your data to Amazon, we create two links and then create this virtual build this virtual machine.

450
00:46:06,390 --> 00:46:11,940
Hey uh look at these two links. Do the computation, do the training that's done in a clear.

451
00:46:12,090 --> 00:46:19,440
But because neither you nor me have access to this virtual account, it's basically as if it's done in secure computation.

452
00:46:19,770 --> 00:46:23,069
And so here we are sort of a cryptography on its head.

453
00:46:23,070 --> 00:46:33,480
And we created out of cryptography this virtual, uh, um, uh, accounts that neither you nor I can access, but jointly we can control.

454
00:46:34,440 --> 00:46:47,110
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.

455
00:46:47,160 --> 00:46:49,690
But it's quite powerful, as I have seen. If I.

456
00:46:49,740 --> 00:46:58,470
As I have shown you, it doesn't release faster, uh, corpus of data like, uh, you know, differential privacy.

457
00:46:58,710 --> 00:47:03,000
It basically outputs the exact value. Highly controlled release.

458
00:47:03,330 --> 00:47:08,760
It's simulates virtual and play for we this almost broker no fuzzing or noise.

459
00:47:09,510 --> 00:47:16,260
Right. It's distinct from, uh, other privacy mechanism like anonymity in differential privacy.

460
00:47:16,590 --> 00:47:21,090
I believe there was a talk here about differential privacy. So you guys know all about it.

461
00:47:21,300 --> 00:47:27,330
But the point about MPC is that you can combine differential privacy and other techniques with MPC.

462
00:47:27,390 --> 00:47:31,470
So those are orthogonal issues and you can combine them together.

463
00:47:32,130 --> 00:47:36,600
And it's a very active research area both in theory and practice.

464
00:47:37,140 --> 00:47:48,900
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.

465
00:47:48,900 --> 00:47:53,100
So virtual accounts where Thomas and it looks like a regular account,

466
00:47:53,490 --> 00:47:58,410
but in reality is controlled by you and me together with neither of us have access to it.

467
00:47:58,890 --> 00:48:04,590
And as are many Start-Ups, it's a rapidly evolving field, and I think I finished on time.

468
00:48:04,590 --> 00:48:07,320
So let me stop here and take questions.