WEBVTT

1
00:00:04.040 --> 00:00:06.500 A:middle L:90%
I can talk pretty loud and I can also encourage

2
00:00:06.500 --> 00:00:08.509 A:middle L:90%
people sitting in the way back to come closer.

3
00:00:08.869 --> 00:00:12.279 A:middle L:90%
There is plenty of space near to the front and

4
00:00:12.279 --> 00:00:14.179 A:middle L:90%
you can still do your email and stuff on your

5
00:00:14.179 --> 00:00:17.260 A:middle L:90%
laptops if you're close to the front. Um So

6
00:00:18.440 --> 00:00:20.829 A:middle L:90%
at least until until they have the mic working.

7
00:00:21.739 --> 00:00:25.690 A:middle L:90%
So so the way secure computation is traditionally introduced is

8
00:00:25.690 --> 00:00:29.699 A:middle L:90%
talking about this millionaire's problem where you have to millionaires

9
00:00:29.699 --> 00:00:32.340 A:middle L:90%
who want to figure out who's richer but don't want

10
00:00:32.340 --> 00:00:34.729 A:middle L:90%
to disclose their net worth to the other party.

11
00:00:34.740 --> 00:00:36.719 A:middle L:90%
Grad students tend to have a hard time relating to

12
00:00:36.719 --> 00:00:39.369 A:middle L:90%
that and ask questions like well what happens if both

13
00:00:39.380 --> 00:00:42.600 A:middle L:90%
parties have zero as their input? Um So that

14
00:00:42.609 --> 00:00:45.859 A:middle L:90%
example I like to use is genetic dating which um

15
00:00:45.869 --> 00:00:48.859 A:middle L:90%
is a more interesting example I think where you've got

16
00:00:49.340 --> 00:00:53.000 A:middle L:90%
two people that meet in a bar or some other

17
00:00:53.000 --> 00:00:57.170 A:middle L:90%
kind of establishment. Um And before engaging in any

18
00:00:57.170 --> 00:01:00.000 A:middle L:90%
archaic courtship rituals, they want to figure out if

19
00:01:00.000 --> 00:01:02.869 A:middle L:90%
they're a good genetic match. So they have a

20
00:01:02.869 --> 00:01:06.629 A:middle L:90%
little program on their android devices or their iphones.

21
00:01:06.640 --> 00:01:07.549 A:middle L:90%
If they don't have the same device, they're already

22
00:01:07.549 --> 00:01:10.459 A:middle L:90%
in big trouble. But let's assume they're at least

23
00:01:10.459 --> 00:01:14.370 A:middle L:90%
compatible enough to have the same mobile platform. Um

24
00:01:14.379 --> 00:01:17.420 A:middle L:90%
And they also have their genome encoded on their device.

25
00:01:17.430 --> 00:01:19.170 A:middle L:90%
So what they want to do is run some

26
00:01:19.170 --> 00:01:22.430 A:middle L:90%
protocol that's going to find out if they're compatible and

27
00:01:22.430 --> 00:01:25.010 A:middle L:90%
it will do something like tell them they could have

28
00:01:25.019 --> 00:01:29.140 A:middle L:90%
healthy offspring or it might give them a warning that

29
00:01:29.140 --> 00:01:34.750 A:middle L:90%
they shouldn't reproduce if they share common recessive diseases.

30
00:01:34.239 --> 00:01:37.129 A:middle L:90%
But they want to do this without disclosing their whole

31
00:01:37.129 --> 00:01:40.629 A:middle L:90%
genome. If they disclose their whole genome. Well

32
00:01:40.629 --> 00:01:44.040 A:middle L:90%
that might leak a lot of other information about themselves,

33
00:01:44.040 --> 00:01:47.480 A:middle L:90%
their propensity to alcoholism, other things about their

34
00:01:47.480 --> 00:01:49.260 A:middle L:90%
their background that they don't want to reveal yet.

35
00:01:49.640 --> 00:01:51.150 A:middle L:90%
They just want to be able to run this protocol

36
00:01:51.150 --> 00:01:55.180 A:middle L:90%
and get the output. If you don't believe me,

37
00:01:55.180 --> 00:01:57.299 A:middle L:90%
this is gonna be common pretty soon. Um

38
00:01:57.310 --> 00:02:01.920 A:middle L:90%
So this is a graph showing the cost of sequencing

39
00:02:01.930 --> 00:02:07.430 A:middle L:90%
the human genome. Uh going from 2001 up to

40
00:02:07.439 --> 00:02:09.960 A:middle L:90%
2010. I don't have the latest numbers here.

41
00:02:10.659 --> 00:02:15.039 A:middle L:90%
And if you look at that first the dark line

42
00:02:15.189 --> 00:02:17.199 A:middle L:90%
and uh my my scribbling tool is broken. So

43
00:02:17.199 --> 00:02:20.639 A:middle L:90%
hopefully you can see without me me scrambling. Um

44
00:02:20.650 --> 00:02:23.129 A:middle L:90%
It was going pretty well with Moore's Law doubling about

45
00:02:23.139 --> 00:02:30.000 A:middle L:90%
every 18 months um until 2007. And then here's

46
00:02:30.000 --> 00:02:34.449 A:middle L:90%
what happened after 2007. So it went crazy like

47
00:02:34.680 --> 00:02:37.460 A:middle L:90%
improving at a much faster rate than Moore's Law.

48
00:02:37.840 --> 00:02:39.050 A:middle L:90%
And now you can buy machines like this one that

49
00:02:39.050 --> 00:02:43.020 A:middle L:90%
has like a little ipod hookup that will sequence the

50
00:02:43.020 --> 00:02:46.090 A:middle L:90%
genome. Um And so to make sure it's clear

51
00:02:46.090 --> 00:02:49.530 A:middle L:90%
sort of what kind of impact that curve has on

52
00:02:49.530 --> 00:02:52.189 A:middle L:90%
real dollars and real figures. So here's a table

53
00:02:52.189 --> 00:02:55.020 A:middle L:90%
showing the cost Going down to 2009. Getting down

54
00:02:55.020 --> 00:02:59.319 A:middle L:90%
to $1,500. The actual cost of sequencing a genome

55
00:02:59.919 --> 00:03:04.120 A:middle L:90%
it's much lower today. But it starts at

56
00:03:04.120 --> 00:03:07.620 A:middle L:90%
57 million. And I've blacked out what year it

57
00:03:07.620 --> 00:03:10.729 A:middle L:90%
was 57 million to get down to 1500 in 2009.

58
00:03:10.740 --> 00:03:17.479 A:middle L:90%
Uh any guesses what year that was sorry,

59
00:03:17.490 --> 00:03:24.449 A:middle L:90%
closed to guests. 2000 2000. Any advances on

60
00:03:24.449 --> 00:03:31.819 A:middle L:90%
2000? Yeah. 2007. Right. So There

61
00:03:31.819 --> 00:03:37.599 A:middle L:90%
are not many things that cost $50 million 2007 that

62
00:03:37.599 --> 00:03:39.900 A:middle L:90%
cost a few $100 today. Um So this is

63
00:03:39.900 --> 00:03:42.750 A:middle L:90%
pretty crazy. You can also see how many authors

64
00:03:43.240 --> 00:03:46.250 A:middle L:90%
typical papers and biology have. Um So there's lots

65
00:03:46.250 --> 00:03:49.979 A:middle L:90%
and lots of people working on this. Um So

66
00:03:49.990 --> 00:03:51.659 A:middle L:90%
this is gonna happen right and there are lots of

67
00:03:51.659 --> 00:03:53.900 A:middle L:90%
things that we might be able to do with genomes

68
00:03:53.900 --> 00:03:54.569 A:middle L:90%
and so far at least medically it's been kind of

69
00:03:54.569 --> 00:03:59.460 A:middle L:90%
disappointing that all the hype about the human genome project

70
00:03:59.939 --> 00:04:02.169 A:middle L:90%
um has not produced a wealth of great new medicines

71
00:04:02.439 --> 00:04:04.710 A:middle L:90%
yet. But there is this hope that it will

72
00:04:04.710 --> 00:04:08.879 A:middle L:90%
lead to personalized medicine where instead of having to try

73
00:04:08.889 --> 00:04:10.969 A:middle L:90%
six drugs until you find out the one that works

74
00:04:10.969 --> 00:04:12.889 A:middle L:90%
for a particular patient, you should be able to

75
00:04:12.889 --> 00:04:15.530 A:middle L:90%
take your genome to the doctor and they can do

76
00:04:15.530 --> 00:04:17.240 A:middle L:90%
some analysis of it some comparison with the data the

77
00:04:17.240 --> 00:04:19.959 A:middle L:90%
pharmaceutical company might have And figure out which drug is

78
00:04:19.959 --> 00:04:23.470 A:middle L:90%
right for you. Or maybe craft one. If

79
00:04:23.480 --> 00:04:29.019 A:middle L:90%
if you're particular profile doesn't match that drug we might

80
00:04:29.019 --> 00:04:30.089 A:middle L:90%
have things like the genetic dating. You can decide

81
00:04:30.089 --> 00:04:32.459 A:middle L:90%
whether that belongs on the good side or the bad

82
00:04:32.459 --> 00:04:35.529 A:middle L:90%
side. Um But all this data could also be

83
00:04:35.529 --> 00:04:39.430 A:middle L:90%
misused. Um And sort of the extreme example of

84
00:04:39.430 --> 00:04:41.500 A:middle L:90%
misuse is this movie that some of you may have

85
00:04:41.500 --> 00:04:44.060 A:middle L:90%
seen. But there are lots of other ways that

86
00:04:44.060 --> 00:04:46.029 A:middle L:90%
could be misused in terms of personal privacy. So

87
00:04:46.029 --> 00:04:49.379 A:middle L:90%
what really matters is whether humans keep control over this

88
00:04:49.379 --> 00:04:53.730 A:middle L:90%
data themselves or have to disclose it to large entities

89
00:04:53.730 --> 00:04:56.360 A:middle L:90%
or governments that might abuse that data in some way.

90
00:04:56.839 --> 00:05:00.040 A:middle L:90%
And the promise of secure computation is we can

91
00:05:00.040 --> 00:05:02.430 A:middle L:90%
still get all the useful things like personalized medicine from

92
00:05:02.430 --> 00:05:05.589 A:middle L:90%
this private data without disclosing it. And the idea

93
00:05:05.600 --> 00:05:09.449 A:middle L:90%
is that we have our two parties that want to

94
00:05:09.449 --> 00:05:12.709 A:middle L:90%
compute some function and the inputs to that function they

95
00:05:12.709 --> 00:05:15.259 A:middle L:90%
want to keep private so they have their their genomes

96
00:05:15.639 --> 00:05:16.259 A:middle L:90%
. Um Could be some other private data. There

97
00:05:16.259 --> 00:05:19.670 A:middle L:90%
are lots of other motivating examples for this. But

98
00:05:19.670 --> 00:05:21.240 A:middle L:90%
what they want to do is compute some function.

99
00:05:21.579 --> 00:05:26.250 A:middle L:90%
Get the output of that function without revealing anything other

100
00:05:26.250 --> 00:05:29.019 A:middle L:90%
than the output to the other party. If they

101
00:05:29.019 --> 00:05:31.220 A:middle L:90%
all trusted some third party to do everything for them

102
00:05:31.220 --> 00:05:32.620 A:middle L:90%
. This would be easy. You just give all

103
00:05:32.620 --> 00:05:34.850 A:middle L:90%
your data to third party. The third party does

104
00:05:34.850 --> 00:05:38.410 A:middle L:90%
the computation and gives you the result and you're trusting

105
00:05:38.410 --> 00:05:39.910 A:middle L:90%
google or the N. S. A. Or

106
00:05:39.910 --> 00:05:42.920 A:middle L:90%
whoever you really trust with all your data. Um

107
00:05:42.930 --> 00:05:45.430 A:middle L:90%
This assumes that both people can agree on a third

108
00:05:45.430 --> 00:05:48.459 A:middle L:90%
party that they trust completely. Um and has lots

109
00:05:48.459 --> 00:05:51.720 A:middle L:90%
of drawbacks if you don't really trust some other party

110
00:05:54.240 --> 00:05:56.870 A:middle L:90%
google might already have all your data anyway. But

111
00:05:56.879 --> 00:06:00.670 A:middle L:90%
assuming they don't here lots of advantages to be able

112
00:06:00.670 --> 00:06:02.610 A:middle L:90%
to doing this without trusting some other parts. Um

113
00:06:02.610 --> 00:06:05.060 A:middle L:90%
so that's the goal of secure computation and it turns

114
00:06:05.060 --> 00:06:08.720 A:middle L:90%
out there are protocols that can do this that have

115
00:06:08.720 --> 00:06:11.259 A:middle L:90%
been known since since the 80s. Um the one

116
00:06:11.259 --> 00:06:12.829 A:middle L:90%
that I'm going to focus on is is called garbled

117
00:06:12.829 --> 00:06:15.230 A:middle L:90%
circuits and the idea is that one party will generate

118
00:06:15.230 --> 00:06:17.439 A:middle L:90%
a circuit so we can turn any computation into the

119
00:06:17.439 --> 00:06:21.860 A:middle L:90%
circuit. Um The other party will evaluate that circuit

120
00:06:23.610 --> 00:06:26.649 A:middle L:90%
and we can do this in a way that doesn't

121
00:06:26.649 --> 00:06:30.980 A:middle L:90%
reveal the inputs and I'll explain briefly how this works

122
00:06:31.439 --> 00:06:33.980 A:middle L:90%
. So this is the protocol that Andrew came up

123
00:06:33.980 --> 00:06:38.660 A:middle L:90%
with and we can think of any normal computation if

124
00:06:38.660 --> 00:06:40.689 A:middle L:90%
we think of circuits, we just have look up

125
00:06:40.689 --> 00:06:43.199 A:middle L:90%
tables right? We have a logic gate, This

126
00:06:43.199 --> 00:06:46.610 A:middle L:90%
is one for should I ask what this is for

127
00:06:46.610 --> 00:06:51.399 A:middle L:90%
to see if people are awake. Okay, good

128
00:06:51.579 --> 00:06:54.550 A:middle L:90%
. This is for and right. So it's just

129
00:06:54.550 --> 00:06:59.110 A:middle L:90%
a look up table normally to implemented and get what

130
00:06:59.110 --> 00:07:00.189 A:middle L:90%
we need to know what the inputs are. Alright

131
00:07:00.199 --> 00:07:02.089 A:middle L:90%
, we need to know what the input started look

132
00:07:02.089 --> 00:07:04.550 A:middle L:90%
up the output and we know what the output is

133
00:07:04.550 --> 00:07:08.120 A:middle L:90%
because that's what the output is, right. Our

134
00:07:08.120 --> 00:07:11.250 A:middle L:90%
goal is to be able to implement an and gate

135
00:07:11.639 --> 00:07:14.670 A:middle L:90%
without knowing what the inputs are and without seeing the

136
00:07:14.670 --> 00:07:16.319 A:middle L:90%
output. So the first step to that would be

137
00:07:16.319 --> 00:07:19.220 A:middle L:90%
well, obviously if we use the semantic values of

138
00:07:19.220 --> 00:07:23.790 A:middle L:90%
zero and 1 to represent inputs, that's not gonna

139
00:07:23.790 --> 00:07:25.860 A:middle L:90%
work. So we've got to use some other values

140
00:07:25.860 --> 00:07:28.480 A:middle L:90%
. So we're going to change those to arbitrary nonsense

141
00:07:29.040 --> 00:07:31.199 A:middle L:90%
. And the party doing the evaluation doesn't need to

142
00:07:31.199 --> 00:07:34.870 A:middle L:90%
know the mapping between the nonsense means zero and the

143
00:07:34.889 --> 00:07:39.269 A:middle L:90%
constant means one. This will just look like arbitrary

144
00:07:39.449 --> 00:07:42.100 A:middle L:90%
strings of bits. Um and we can do the

145
00:07:42.100 --> 00:07:44.790 A:middle L:90%
same thing with the output. Does this solve our

146
00:07:44.790 --> 00:07:46.870 A:middle L:90%
problem, is this enough to be able to execute

147
00:07:46.870 --> 00:07:57.829 A:middle L:90%
the end without revealing the inputs. So what does

148
00:07:57.829 --> 00:08:07.850 A:middle L:90%
the evaluator of such a gate learn? Can you

149
00:08:07.850 --> 00:08:11.290 A:middle L:90%
tell which of the X values represents 1? Yeah

150
00:08:11.360 --> 00:08:13.379 A:middle L:90%
. Right. If you know this is an and

151
00:08:13.379 --> 00:08:15.779 A:middle L:90%
gate and we're assuming that you do that, you

152
00:08:15.779 --> 00:08:18.879 A:middle L:90%
know what function you're computing? Well, three of

153
00:08:18.879 --> 00:08:20.769 A:middle L:90%
the outputs match. Right. Even if we scramble

154
00:08:20.769 --> 00:08:22.069 A:middle L:90%
order, there's always going to be three that represents

155
00:08:22.069 --> 00:08:24.759 A:middle L:90%
zero and one that represents one. So we're going

156
00:08:24.759 --> 00:08:26.949 A:middle L:90%
to know what the output is, that's gonna tell

157
00:08:26.949 --> 00:08:31.569 A:middle L:90%
us when the input was one. Um So this

158
00:08:31.569 --> 00:08:33.139 A:middle L:90%
is not enough but we can't just replace the values

159
00:08:33.139 --> 00:08:37.730 A:middle L:90%
. We've got to also hide the outputs and so

160
00:08:37.730 --> 00:08:39.059 A:middle L:90%
the way to do that is to encrypt them.

161
00:08:39.070 --> 00:08:41.639 A:middle L:90%
So we're gonna encrypt each of these outputs. We

162
00:08:41.639 --> 00:08:43.169 A:middle L:90%
need to encrypt them in a way that the evaluator

163
00:08:43.169 --> 00:08:48.659 A:middle L:90%
can figure out The actual output wire for the one

164
00:08:50.049 --> 00:08:52.299 A:middle L:90%
that it has the inputs for but can't figure out

165
00:08:52.299 --> 00:08:54.940 A:middle L:90%
any others. So the trick to doing that is

166
00:08:54.940 --> 00:08:58.919 A:middle L:90%
we're going to use the input nonsense as the keys

167
00:08:58.919 --> 00:09:03.500 A:middle L:90%
for the encryption. So if we encrypt um If

168
00:09:03.500 --> 00:09:07.029 A:middle L:90%
our inputs are representing zero and 1 we're going to

169
00:09:07.029 --> 00:09:09.860 A:middle L:90%
have one of these lines encrypted using those inputs.

170
00:09:11.399 --> 00:09:13.250 A:middle L:90%
That's the only one that the evaluator will be able

171
00:09:13.250 --> 00:09:16.669 A:middle L:90%
to decrypt to be able to decrypt. You need

172
00:09:16.669 --> 00:09:20.389 A:middle L:90%
both the keys used for encryption. Um and so

173
00:09:20.399 --> 00:09:24.590 A:middle L:90%
the evaluator learns that X0 value but doesn't know what

174
00:09:24.590 --> 00:09:26.320 A:middle L:90%
any of the outputs other outputs are. So it

175
00:09:26.320 --> 00:09:28.769 A:middle L:90%
doesn't learn that there are three that match that because

176
00:09:28.789 --> 00:09:31.860 A:middle L:90%
she can only decrypt one of those. Okay so

177
00:09:33.240 --> 00:09:33.950 A:middle L:90%
we of course also need to scramble the order.

178
00:09:35.340 --> 00:09:37.299 A:middle L:90%
Obviously if we kept everything in the same order that

179
00:09:37.299 --> 00:09:39.539 A:middle L:90%
would reveal it but that's easy. So that's what

180
00:09:39.539 --> 00:09:39.990 A:middle L:90%
we're gonna do. We don't need the other part

181
00:09:39.990 --> 00:09:43.159 A:middle L:90%
of the table. We're gonna have this random permutation

182
00:09:43.639 --> 00:09:48.039 A:middle L:90%
of the four outputs each encrypted with different keys and

183
00:09:48.049 --> 00:09:50.129 A:middle L:90%
the evaluation of the circuit can only evaluate one of

184
00:09:50.129 --> 00:09:52.340 A:middle L:90%
those and it's the one that actually corresponds to the

185
00:09:52.340 --> 00:09:56.360 A:middle L:90%
inputs that you have. So we can do any

186
00:09:56.360 --> 00:10:01.259 A:middle L:90%
gate this way we're gonna evaluate the gate. So

187
00:10:01.360 --> 00:10:05.120 A:middle L:90%
the generator generates the gate picks the nazis, send

188
00:10:05.120 --> 00:10:07.019 A:middle L:90%
it to the evaluator evaluator can decrypt one of those

189
00:10:09.139 --> 00:10:11.159 A:middle L:90%
to decrypt it. The evaluator needs to know these

190
00:10:11.159 --> 00:10:13.710 A:middle L:90%
actual inputs. That's the other problem we've got to

191
00:10:13.710 --> 00:10:18.409 A:middle L:90%
solve. Alice can send the one corresponding her own

192
00:10:18.409 --> 00:10:20.629 A:middle L:90%
input to bob. Right? So she she knows

193
00:10:20.629 --> 00:10:22.250 A:middle L:90%
her own values either zero or one and picks which

194
00:10:22.250 --> 00:10:24.789 A:middle L:90%
one of these to send. Bob. Doesn't know

195
00:10:24.789 --> 00:10:28.070 A:middle L:90%
what it means because they're just arbitrary nazis. But

196
00:10:28.070 --> 00:10:33.059 A:middle L:90%
bob needs to know his input as well. And

197
00:10:33.240 --> 00:10:37.309 A:middle L:90%
Alice can't send bob both B zero and B.

198
00:10:37.309 --> 00:10:39.309 A:middle L:90%
one. What would go wrong if if Alice could

199
00:10:39.309 --> 00:10:48.539 A:middle L:90%
send both inputs to bob. So, if bob

200
00:10:48.539 --> 00:10:52.419 A:middle L:90%
knows both, bob knows one of Alice's values in

201
00:10:52.419 --> 00:10:54.899 A:middle L:90%
both possibilities for representing bob spit. How many of

202
00:10:54.899 --> 00:11:03.289 A:middle L:90%
the lines in the garble table could bob decrypt Yeah

203
00:11:03.299 --> 00:11:05.450 A:middle L:90%
. Two. Alright, that's one. Too many

204
00:11:05.460 --> 00:11:07.860 A:middle L:90%
. Right. If bob could decrypt two lines well

205
00:11:07.860 --> 00:11:09.490 A:middle L:90%
then he can learn if the output for both of

206
00:11:09.490 --> 00:11:13.659 A:middle L:90%
those is zero, then he learns Alice's input.

207
00:11:13.240 --> 00:11:16.259 A:middle L:90%
All right. So, so that's a problem.

208
00:11:16.269 --> 00:11:16.690 A:middle L:90%
So, we need to make sure that bob only

209
00:11:16.690 --> 00:11:20.350 A:middle L:90%
gets one of that inputs corresponding to his own one

210
00:11:20.350 --> 00:11:22.259 A:middle L:90%
of the wire labels corresponding to his own input.

211
00:11:24.740 --> 00:11:26.909 A:middle L:90%
But he can't just ask Alice for which one he

212
00:11:26.909 --> 00:11:28.840 A:middle L:90%
wants because that would reveal his input. Tallis So

213
00:11:28.840 --> 00:11:31.950 A:middle L:90%
the trick is to use something called oblivious transfer.

214
00:11:31.539 --> 00:11:35.639 A:middle L:90%
Um Which I'm not gonna go into how that works

215
00:11:35.639 --> 00:11:37.789 A:middle L:90%
. There are lots of different protocols for doing this

216
00:11:37.799 --> 00:11:39.830 A:middle L:90%
. Um It's a it's a well studied cryptographic primitive

217
00:11:39.840 --> 00:11:43.519 A:middle L:90%
but it has this property that Alice can generate to

218
00:11:43.529 --> 00:11:48.950 A:middle L:90%
nonsense Bob Sends Picks one Bit which one he wants

219
00:11:48.440 --> 00:11:50.690 A:middle L:90%
. They execute a protocol and at the end of

220
00:11:50.690 --> 00:11:54.860 A:middle L:90%
this bob gets one of the values And Alice doesn't

221
00:11:54.860 --> 00:11:56.019 A:middle L:90%
learn which one Bob got and Bob doesn't learn anything

222
00:11:56.019 --> 00:11:58.490 A:middle L:90%
about the other value. Um It should be sort

223
00:11:58.490 --> 00:12:01.399 A:middle L:90%
of surprising to you that you can actually do this

224
00:12:01.409 --> 00:12:03.889 A:middle L:90%
right? This is one of these um magical crypto

225
00:12:03.889 --> 00:12:07.049 A:middle L:90%
things that can do something that you would think shouldn't

226
00:12:07.049 --> 00:12:11.879 A:middle L:90%
be possible but you can um Okay, so now

227
00:12:11.879 --> 00:12:13.509 A:middle L:90%
we can do any function this way because we can

228
00:12:13.509 --> 00:12:16.649 A:middle L:90%
pick our wire labels to propagate through the computation,

229
00:12:16.659 --> 00:12:20.809 A:middle L:90%
we can represent any function we want as gates and

230
00:12:20.809 --> 00:12:24.169 A:middle L:90%
we can execute any function this way there are a

231
00:12:24.169 --> 00:12:26.559 A:middle L:90%
couple of big issues. This is very different from

232
00:12:28.340 --> 00:12:31.389 A:middle L:90%
regular digital circuits. When we implement logic with regular

233
00:12:31.389 --> 00:12:37.090 A:middle L:90%
digital circuits, each operation is very efficient. We're

234
00:12:37.090 --> 00:12:39.039 A:middle L:90%
operating on known data, we're not trying to keep

235
00:12:39.049 --> 00:12:43.860 A:middle L:90%
the values secret and each operation takes a few nanoseconds

236
00:12:43.320 --> 00:12:50.090 A:middle L:90%
to do something like an and gate with garbled circuits

237
00:12:50.090 --> 00:12:52.659 A:middle L:90%
. Each operation requires encryption so it's very expensive to

238
00:12:52.669 --> 00:12:56.720 A:middle L:90%
do each operation. Um The other big differences.

239
00:12:56.720 --> 00:12:58.360 A:middle L:90%
We can't reuse anything right. If we reuse any

240
00:12:58.360 --> 00:13:01.830 A:middle L:90%
of the gates we would have a problem that that

241
00:13:01.830 --> 00:13:05.169 A:middle L:90%
would reveal some information. It would leak if we

242
00:13:05.169 --> 00:13:07.549 A:middle L:90%
got the same output as last time we learned something

243
00:13:07.549 --> 00:13:09.779 A:middle L:90%
about those inputs. So when we designed regular digital

244
00:13:09.779 --> 00:13:13.269 A:middle L:90%
circuits reuse is great, right? We want to

245
00:13:13.269 --> 00:13:15.860 A:middle L:90%
use the same transistors over and over again. When

246
00:13:15.860 --> 00:13:18.840 A:middle L:90%
we designed garbled circuits, we're not allowed to have

247
00:13:18.840 --> 00:13:22.440 A:middle L:90%
any reviews. So this means if we're designing circuits

248
00:13:22.440 --> 00:13:24.080 A:middle L:90%
to work on large problems, they get really huge

249
00:13:24.080 --> 00:13:26.990 A:middle L:90%
really fast. We end up with with billions of

250
00:13:26.000 --> 00:13:31.360 A:middle L:90%
gates. So until recently, at least until about

251
00:13:31.740 --> 00:13:35.580 A:middle L:90%
uh 10 years ago. This was really just an

252
00:13:35.590 --> 00:13:37.539 A:middle L:90%
interesting theoretical trick that Andrew came up with in the

253
00:13:37.539 --> 00:13:39.990 A:middle L:90%
80s that no one thought you could actually build systems

254
00:13:39.990 --> 00:13:41.940 A:middle L:90%
this way because if you have to do, you

255
00:13:41.940 --> 00:13:45.360 A:middle L:90%
know, for encryptions for each bit operation, that

256
00:13:45.360 --> 00:13:48.379 A:middle L:90%
just sounds crazy. But back in 2004, Benny

257
00:13:48.379 --> 00:13:52.379 A:middle L:90%
Pincus group actually developed a system this way built a

258
00:13:52.379 --> 00:13:54.590 A:middle L:90%
tool that could take a program, turn it into

259
00:13:54.600 --> 00:13:58.830 A:middle L:90%
a garbled table and actually execute it. Um And

260
00:13:58.840 --> 00:14:01.620 A:middle L:90%
it worked for examples like the Millionaire's problem where you're

261
00:14:01.620 --> 00:14:05.870 A:middle L:90%
doing a greater than comparison. Um The problem with

262
00:14:05.870 --> 00:14:07.610 A:middle L:90%
this is the size of circuit that you generate is

263
00:14:07.610 --> 00:14:09.919 A:middle L:90%
actually huge. It's it's not to scale. And

264
00:14:09.929 --> 00:14:13.580 A:middle L:90%
when you tried this approach on any problem that was

265
00:14:13.580 --> 00:14:16.179 A:middle L:90%
actually interesting, um you couldn't even finish building the

266
00:14:16.179 --> 00:14:18.350 A:middle L:90%
circuit because it blew up your memory and all your

267
00:14:18.350 --> 00:14:22.759 A:middle L:90%
displaced just trying to store the circuit. Um So

268
00:14:22.539 --> 00:14:26.129 A:middle L:90%
the first thing that we started doing to try to

269
00:14:26.129 --> 00:14:28.120 A:middle L:90%
make this faster was to observe that you don't actually

270
00:14:28.120 --> 00:14:30.980 A:middle L:90%
need to keep the whole circuit in memory, that's

271
00:14:30.980 --> 00:14:33.419 A:middle L:90%
your big bottleneck. Is this whole circuit, there's

272
00:14:33.419 --> 00:14:33.909 A:middle L:90%
no reason you need to keep the whole circuit in

273
00:14:33.909 --> 00:14:37.820 A:middle L:90%
memory. Um So my student came up with a

274
00:14:37.830 --> 00:14:39.320 A:middle L:90%
clever way of pipeline in it, where all you

275
00:14:39.320 --> 00:14:43.200 A:middle L:90%
need to do is create the gates, you need

276
00:14:43.200 --> 00:14:43.960 A:middle L:90%
to know the circuit structure, so you need to

277
00:14:43.960 --> 00:14:46.179 A:middle L:90%
know how you're valuing the gates and how they're connected

278
00:14:46.200 --> 00:14:48.870 A:middle L:90%
. But all the large amount of the circuit that

279
00:14:48.909 --> 00:14:50.909 A:middle L:90%
you can't reuse all these garbled tables that you have

280
00:14:50.909 --> 00:14:52.620 A:middle L:90%
to keep creating, well you don't need to keep

281
00:14:52.620 --> 00:14:56.559 A:middle L:90%
those. So you have a framework that's generating gates

282
00:14:56.639 --> 00:15:00.080 A:middle L:90%
as you generate gates, you send them to the

283
00:15:00.080 --> 00:15:03.320 A:middle L:90%
evaluator and the evaluator doesn't need the full circuit,

284
00:15:03.320 --> 00:15:05.789 A:middle L:90%
it just needs the gate and all the input of

285
00:15:05.789 --> 00:15:07.720 A:middle L:90%
that gate and it will evaluate them as they come

286
00:15:07.720 --> 00:15:09.769 A:middle L:90%
in. So we can pipeline all of this process

287
00:15:09.769 --> 00:15:11.860 A:middle L:90%
and never need to store the whole circuit, never

288
00:15:11.860 --> 00:15:13.289 A:middle L:90%
need to send the whole circuit. We're just sending

289
00:15:13.289 --> 00:15:16.059 A:middle L:90%
gates and evaluating them as they come. As long

290
00:15:16.059 --> 00:15:20.029 A:middle L:90%
as we've sorted the circuit of topological way the inputs

291
00:15:20.029 --> 00:15:22.080 A:middle L:90%
will be ready and we'll get the outputs. So

292
00:15:22.080 --> 00:15:24.860 A:middle L:90%
this basically means you can scale to any size circuit

293
00:15:24.590 --> 00:15:26.610 A:middle L:90%
the time to execute. Still depends on the number

294
00:15:26.610 --> 00:15:30.429 A:middle L:90%
of gates that you have to evaluate but there's um

295
00:15:30.440 --> 00:15:35.610 A:middle L:90%
you've you've solved the memory scaling problem, looking at

296
00:15:35.610 --> 00:15:39.269 A:middle L:90%
what's going on a little more closely were overlapping the

297
00:15:39.269 --> 00:15:43.539 A:middle L:90%
generation and evaluation phases. Alright, So now the

298
00:15:43.539 --> 00:15:46.039 A:middle L:90%
generator is generating the circuits as it transmits it,

299
00:15:46.049 --> 00:15:50.740 A:middle L:90%
they can be evaluated as they're going. The cost

300
00:15:50.750 --> 00:15:54.009 A:middle L:90%
to generate a circuit is for encryptions, you've got

301
00:15:54.009 --> 00:15:56.870 A:middle L:90%
to build that whole garble table. Um there's a

302
00:15:56.870 --> 00:15:58.950 A:middle L:90%
trick you can use to make it so to evaluate

303
00:15:58.960 --> 00:16:00.700 A:middle L:90%
a gate, you only need to decrypt one,

304
00:16:00.710 --> 00:16:03.190 A:middle L:90%
you can tell which one to decrypt without leaking any

305
00:16:03.190 --> 00:16:07.309 A:middle L:90%
information by embedding some some bits in the nonsense.

306
00:16:07.320 --> 00:16:10.600 A:middle L:90%
And then that means the evaluation is about a quarter

307
00:16:10.600 --> 00:16:15.570 A:middle L:90%
as much work as the generation. So evaluators got

308
00:16:15.570 --> 00:16:18.929 A:middle L:90%
all these idle times when it's waiting for the generator

309
00:16:18.940 --> 00:16:21.919 A:middle L:90%
to produce more gates for it to evaluate. So

310
00:16:21.919 --> 00:16:22.600 A:middle L:90%
keep that in mind because what we'll use those at

311
00:16:22.600 --> 00:16:29.740 A:middle L:90%
all times in a useful way soon. So this

312
00:16:29.750 --> 00:16:32.980 A:middle L:90%
has a big impact on performance. We can get

313
00:16:32.980 --> 00:16:36.440 A:middle L:90%
to the point where we're evaluating large circuits with billions

314
00:16:36.440 --> 00:16:38.289 A:middle L:90%
of gates and the time to evaluate a gate is

315
00:16:38.289 --> 00:16:45.139 A:middle L:90%
still many orders of magnitude slower than normal computation but

316
00:16:45.149 --> 00:16:48.149 A:middle L:90%
within the realm of doing sort of interesting large scale

317
00:16:48.149 --> 00:16:52.950 A:middle L:90%
problems. Okay, so in terms of security,

318
00:16:52.950 --> 00:16:55.730 A:middle L:90%
this really only gets us halfway there. So the

319
00:16:55.740 --> 00:16:59.120 A:middle L:90%
standard garbled circuit protocol and most of the work that

320
00:16:59.120 --> 00:17:03.039 A:middle L:90%
focused on building systems has this threat model that is

321
00:17:03.039 --> 00:17:06.140 A:middle L:90%
a really, really ridiculously weak one. And it's

322
00:17:06.140 --> 00:17:08.650 A:middle L:90%
called the semi honest threat model and what it means

323
00:17:08.650 --> 00:17:12.920 A:middle L:90%
is you provide these high privacy and correctness guarantees.

324
00:17:12.930 --> 00:17:15.960 A:middle L:90%
As long as both parties follow the protocol as specified

325
00:17:17.539 --> 00:17:19.500 A:middle L:90%
, right? Um Normally security is all about thinking

326
00:17:19.500 --> 00:17:22.509 A:middle L:90%
about what happens when their adversaries who don't follow the

327
00:17:22.509 --> 00:17:25.619 A:middle L:90%
rules. And these protocols only work when you assume

328
00:17:25.619 --> 00:17:26.779 A:middle L:90%
that both parties follow the rules. So that's a

329
00:17:26.789 --> 00:17:32.140 A:middle L:90%
really bad property for security protocol to have. But

330
00:17:32.150 --> 00:17:34.890 A:middle L:90%
there's a way to tweak it to actually get very

331
00:17:34.890 --> 00:17:37.230 A:middle L:90%
close to what we want with only adding a little

332
00:17:37.230 --> 00:17:41.220 A:middle L:90%
to the cost. So if you think about what

333
00:17:41.220 --> 00:17:42.059 A:middle L:90%
happens, if you don't send the results back,

334
00:17:44.519 --> 00:17:45.660 A:middle L:90%
then at least you get perfect privacy right? If

335
00:17:47.240 --> 00:17:49.569 A:middle L:90%
you have an oblivious transfer that that works correctly and

336
00:17:49.569 --> 00:17:52.809 A:middle L:90%
and we know about good oblivious transfer protocols and you

337
00:17:52.809 --> 00:17:56.220 A:middle L:90%
do a garbled circuit protocol, but the evaluator who

338
00:17:56.220 --> 00:17:59.859 A:middle L:90%
evaluates the circuit never sends anything back to the generator

339
00:18:00.339 --> 00:18:02.380 A:middle L:90%
. Well, that's a really good guarantee that you

340
00:18:02.380 --> 00:18:03.559 A:middle L:90%
have privacy. You're not sending anything back at all

341
00:18:04.240 --> 00:18:07.970 A:middle L:90%
. Um it doesn't give you correctness right, that

342
00:18:07.980 --> 00:18:11.019 A:middle L:90%
the generator could produce the circuit that implement some completely

343
00:18:11.019 --> 00:18:14.599 A:middle L:90%
different function from the one you wanted. Um and

344
00:18:14.599 --> 00:18:17.160 A:middle L:90%
so you don't know if you got the correct result

345
00:18:17.640 --> 00:18:18.849 A:middle L:90%
. And it also is very unfair because the generator

346
00:18:18.849 --> 00:18:21.700 A:middle L:90%
does all this work, but doesn't get any results

347
00:18:21.700 --> 00:18:23.150 A:middle L:90%
back and lots of the scenarios, we want to

348
00:18:23.150 --> 00:18:26.000 A:middle L:90%
use this, we want both parties to get the

349
00:18:26.000 --> 00:18:27.569 A:middle L:90%
results, but if you think about this, it

350
00:18:27.569 --> 00:18:30.140 A:middle L:90%
gives us sort of half of what we need.

351
00:18:30.509 --> 00:18:33.640 A:middle L:90%
It gives us strong privacy without that. So normally

352
00:18:33.640 --> 00:18:37.200 A:middle L:90%
if we get half of what we need by doing

353
00:18:37.200 --> 00:18:38.559 A:middle L:90%
something once, well we should do it twice,

354
00:18:40.140 --> 00:18:41.690 A:middle L:90%
then we'll get all of what we need. This

355
00:18:41.690 --> 00:18:45.720 A:middle L:90%
is a unstated composition role in computer science. Um

356
00:18:45.730 --> 00:18:48.680 A:middle L:90%
So that's what we're gonna do, we're gonna execute

357
00:18:48.680 --> 00:18:52.049 A:middle L:90%
it twice. Um and this is sort of like

358
00:18:52.059 --> 00:18:56.630 A:middle L:90%
the two executions in the picture. Um The difference

359
00:18:56.630 --> 00:18:59.250 A:middle L:90%
is when we do our two executions were gonna have

360
00:18:59.250 --> 00:19:03.759 A:middle L:90%
the executioner and the generator switch roles between them so

361
00:19:03.769 --> 00:19:06.049 A:middle L:90%
they'll each do one in each role. Um I

362
00:19:06.049 --> 00:19:07.450 A:middle L:90%
have not been able to find any actual executioners to

363
00:19:07.450 --> 00:19:10.380 A:middle L:90%
ask them whether this is a good idea for them

364
00:19:10.390 --> 00:19:12.000 A:middle L:90%
but I think they probably wouldn't be too enthusiastic about

365
00:19:12.000 --> 00:19:15.259 A:middle L:90%
the switching roles part. Um But it works well

366
00:19:15.259 --> 00:19:18.160 A:middle L:90%
for us, so here's what we're gonna do.

367
00:19:18.640 --> 00:19:21.920 A:middle L:90%
So we're going to execute the first protocol. Regular

368
00:19:21.920 --> 00:19:23.759 A:middle L:90%
, semi honest garbled circuit protocol Alice is going to

369
00:19:23.759 --> 00:19:26.089 A:middle L:90%
generate. The circuit bob's gonna evaluate it, bob

370
00:19:26.089 --> 00:19:30.359 A:middle L:90%
is going to get the result, then we're gonna

371
00:19:30.619 --> 00:19:33.900 A:middle L:90%
do the same thing in the other direction, bob

372
00:19:33.900 --> 00:19:36.710 A:middle L:90%
is going to generate the circuit Alice is going to

373
00:19:36.710 --> 00:19:38.799 A:middle L:90%
evaluate it. Alice will get the result. So

374
00:19:38.799 --> 00:19:42.289 A:middle L:90%
now they've both got results, if they were both

375
00:19:42.289 --> 00:19:45.349 A:middle L:90%
honest, the results should be the same. If

376
00:19:45.359 --> 00:19:48.400 A:middle L:90%
one sheeted the results would be different. So what

377
00:19:48.400 --> 00:19:51.079 A:middle L:90%
we want to do is compare those results. If

378
00:19:51.079 --> 00:19:55.450 A:middle L:90%
those results are equal then we know that if we

379
00:19:55.450 --> 00:19:59.309 A:middle L:90%
were honest the other party evaluated our circuit correctly,

380
00:19:59.319 --> 00:20:00.369 A:middle L:90%
um The results should be the same and we have

381
00:20:00.369 --> 00:20:03.029 A:middle L:90%
a lot of confidence that that we got the correct

382
00:20:03.029 --> 00:20:04.730 A:middle L:90%
results. Now we have to be real careful how

383
00:20:04.730 --> 00:20:07.079 A:middle L:90%
we do that equality test, right? We can't

384
00:20:07.089 --> 00:20:11.200 A:middle L:90%
allow one party to lie about the result in the

385
00:20:11.200 --> 00:20:12.769 A:middle L:90%
quality test because then they could trick us into thinking

386
00:20:12.779 --> 00:20:15.109 A:middle L:90%
our result is correct and we can't leak any more

387
00:20:15.109 --> 00:20:18.049 A:middle L:90%
information uh by doing the quality test. So we

388
00:20:18.049 --> 00:20:21.289 A:middle L:90%
need to do the quality test in a careful way

389
00:20:21.299 --> 00:20:23.099 A:middle L:90%
um In a way that that has the high security

390
00:20:23.099 --> 00:20:26.650 A:middle L:90%
properties but there are ways to do a quality test

391
00:20:26.650 --> 00:20:27.740 A:middle L:90%
and it's small, right? The quality test doesn't

392
00:20:27.740 --> 00:20:30.450 A:middle L:90%
scale with the size of the circuit and it only

393
00:20:30.450 --> 00:20:33.619 A:middle L:90%
depends on the size of the output. So that's

394
00:20:33.619 --> 00:20:36.880 A:middle L:90%
what we're gonna do. Um This isn't perfect.

395
00:20:36.890 --> 00:20:38.220 A:middle L:90%
Right? It does leak some information and the information

396
00:20:38.220 --> 00:20:41.869 A:middle L:90%
that leaks is the result of the quality test,

397
00:20:41.880 --> 00:20:42.700 A:middle L:90%
you certainly have to share that, right? If

398
00:20:42.700 --> 00:20:47.170 A:middle L:90%
you don't share the result of the quality test then

399
00:20:47.220 --> 00:20:49.980 A:middle L:90%
you haven't got anything. Um And so that's basically

400
00:20:49.980 --> 00:20:53.160 A:middle L:90%
one bit right. If the outputs are equal,

401
00:20:55.140 --> 00:20:59.079 A:middle L:90%
um an attacker could design a circuit. So for

402
00:20:59.079 --> 00:21:00.920 A:middle L:90%
some set of inputs, the outputs are b are

403
00:21:00.920 --> 00:21:03.819 A:middle L:90%
equal and some set of inputs. The outputs are

404
00:21:03.819 --> 00:21:07.049 A:middle L:90%
different and the attacker can learn whether your input is

405
00:21:07.049 --> 00:21:10.130 A:middle L:90%
in the set that makes it equal or the set

406
00:21:10.130 --> 00:21:11.539 A:middle L:90%
that makes it unequal So you're leaking one bit of

407
00:21:11.539 --> 00:21:15.799 A:middle L:90%
information. Um You're getting caught when you cheat,

408
00:21:15.809 --> 00:21:18.670 A:middle L:90%
right? At least in the case where they're different

409
00:21:19.039 --> 00:21:21.680 A:middle L:90%
, but in the case when they're not different,

410
00:21:21.680 --> 00:21:22.960 A:middle L:90%
you're still leaking some information because the attacker when they

411
00:21:22.960 --> 00:21:26.650 A:middle L:90%
weren't different, so that's what you're giving up and

412
00:21:26.650 --> 00:21:30.750 A:middle L:90%
you can think about that in terms of You're giving

413
00:21:30.759 --> 00:21:33.380 A:middle L:90%
a malicious party, the opportunity to partition the input

414
00:21:33.380 --> 00:21:37.759 A:middle L:90%
space into 2 2 groups. Um and those are

415
00:21:38.140 --> 00:21:41.250 A:middle L:90%
so f is the output of the actual function your

416
00:21:41.250 --> 00:21:42.470 A:middle L:90%
computing, G is the one bit that you get

417
00:21:42.480 --> 00:21:48.940 A:middle L:90%
that is the equality test and the other party,

418
00:21:48.940 --> 00:21:52.480 A:middle L:90%
if they're dishonest can learn which set your input is

419
00:21:52.480 --> 00:21:55.769 A:middle L:90%
in of these groups. Um There are ways of

420
00:21:56.140 --> 00:21:57.750 A:middle L:90%
eliminating this problem that start to get get much more

421
00:21:57.750 --> 00:22:02.259 A:middle L:90%
expensive and I won't get into now. Um and

422
00:22:02.269 --> 00:22:03.690 A:middle L:90%
the way to to reason about this. Um just

423
00:22:03.690 --> 00:22:06.980 A:middle L:90%
to mention a little bit that that you can formally

424
00:22:06.980 --> 00:22:08.720 A:middle L:90%
show that the protocol has this property. Um So

425
00:22:08.720 --> 00:22:12.890 A:middle L:90%
the normal malicious model is you've got a protocol that

426
00:22:12.890 --> 00:22:15.890 A:middle L:90%
behaves in the real world, You're looking at the

427
00:22:15.890 --> 00:22:18.160 A:middle L:90%
actual protocol and you want to compare that to an

428
00:22:18.160 --> 00:22:22.210 A:middle L:90%
ideal world model where you've got a protocol Done by

429
00:22:22.210 --> 00:22:25.150 A:middle L:90%
a trusted 3rd party that just sends you the output

430
00:22:25.410 --> 00:22:27.049 A:middle L:90%
, if those things can see if you can simulate

431
00:22:27.519 --> 00:22:30.450 A:middle L:90%
everything that you can do in the real world,

432
00:22:30.460 --> 00:22:32.849 A:middle L:90%
in the ideal world, then you're not leaking anything

433
00:22:33.619 --> 00:22:34.500 A:middle L:90%
. We obviously can't do that here because we know

434
00:22:34.500 --> 00:22:40.150 A:middle L:90%
we're leaking one bit. So the analogous model is

435
00:22:40.160 --> 00:22:42.160 A:middle L:90%
this real world with an extra one bit output of

436
00:22:42.160 --> 00:22:45.109 A:middle L:90%
an arbitrary function, and then we can prove that

437
00:22:45.109 --> 00:22:47.859 A:middle L:90%
the protocol that we have is equivalent to that.

438
00:22:49.940 --> 00:22:55.049 A:middle L:90%
Okay, so the way that we make this fast

439
00:22:55.640 --> 00:22:56.869 A:middle L:90%
is we can actually overlap these steps. So if

440
00:22:56.869 --> 00:23:00.039 A:middle L:90%
you remember when I showed you the pipe lining a

441
00:23:00.039 --> 00:23:03.380 A:middle L:90%
third of the time, I'm sorry, three quarters

442
00:23:03.380 --> 00:23:06.680 A:middle L:90%
of the time, the evaluator is idle approximately because

443
00:23:06.680 --> 00:23:07.450 A:middle L:90%
they have less work to do than the generator.

444
00:23:08.039 --> 00:23:11.849 A:middle L:90%
Well, now we're overlapping the two steps, they're

445
00:23:11.849 --> 00:23:12.660 A:middle L:90%
doing almost the same amount of work, and the

446
00:23:12.660 --> 00:23:17.170 A:middle L:90%
total work they're doing is just one and a quarter

447
00:23:17.279 --> 00:23:19.589 A:middle L:90%
what it was before. So the actual cost of

448
00:23:19.589 --> 00:23:22.329 A:middle L:90%
doing this is pretty low. There's also the quality

449
00:23:22.329 --> 00:23:26.450 A:middle L:90%
tests, which is pretty inexpensive. Um So here's

450
00:23:26.450 --> 00:23:27.640 A:middle L:90%
what that looks like in terms of what happens when

451
00:23:27.640 --> 00:23:30.859 A:middle L:90%
you actually run problems. Um if you've got a

452
00:23:30.859 --> 00:23:34.730 A:middle L:90%
dual core machine, You have very little cost over

453
00:23:34.740 --> 00:23:37.349 A:middle L:90%
the semi honest protocol where you're just doing it in

454
00:23:37.349 --> 00:23:41.349 A:middle L:90%
one direction because you're overlapping all this work. Um

455
00:23:41.359 --> 00:23:44.019 A:middle L:90%
if you can find the single core machine which is

456
00:23:44.019 --> 00:23:45.380 A:middle L:90%
really hard to do today or configure your machine to

457
00:23:45.380 --> 00:23:48.190 A:middle L:90%
only allow one core to be used for this,

458
00:23:48.200 --> 00:23:49.059 A:middle L:90%
then you see the cost is more like, like

459
00:23:49.059 --> 00:23:52.950 A:middle L:90%
the 30% you would expect um from the overlapping.

460
00:23:52.440 --> 00:23:56.710 A:middle L:90%
um So this works well enough that you can do

461
00:23:56.720 --> 00:24:00.140 A:middle L:90%
arbitrarily large circuits. There's no scaling problems because it's

462
00:24:00.140 --> 00:24:03.970 A:middle L:90%
all pipeline um and it's fast enough to do some

463
00:24:03.970 --> 00:24:07.680 A:middle L:90%
fairly interesting problems um and it's much faster than than

464
00:24:07.680 --> 00:24:11.069 A:middle L:90%
the best known solutions that avoid this problem of leaking

465
00:24:11.069 --> 00:24:12.690 A:middle L:90%
one bit And how important it is to Leak one

466
00:24:12.690 --> 00:24:17.410 A:middle L:90%
bit is definitely highly debatable question. One way to

467
00:24:17.410 --> 00:24:21.190 A:middle L:90%
think about that is you're already revealing the output which

468
00:24:21.190 --> 00:24:22.619 A:middle L:90%
is revealing a lot about your inputs. So this

469
00:24:22.630 --> 00:24:26.420 A:middle L:90%
extra bit that might be revealed through the quality test

470
00:24:26.430 --> 00:24:29.450 A:middle L:90%
um is pretty small compared to what you're already revealing

471
00:24:29.460 --> 00:24:33.140 A:middle L:90%
by sharing the outputs for most problems. Okay,

472
00:24:33.150 --> 00:24:37.470 A:middle L:90%
so the rest of the time I want to talk

473
00:24:37.529 --> 00:24:41.460 A:middle L:90%
some about applications and the applications that I've talked about

474
00:24:41.460 --> 00:24:44.109 A:middle L:90%
so far and that that we have results from here

475
00:24:44.109 --> 00:24:47.269 A:middle L:90%
. These are applications that quite naturally map two circuits

476
00:24:48.200 --> 00:24:51.240 A:middle L:90%
and that's why these are chosen and used as the

477
00:24:51.240 --> 00:24:53.309 A:middle L:90%
benchmarks. Things like doing encryption. So doing private

478
00:24:53.309 --> 00:24:56.980 A:middle L:90%
encryption is actually quite useful. You can have one

479
00:24:56.980 --> 00:25:00.119 A:middle L:90%
party know the data, you're encrypting one party,

480
00:25:00.119 --> 00:25:02.289 A:middle L:90%
no, the key. They can produce the encryption

481
00:25:02.289 --> 00:25:04.859 A:middle L:90%
of that data with that key without knowing knowing either

482
00:25:04.869 --> 00:25:07.269 A:middle L:90%
without either party knowing both the data and the key

483
00:25:08.210 --> 00:25:11.390 A:middle L:90%
. But encryption algorithms are designed to be efficient as

484
00:25:11.390 --> 00:25:14.589 A:middle L:90%
circuits. That's one of the factors used in deciding

485
00:25:14.589 --> 00:25:17.529 A:middle L:90%
an encryption algorithm is whether you can implement it as

486
00:25:17.529 --> 00:25:19.650 A:middle L:90%
a circuit well and these other problems like edit distance

487
00:25:19.660 --> 00:25:22.950 A:middle L:90%
also map very well, circuits, what we'd really

488
00:25:22.950 --> 00:25:25.759 A:middle L:90%
like to get to those is being able to take

489
00:25:25.769 --> 00:25:29.829 A:middle L:90%
arbitrary programs, being able to take things people do

490
00:25:29.829 --> 00:25:32.670 A:middle L:90%
in real code, turn it into a circuit and

491
00:25:32.670 --> 00:25:33.740 A:middle L:90%
be able to execute it in a reasonable time as

492
00:25:33.740 --> 00:25:37.650 A:middle L:90%
a secure computation. The problem is, real code

493
00:25:37.660 --> 00:25:41.529 A:middle L:90%
does all sorts of crazy things that seems horrible to

494
00:25:41.529 --> 00:25:45.460 A:middle L:90%
implement. Things like assigning to an array. Right

495
00:25:47.240 --> 00:25:49.450 A:middle L:90%
? So this doesn't seem that crazy if you're not

496
00:25:49.450 --> 00:25:52.359 A:middle L:90%
implementing in a circuit, probably uh you put stuff

497
00:25:52.359 --> 00:25:55.769 A:middle L:90%
like this in your code without thinking about how horrible

498
00:25:55.769 --> 00:25:56.680 A:middle L:90%
it is. But if you think about what you

499
00:25:56.680 --> 00:26:00.630 A:middle L:90%
have to do to do an arbitrary array assignment in

500
00:26:00.630 --> 00:26:03.000 A:middle L:90%
a circuit, well you've got to do something like

501
00:26:03.000 --> 00:26:06.059 A:middle L:90%
this. Right? So remember that its data oblivious

502
00:26:06.069 --> 00:26:08.099 A:middle L:90%
, we can't know anything about the inputs. So

503
00:26:08.099 --> 00:26:11.059 A:middle L:90%
to do that one assignment Well, we've got to

504
00:26:11.059 --> 00:26:12.670 A:middle L:90%
have a marks that looks at each element of the

505
00:26:12.670 --> 00:26:15.730 A:middle L:90%
race. So we're gonna check is the index value

506
00:26:15.730 --> 00:26:19.460 A:middle L:90%
we're assigning to equal to zero If it is,

507
00:26:19.460 --> 00:26:22.759 A:middle L:90%
we replace the value in element zero of the array

508
00:26:22.769 --> 00:26:26.140 A:middle L:90%
with the new value. But we got to do

509
00:26:26.140 --> 00:26:29.769 A:middle L:90%
that for every element of the array. And if

510
00:26:29.769 --> 00:26:33.089 A:middle L:90%
we don't know anything about the index and we need

511
00:26:33.089 --> 00:26:34.019 A:middle L:90%
to do this in a secure computation, we need

512
00:26:34.019 --> 00:26:36.829 A:middle L:90%
to design a circuit to be able to do this

513
00:26:37.839 --> 00:26:38.390 A:middle L:90%
. We're going to need a circuit that's as big

514
00:26:38.390 --> 00:26:41.539 A:middle L:90%
as the array. So if we want to solve

515
00:26:41.539 --> 00:26:45.700 A:middle L:90%
interesting problems are raised are pretty big and for every

516
00:26:45.799 --> 00:26:47.920 A:middle L:90%
array update, if we have to copy the entire

517
00:26:47.920 --> 00:26:49.890 A:middle L:90%
circuit, our program is not going to, our

518
00:26:49.900 --> 00:26:52.380 A:middle L:90%
protocol is not going to finish at least not in

519
00:26:52.380 --> 00:26:55.460 A:middle L:90%
any reasonable amount of time. So we want to

520
00:26:55.460 --> 00:26:59.369 A:middle L:90%
do something better than that as an example of where

521
00:26:59.380 --> 00:27:02.319 A:middle L:90%
we can see obvious ways to do better. So

522
00:27:02.319 --> 00:27:03.700 A:middle L:90%
suppose the update is in a loop like this,

523
00:27:04.839 --> 00:27:07.500 A:middle L:90%
well then we know that we're doing this for each

524
00:27:07.500 --> 00:27:11.369 A:middle L:90%
element in the array so we can build a circuit

525
00:27:11.369 --> 00:27:12.779 A:middle L:90%
that does them all at once. We don't need

526
00:27:12.779 --> 00:27:15.460 A:middle L:90%
them boxes. Alright. We can update each element

527
00:27:15.460 --> 00:27:18.180 A:middle L:90%
of the array the same way and whatever function we

528
00:27:18.180 --> 00:27:22.170 A:middle L:90%
want to update it. We don't need to do

529
00:27:22.170 --> 00:27:26.059 A:middle L:90%
you and copies of the circuit updating each one separately

530
00:27:26.640 --> 00:27:29.200 A:middle L:90%
. So this gives the insight that well, this

531
00:27:29.200 --> 00:27:30.609 A:middle L:90%
is a really obvious easy example for that. Most

532
00:27:30.609 --> 00:27:33.109 A:middle L:90%
things that we see in real code are not that

533
00:27:33.109 --> 00:27:36.279 A:middle L:90%
simple, but maybe we can take advantage of similar

534
00:27:36.279 --> 00:27:40.750 A:middle L:90%
properties and design ways of implementing data structures in circuits

535
00:27:40.759 --> 00:27:42.940 A:middle L:90%
that don't require all this copying but give us something

536
00:27:42.940 --> 00:27:45.700 A:middle L:90%
much more close to what we need in real programs

537
00:27:45.700 --> 00:27:51.289 A:middle L:90%
for fairly arbitrary access. So here's an example of

538
00:27:51.289 --> 00:27:52.960 A:middle L:90%
how we can do that. Um so we can

539
00:27:52.960 --> 00:27:56.430 A:middle L:90%
take advantage of local locality if we know that we

540
00:27:56.430 --> 00:27:59.599 A:middle L:90%
don't know exactly what elements being updated, but we

541
00:27:59.599 --> 00:28:02.640 A:middle L:90%
know which one of a small number of possible elements

542
00:28:02.640 --> 00:28:04.630 A:middle L:90%
could be updated, then we don't need to copy

543
00:28:04.630 --> 00:28:07.079 A:middle L:90%
the whole array and we can think of this like

544
00:28:07.079 --> 00:28:11.480 A:middle L:90%
a stack, so this code doesn't look explicitly like

545
00:28:11.480 --> 00:28:14.130 A:middle L:90%
a stack, but if we knew that we're starting

546
00:28:14.130 --> 00:28:15.140 A:middle L:90%
with the top element, we can turn this into

547
00:28:15.140 --> 00:28:19.160 A:middle L:90%
stack operations and think of it that way and there's

548
00:28:19.160 --> 00:28:22.279 A:middle L:90%
a small number of possible things that could be going

549
00:28:22.279 --> 00:28:23.450 A:middle L:90%
on here. The other thing to keep in mind

550
00:28:23.450 --> 00:28:26.940 A:middle L:90%
is because it's a circuit, we don't have any

551
00:28:26.940 --> 00:28:29.869 A:middle L:90%
control file. Alright. So anything that depends on

552
00:28:29.869 --> 00:28:33.019 A:middle L:90%
a condition like the if we have to embed in

553
00:28:33.019 --> 00:28:34.710 A:middle L:90%
the circuit we sort of have to embed in the

554
00:28:34.710 --> 00:28:37.119 A:middle L:90%
circuit following all paths. So what we want instead

555
00:28:37.119 --> 00:28:40.950 A:middle L:90%
of what would what you think of compiling this to

556
00:28:40.960 --> 00:28:44.890 A:middle L:90%
regular code. We want to turn it into code

557
00:28:44.890 --> 00:28:45.609 A:middle L:90%
that looks like a circuit. So it's going to

558
00:28:45.609 --> 00:28:49.130 A:middle L:90%
be conditional statements, so we can think of getting

559
00:28:49.140 --> 00:28:52.410 A:middle L:90%
the top element of the stack, we're going to

560
00:28:52.420 --> 00:28:56.269 A:middle L:90%
update it conditionally. So if the X is not

561
00:28:56.269 --> 00:28:59.809 A:middle L:90%
equal to zero predicate is true, then we update

562
00:28:59.809 --> 00:29:02.319 A:middle L:90%
the top of the stack, otherwise we do nothing

563
00:29:02.380 --> 00:29:04.789 A:middle L:90%
. And that's what these conditional operations do. And

564
00:29:04.789 --> 00:29:08.119 A:middle L:90%
then we push the stack. If both of these

565
00:29:08.119 --> 00:29:11.400 A:middle L:90%
tests are true. Um and then we update the

566
00:29:11.400 --> 00:29:14.180 A:middle L:90%
top of the stack again. So that's our goal

567
00:29:14.180 --> 00:29:18.960 A:middle L:90%
is to turn what seems like fairly arbitrary accesses in

568
00:29:18.960 --> 00:29:22.200 A:middle L:90%
real programs in the code that can be more localized

569
00:29:22.210 --> 00:29:25.059 A:middle L:90%
and that can be more easily turned into a circuit

570
00:29:25.839 --> 00:29:26.690 A:middle L:90%
. So once we've done that, then how do

571
00:29:26.690 --> 00:29:29.940 A:middle L:90%
we make a circuit that's efficient? Once we know

572
00:29:29.950 --> 00:29:34.269 A:middle L:90%
we're implementing something like a stack. So if we

573
00:29:34.640 --> 00:29:37.910 A:middle L:90%
did a naive conditional push, it would be something

574
00:29:37.910 --> 00:29:41.640 A:middle L:90%
like this. We have the p is the condition

575
00:29:41.650 --> 00:29:44.910 A:middle L:90%
that tells us whether we're pushing or not so that's

576
00:29:44.910 --> 00:29:47.670 A:middle L:90%
true or false. Um X is the new value

577
00:29:47.680 --> 00:29:48.990 A:middle L:90%
and for each element of the stack. Well,

578
00:29:49.000 --> 00:29:51.950 A:middle L:90%
if we push, we've got to move it down

579
00:29:51.950 --> 00:29:53.309 A:middle L:90%
one to make space for it. Um if we

580
00:29:53.309 --> 00:29:56.910 A:middle L:90%
didn't push, we copy it over. So this

581
00:29:56.910 --> 00:29:57.960 A:middle L:90%
still looks like we have the same problem we had

582
00:29:59.440 --> 00:30:02.680 A:middle L:90%
with our array update that we need to copy the

583
00:30:02.680 --> 00:30:07.109 A:middle L:90%
whole circuit for each push operation. Far more expensive

584
00:30:07.109 --> 00:30:08.680 A:middle L:90%
than we want, but we can do better than

585
00:30:08.680 --> 00:30:11.950 A:middle L:90%
that and we can take advantage of the locality by

586
00:30:12.339 --> 00:30:15.390 A:middle L:90%
looking at these operations and groups. So we're batch

587
00:30:15.390 --> 00:30:17.839 A:middle L:90%
in the operations and were knowing that they can only

588
00:30:17.839 --> 00:30:19.839 A:middle L:90%
affect a small part of the data structure. So

589
00:30:19.849 --> 00:30:23.759 A:middle L:90%
uh here's what that might look like with a concrete

590
00:30:23.769 --> 00:30:26.789 A:middle L:90%
push that the naive way we're going to move that

591
00:30:26.799 --> 00:30:30.119 A:middle L:90%
to a way that limits the amount of the stack

592
00:30:30.119 --> 00:30:33.839 A:middle L:90%
we have to look at for each operation. So

593
00:30:33.839 --> 00:30:36.069 A:middle L:90%
what we're gonna do is divide the stacking the levels

594
00:30:36.119 --> 00:30:37.269 A:middle L:90%
. So we have level zero is our top level

595
00:30:37.710 --> 00:30:41.190 A:middle L:90%
and our property Eddie's level is we're gonna have five

596
00:30:41.190 --> 00:30:45.369 A:middle L:90%
blocks and the size of each block doubles at each

597
00:30:45.369 --> 00:30:47.410 A:middle L:90%
level. So at the top level it's just one

598
00:30:47.410 --> 00:30:52.460 A:middle L:90%
element and we're going to have a constraint that we

599
00:30:52.940 --> 00:30:56.029 A:middle L:90%
have at our starting point is that we have at

600
00:30:56.029 --> 00:31:00.019 A:middle L:90%
least two full slots At each level and two empty

601
00:31:00.019 --> 00:31:03.920 A:middle L:90%
slots. That means that we can potentially do two

602
00:31:03.920 --> 00:31:06.900 A:middle L:90%
pushes. We can do to pops we can do

603
00:31:06.900 --> 00:31:10.549 A:middle L:90%
some mix of conditional pushes and pops without needing to

604
00:31:10.940 --> 00:31:14.519 A:middle L:90%
change the level of blood. So our goal is

605
00:31:14.519 --> 00:31:17.940 A:middle L:90%
to be able to for many operations only need to

606
00:31:17.940 --> 00:31:19.180 A:middle L:90%
look at a small part of the stack. So

607
00:31:19.180 --> 00:31:21.609 A:middle L:90%
here's how that's going to work. So if we

608
00:31:21.609 --> 00:31:26.299 A:middle L:90%
have our initial state, suppose we have a conditional

609
00:31:26.299 --> 00:31:30.819 A:middle L:90%
push. Well we have space and level zero for

610
00:31:30.819 --> 00:31:33.200 A:middle L:90%
that new element. Um The T. Values here

611
00:31:33.200 --> 00:31:34.299 A:middle L:90%
keep track of how many elements of that level are

612
00:31:34.299 --> 00:31:37.900 A:middle L:90%
alive. So we're going to push the new element

613
00:31:37.049 --> 00:31:38.890 A:middle L:90%
. Now we have four live elements at the top

614
00:31:38.890 --> 00:31:41.799 A:middle L:90%
level, the rest of it. Well, we

615
00:31:41.799 --> 00:31:45.650 A:middle L:90%
knew at circuit generation time, right? We don't

616
00:31:45.650 --> 00:31:48.130 A:middle L:90%
need to copy those over. We knew since we

617
00:31:48.130 --> 00:31:51.990 A:middle L:90%
started with two spaces left, we're never gonna need

618
00:31:51.990 --> 00:31:53.539 A:middle L:90%
to do anything with the other elements. So these

619
00:31:53.539 --> 00:31:56.809 A:middle L:90%
can all be copied at no cost and we have

620
00:31:56.809 --> 00:32:00.000 A:middle L:90%
space for another one. We can do another conditional

621
00:32:00.000 --> 00:32:01.359 A:middle L:90%
push that's going to fill up the top level.

622
00:32:02.440 --> 00:32:06.579 A:middle L:90%
We didn't have to do anything with other levels but

623
00:32:06.579 --> 00:32:07.920 A:middle L:90%
now we don't have any more space that we have

624
00:32:07.920 --> 00:32:09.609 A:middle L:90%
to do more operations and note that these are conditional

625
00:32:09.609 --> 00:32:12.819 A:middle L:90%
pushes so they might not have filled it up but

626
00:32:12.819 --> 00:32:15.049 A:middle L:90%
we don't know that. So we have to build

627
00:32:15.049 --> 00:32:19.380 A:middle L:90%
into the circuit to check at this point if the

628
00:32:19.390 --> 00:32:22.579 A:middle L:90%
top level is too full, then we shifted down

629
00:32:22.579 --> 00:32:24.240 A:middle L:90%
to the bottom level to have space for the next

630
00:32:24.240 --> 00:32:27.450 A:middle L:90%
operation. So that's going to work like this.

631
00:32:27.450 --> 00:32:30.759 A:middle L:90%
We're going to shift enough over to have space For

632
00:32:30.769 --> 00:32:36.059 A:middle L:90%
at least two empty slots and the bottom to end

633
00:32:36.059 --> 00:32:37.960 A:middle L:90%
up in one of the blocks on the next level

634
00:32:37.440 --> 00:32:42.250 A:middle L:90%
. Alright, so every two conditional operations at the

635
00:32:42.250 --> 00:32:44.269 A:middle L:90%
top level, we need to potentially do a shift

636
00:32:44.940 --> 00:32:49.190 A:middle L:90%
and then after um for conditional operations we might need

637
00:32:49.190 --> 00:32:51.759 A:middle L:90%
to do a shift at the next level so we

638
00:32:51.759 --> 00:32:52.809 A:middle L:90%
can advertise all the costs, We end up with

639
00:32:52.819 --> 00:32:55.109 A:middle L:90%
the cost scaling as the log of the size of

640
00:32:55.109 --> 00:32:59.089 A:middle L:90%
the stack, instead of linear in the size of

641
00:32:59.089 --> 00:33:00.960 A:middle L:90%
the stack that it would be with with the naive

642
00:33:00.960 --> 00:33:04.049 A:middle L:90%
way of doing this. Okay. And so this

643
00:33:04.049 --> 00:33:06.059 A:middle L:90%
this is the way to do it for stacks.

644
00:33:06.539 --> 00:33:07.480 A:middle L:90%
There are other ways to do it for other data

645
00:33:07.480 --> 00:33:10.779 A:middle L:90%
structures cues are quite similar to this. Um If

646
00:33:10.779 --> 00:33:13.930 A:middle L:90%
it's an array we can think of an array as

647
00:33:13.940 --> 00:33:17.990 A:middle L:90%
a mapping. So it's association map where the keys

648
00:33:17.990 --> 00:33:20.569 A:middle L:90%
are in texas but it works for any kind of

649
00:33:20.579 --> 00:33:22.410 A:middle L:90%
associative map. And there we also used the idea

650
00:33:22.410 --> 00:33:25.859 A:middle L:90%
of matching if we can sort the request and in

651
00:33:25.859 --> 00:33:29.619 A:middle L:90%
order then we can eliminate the ones we don't need

652
00:33:29.630 --> 00:33:31.599 A:middle L:90%
by looking for for ones with adjacent keys. Um

653
00:33:31.609 --> 00:33:35.059 A:middle L:90%
and and by batch ng them reduce the overall cost

654
00:33:35.440 --> 00:33:37.950 A:middle L:90%
. Um So here's an example of where this kind

655
00:33:37.950 --> 00:33:39.539 A:middle L:90%
of thing is useful. So our goal is to

656
00:33:39.539 --> 00:33:43.359 A:middle L:90%
get to be able to do secure computations that are

657
00:33:44.339 --> 00:33:46.150 A:middle L:90%
more like arbitrary real programs not limited to the things

658
00:33:46.150 --> 00:33:49.660 A:middle L:90%
that can be done easily in circuits. And if

659
00:33:49.660 --> 00:33:52.839 A:middle L:90%
we have a this is a clustering algorithm, dB

660
00:33:52.839 --> 00:33:57.460 A:middle L:90%
scan which is fairly popular in the machine learning community

661
00:33:58.259 --> 00:34:00.569 A:middle L:90%
. We have two parties that have their own databases

662
00:34:00.680 --> 00:34:01.890 A:middle L:90%
and these are multidimensional, I've drawn them as as

663
00:34:01.890 --> 00:34:06.119 A:middle L:90%
two dimensional points and what they want to do is

664
00:34:06.119 --> 00:34:07.670 A:middle L:90%
cluster them. Each one could cluster their own data

665
00:34:08.440 --> 00:34:12.130 A:middle L:90%
but they'll get better clustering results. If they can

666
00:34:12.130 --> 00:34:15.090 A:middle L:90%
combine their data they'll learn more. So this example

667
00:34:15.090 --> 00:34:15.429 A:middle L:90%
where this might be useful, it could be a

668
00:34:15.440 --> 00:34:19.250 A:middle L:90%
medical example, it could be financial fraud detection.

669
00:34:19.260 --> 00:34:22.489 A:middle L:90%
They're looking for um outlier transactions in some some data

670
00:34:22.489 --> 00:34:24.840 A:middle L:90%
set and by combining their data they'll get much better

671
00:34:24.840 --> 00:34:27.469 A:middle L:90%
results but they want to keep their data private.

672
00:34:27.940 --> 00:34:30.050 A:middle L:90%
So their goal is to combine their data figure out

673
00:34:30.050 --> 00:34:32.989 A:middle L:90%
the clusters each party will learn which cluster each of

674
00:34:32.989 --> 00:34:37.260 A:middle L:90%
its points is in but won't learn anything else about

675
00:34:37.260 --> 00:34:39.250 A:middle L:90%
the other parties points. Um And the way this

676
00:34:39.250 --> 00:34:45.179 A:middle L:90%
algorithm works is basically doing a depth first search finding

677
00:34:45.190 --> 00:34:46.920 A:middle L:90%
points that are in each other building clusters based on

678
00:34:46.920 --> 00:34:50.650 A:middle L:90%
some constraints of the minimum number of points you want

679
00:34:50.650 --> 00:34:52.159 A:middle L:90%
in a cluster in the density needs. Um The

680
00:34:52.159 --> 00:34:54.650 A:middle L:90%
important thing to notice is it's got lots of array

681
00:34:54.650 --> 00:34:59.800 A:middle L:90%
operations um and it's also using a stack, so

682
00:34:59.800 --> 00:35:00.739 A:middle L:90%
if we want to implement as a circuit, we

683
00:35:00.739 --> 00:35:04.780 A:middle L:90%
need to take advantage of these data structures. Um

684
00:35:04.789 --> 00:35:08.210 A:middle L:90%
some of the operations are within if blocks, so

685
00:35:08.210 --> 00:35:12.260 A:middle L:90%
they're going to be conditional pushes, conditional array updates

686
00:35:12.300 --> 00:35:14.960 A:middle L:90%
, things that we need to implement efficiently as circuits

687
00:35:15.739 --> 00:35:20.980 A:middle L:90%
. Um and this changes of matching and taking advantage

688
00:35:20.980 --> 00:35:22.349 A:middle L:90%
of locality means we can do that much more efficiently

689
00:35:22.360 --> 00:35:25.349 A:middle L:90%
. So um the red line is what you would

690
00:35:25.360 --> 00:35:30.590 A:middle L:90%
get with normal data structures um We're getting up to

691
00:35:30.590 --> 00:35:34.059 A:middle L:90%
even, it's fairly small having 480 points as a

692
00:35:34.059 --> 00:35:36.099 A:middle L:90%
secure computation, takes about 10 hours to run,

693
00:35:36.110 --> 00:35:38.909 A:middle L:90%
uh takes less than an hour with the optimized structures

694
00:35:38.909 --> 00:35:42.900 A:middle L:90%
and the difference will increase as we make things things

695
00:35:42.900 --> 00:35:45.619 A:middle L:90%
bigger. Um So our goal here is to get

696
00:35:45.619 --> 00:35:46.559 A:middle L:90%
to the point where you can take arbitrary programs and

697
00:35:46.559 --> 00:35:51.349 A:middle L:90%
make them run reasonably efficiently as private computations as circuits

698
00:35:52.940 --> 00:35:55.809 A:middle L:90%
. So one of the big questions that that I

699
00:35:55.820 --> 00:35:59.369 A:middle L:90%
haven't addressed and I think is really an important question

700
00:35:59.369 --> 00:36:00.840 A:middle L:90%
to think about and secure computation is how do you

701
00:36:00.840 --> 00:36:04.940 A:middle L:90%
actually get these kinds of things deployed? Right.

702
00:36:04.940 --> 00:36:07.840 A:middle L:90%
So we started from the question of you don't trust

703
00:36:07.840 --> 00:36:10.780 A:middle L:90%
the third party with all your data. Are you

704
00:36:10.780 --> 00:36:13.670 A:middle L:90%
really better off if you end up trusting a third

705
00:36:13.670 --> 00:36:15.730 A:middle L:90%
party to design a protocol for you and give you

706
00:36:15.730 --> 00:36:17.900 A:middle L:90%
code that you use give your data to. Um

707
00:36:19.150 --> 00:36:21.539 A:middle L:90%
and so as a way to start thinking about that

708
00:36:21.550 --> 00:36:27.110 A:middle L:90%
we built a toy android application. You can download

709
00:36:27.110 --> 00:36:29.829 A:middle L:90%
it if you want. Um It doesn't do the

710
00:36:29.840 --> 00:36:31.409 A:middle L:90%
genetic dating application because we don't have enough people with

711
00:36:31.420 --> 00:36:34.949 A:middle L:90%
genomes on their mobile phones yet. But it does

712
00:36:34.949 --> 00:36:37.130 A:middle L:90%
something that's sort of useful and you could argue it

713
00:36:37.139 --> 00:36:39.659 A:middle L:90%
is important for privacy that it takes your address book

714
00:36:40.130 --> 00:36:44.400 A:middle L:90%
um and finds out whether the person that you do

715
00:36:44.400 --> 00:36:46.260 A:middle L:90%
the protocol with any people that you know in common

716
00:36:46.269 --> 00:36:50.039 A:middle L:90%
. So it's doing an intersection of the entries in

717
00:36:50.039 --> 00:36:52.099 A:middle L:90%
your contact list um and it will give you an

718
00:36:52.099 --> 00:36:54.050 A:middle L:90%
output that says here's here's the people you know in

719
00:36:54.050 --> 00:36:58.239 A:middle L:90%
common. Um and it does this using a garbled

720
00:36:58.239 --> 00:37:00.650 A:middle L:90%
circuit protocol with all the security properties like I've described

721
00:37:01.429 --> 00:37:05.760 A:middle L:90%
except when you download this application, install it on

722
00:37:05.760 --> 00:37:07.400 A:middle L:90%
android. The first thing it asks you to do

723
00:37:07.400 --> 00:37:09.530 A:middle L:90%
is give this application full permission to your address book

724
00:37:09.530 --> 00:37:12.639 A:middle L:90%
and full permission to the network. So as a

725
00:37:12.639 --> 00:37:15.050 A:middle L:90%
user unless you sort of read our source code and

726
00:37:15.059 --> 00:37:19.579 A:middle L:90%
understand cryptography and build these protocols yourself. Um It's

727
00:37:19.579 --> 00:37:21.750 A:middle L:90%
only buying you something if if you really trust me

728
00:37:22.329 --> 00:37:23.730 A:middle L:90%
or trust trust the students and implement you can read

729
00:37:23.730 --> 00:37:27.969 A:middle L:90%
the reviews, you know um Both of these are

730
00:37:27.969 --> 00:37:30.079 A:middle L:90%
from well ones from the ones from the student who

731
00:37:30.079 --> 00:37:31.050 A:middle L:90%
did it. So whether you buy the reviews or

732
00:37:31.050 --> 00:37:34.090 A:middle L:90%
not, you know there's nothing that will really convince

733
00:37:34.090 --> 00:37:36.780 A:middle L:90%
you that this is keeping your data private. So

734
00:37:36.780 --> 00:37:37.670 A:middle L:90%
I think that's that's a big open question in this

735
00:37:37.670 --> 00:37:40.690 A:middle L:90%
area and something that um I hope some of you

736
00:37:40.699 --> 00:37:44.809 A:middle L:90%
will make progress on. Um So most of the

737
00:37:44.809 --> 00:37:46.769 A:middle L:90%
work that I talked about was done by john huang

738
00:37:46.780 --> 00:37:52.719 A:middle L:90%
who's finished his PhD? No is I guess a

739
00:37:52.730 --> 00:37:54.719 A:middle L:90%
doctor um Sammy did the work on the data structures

740
00:37:54.719 --> 00:37:57.800 A:middle L:90%
that I talked about at the end um and we

741
00:37:57.800 --> 00:38:00.809 A:middle L:90%
also collaborate with Jonathan katz at University of Maryland who

742
00:38:00.809 --> 00:38:05.489 A:middle L:90%
was as a fantastic cryptographer. So you can download

743
00:38:05.500 --> 00:38:07.559 A:middle L:90%
the code and all the papers from our might be

744
00:38:07.559 --> 00:38:10.199 A:middle L:90%
evil dot com site. Um which I'm happy to

745
00:38:10.199 --> 00:38:13.880 A:middle L:90%
say we pay the domain fees for this from a

746
00:38:13.889 --> 00:38:16.090 A:middle L:90%
gift from google. So they're very happy to sponsor

747
00:38:16.090 --> 00:38:20.130 A:middle L:90%
might be evil. Um And I would be very

748
00:38:20.130 --> 00:38:24.530 A:middle L:90%
happy to take questions. Yes. Okay. Thank

749
00:38:24.530 --> 00:38:34.539 A:middle L:90%
you mm hmm. Mhm. In the year two

750
00:38:36.219 --> 00:38:38.010 A:middle L:90%
this is the same year where gpu computing became very

751
00:38:38.010 --> 00:38:46.320 A:middle L:90%
prevalent. Yeah, kind of expected. This is

752
00:38:46.320 --> 00:39:00.199 A:middle L:90%
one four I thought. Sorry. Right thanks if

753
00:39:00.199 --> 00:39:04.590 A:middle L:90%
you Okay. Yeah. So the question is so

754
00:39:04.590 --> 00:39:07.079 A:middle L:90%
why did we see this dramatic decrease in the cost

755
00:39:07.090 --> 00:39:09.710 A:middle L:90%
of genome sequencing? Um And then the other question

756
00:39:09.710 --> 00:39:15.460 A:middle L:90%
about analyzing circuits. Yeah. Um um So so

757
00:39:15.469 --> 00:39:19.650 A:middle L:90%
there so that the main reason for the genome sequencing

758
00:39:19.659 --> 00:39:22.739 A:middle L:90%
. So if it was just computing power increasing we'd

759
00:39:22.739 --> 00:39:24.159 A:middle L:90%
think it would sort of stay along the moore's law

760
00:39:24.170 --> 00:39:28.719 A:middle L:90%
curve. Um And gpu s are part of that

761
00:39:28.730 --> 00:39:30.539 A:middle L:90%
and and could be you know better parallel algorithms are

762
00:39:30.539 --> 00:39:34.829 A:middle L:90%
part of that. Um The main difference is really

763
00:39:34.829 --> 00:39:38.420 A:middle L:90%
improved algorithms for doing genome assembly um that have reduced

764
00:39:38.429 --> 00:39:42.590 A:middle L:90%
the cost. Um So the old way of doing

765
00:39:42.590 --> 00:39:45.539 A:middle L:90%
genome sequencing um that was used for most of the

766
00:39:45.539 --> 00:39:47.989 A:middle L:90%
human genome project was you had to read a long

767
00:39:47.989 --> 00:39:52.260 A:middle L:90%
sequence and then you tried to align it Um and

768
00:39:52.260 --> 00:39:54.500 A:middle L:90%
you so you would read these long strips of about

769
00:39:54.510 --> 00:39:58.670 A:middle L:90%
500 nucleotides, you get all these out of your

770
00:39:58.670 --> 00:40:00.070 A:middle L:90%
machine and and then you would try to you'll find

771
00:40:00.070 --> 00:40:05.309 A:middle L:90%
the least common superstring that would contain all those in

772
00:40:05.309 --> 00:40:07.420 A:middle L:90%
overlapping them because their errors. It's it's um hard

773
00:40:07.420 --> 00:40:09.739 A:middle L:90%
to know if you've got exactly the right jean amount

774
00:40:09.739 --> 00:40:13.230 A:middle L:90%
of it. Um The big advance in algorithm for

775
00:40:13.230 --> 00:40:15.840 A:middle L:90%
this is now you can do this with really short

776
00:40:15.840 --> 00:40:19.480 A:middle L:90%
snippets and this was sort of came out of craig

777
00:40:19.480 --> 00:40:22.570 A:middle L:90%
venter's work where there was a lot of politics towards

778
00:40:22.570 --> 00:40:23.739 A:middle L:90%
the end of the human genome project and they ended

779
00:40:23.739 --> 00:40:28.820 A:middle L:90%
up sort of there was the publicly funded project that

780
00:40:29.510 --> 00:40:34.309 A:middle L:90%
Francis Collins was leading at the NIH and the competitive

781
00:40:34.309 --> 00:40:37.460 A:middle L:90%
commercial project that craig venter was leading and they were

782
00:40:37.460 --> 00:40:40.820 A:middle L:90%
doing what they called shotgun sequencing where you're having very

783
00:40:40.820 --> 00:40:45.449 A:middle L:90%
short snippets but using um more clever algorithms to be

784
00:40:45.449 --> 00:40:51.059 A:middle L:90%
able to still assemble them correctly um There's always potential

785
00:40:51.059 --> 00:40:52.239 A:middle L:90%
for error. You'd never know if it's really the

786
00:40:52.239 --> 00:40:55.579 A:middle L:90%
correct genome um but it greatly reduces the cost and

787
00:40:55.579 --> 00:41:00.590 A:middle L:90%
then they're they're both biochemical improvements as well as algorithmic

788
00:41:00.590 --> 00:41:02.449 A:middle L:90%
and computing improvements that that really contributed to that that

789
00:41:02.449 --> 00:41:06.719 A:middle L:90%
huge difference. Um The other part of the question

790
00:41:06.719 --> 00:41:09.000 A:middle L:90%
about sort of why use circuits? So for the

791
00:41:09.010 --> 00:41:13.199 A:middle L:90%
genome assembly stuff none of that's done with circuit.

792
00:41:13.199 --> 00:41:17.880 A:middle L:90%
So that's all done with regular maybe some using Gpus

793
00:41:17.880 --> 00:41:22.369 A:middle L:90%
but regular processing on general purpose computing, there's no

794
00:41:22.380 --> 00:41:25.670 A:middle L:90%
um attempts that I know to try to do that

795
00:41:25.679 --> 00:41:29.630 A:middle L:90%
part of it privately. Um The assumption if you

796
00:41:29.630 --> 00:41:31.260 A:middle L:90%
want a genome privacy you do you have to get

797
00:41:31.260 --> 00:41:35.539 A:middle L:90%
your genome sequenced by someone you trust to give you

798
00:41:35.539 --> 00:41:38.659 A:middle L:90%
the genome um and then uh not store it themselves

799
00:41:38.659 --> 00:41:40.840 A:middle L:90%
or do something else with it. Um All the

800
00:41:40.840 --> 00:41:43.949 A:middle L:90%
computations that I I talked about are things that you

801
00:41:43.949 --> 00:41:45.920 A:middle L:90%
would do after that stage where you've you've already got

802
00:41:45.920 --> 00:41:50.010 A:middle L:90%
the data um whether it's a genome or something else

803
00:41:50.019 --> 00:41:52.880 A:middle L:90%
then for the garbled circuit protocol we need to use

804
00:41:52.880 --> 00:41:54.500 A:middle L:90%
circuits because that's the way that we can do the

805
00:41:54.510 --> 00:42:00.170 A:middle L:90%
computing without revealing the data. Um the other interesting

806
00:42:00.170 --> 00:42:01.019 A:middle L:90%
point you bring out using Gpu so one of the

807
00:42:01.019 --> 00:42:04.960 A:middle L:90%
ways to make these protocols a lot faster. They're

808
00:42:04.960 --> 00:42:06.780 A:middle L:90%
highly paralyzed able. So you saw one of the

809
00:42:06.780 --> 00:42:07.960 A:middle L:90%
things we did was pipeline the circuit. So we've

810
00:42:07.969 --> 00:42:10.690 A:middle L:90%
got all these gates, we can do the encryptions

811
00:42:10.690 --> 00:42:14.269 A:middle L:90%
, we can do the gates mostly in parallel other

812
00:42:14.269 --> 00:42:16.030 A:middle L:90%
than dependencies. So um you can certainly get much

813
00:42:16.030 --> 00:42:19.840 A:middle L:90%
better results by using a GPO for this and there's

814
00:42:19.840 --> 00:42:22.019 A:middle L:90%
a few groups working on that. We we haven't

815
00:42:22.030 --> 00:42:24.820 A:middle L:90%
done that in my group but there's definitely a lot

816
00:42:24.820 --> 00:42:30.119 A:middle L:90%
of opportunity to get much better performance if you mhm

817
00:42:30.500 --> 00:42:31.369 A:middle L:90%
run this on a Gpu. And the computations you're

818
00:42:31.369 --> 00:42:34.949 A:middle L:90%
doing there there have been several works trying to make

819
00:42:34.949 --> 00:42:38.110 A:middle L:90%
encryption work fast on Gps um So that is very

820
00:42:38.110 --> 00:42:46.949 A:middle L:90%
paralyzed able to do this. Yeah. Thanks three

821
00:42:46.949 --> 00:42:51.860 A:middle L:90%
steps and the circuit to bomb the other Dallas and

822
00:42:51.860 --> 00:42:57.119 A:middle L:90%
then the equality and then the equality test. Um

823
00:42:59.000 --> 00:43:02.949 A:middle L:90%
and uh so so I have to question the threat

824
00:43:02.949 --> 00:43:07.460 A:middle L:90%
model for the first two steps are still under the

825
00:43:07.460 --> 00:43:10.800 A:middle L:90%
semi honest adversary model. Um And then um I

826
00:43:10.800 --> 00:43:14.610 A:middle L:90%
think the next question is I'm thinking is it possible

827
00:43:14.610 --> 00:43:16.719 A:middle L:90%
at all if you're doing some sort of pipe lining

828
00:43:17.400 --> 00:43:22.570 A:middle L:90%
um and then you could make it more secure in

829
00:43:22.570 --> 00:43:24.260 A:middle L:90%
the sense that if bob does something you know,

830
00:43:24.260 --> 00:43:29.179 A:middle L:90%
premature stopping the computation Alice would stop the computation as

831
00:43:29.179 --> 00:43:30.489 A:middle L:90%
well and then you know, no one gets anything

832
00:43:30.500 --> 00:43:35.820 A:middle L:90%
um you know, is it possible at all?

833
00:43:35.900 --> 00:43:37.289 A:middle L:90%
Okay, good. So the question about, you

834
00:43:37.289 --> 00:43:39.119 A:middle L:90%
know, the threat models for the dual execution protocol

835
00:43:39.300 --> 00:43:43.550 A:middle L:90%
, which probably it's too hard for me to go

836
00:43:43.550 --> 00:43:46.340 A:middle L:90%
back to. Um But so that the 22 important

837
00:43:46.340 --> 00:43:49.309 A:middle L:90%
, but so when you do the semi honest part

838
00:43:50.199 --> 00:43:53.099 A:middle L:90%
um nothing goes back in the middle, right?

839
00:43:53.110 --> 00:43:57.489 A:middle L:90%
So you can't if there's something invalid, like if

840
00:43:57.489 --> 00:44:00.679 A:middle L:90%
you get an error evaluating the circuit because none of

841
00:44:00.679 --> 00:44:02.110 A:middle L:90%
the, you know, some gate doesn't encrypt at

842
00:44:02.110 --> 00:44:05.500 A:middle L:90%
all or there's there's some flaw in the data.

843
00:44:05.889 --> 00:44:08.559 A:middle L:90%
You can't complain about that because if you complain about

844
00:44:08.559 --> 00:44:10.570 A:middle L:90%
that and said, oh I found, you know

845
00:44:10.579 --> 00:44:13.590 A:middle L:90%
, there was something broken the protocol or I didn't

846
00:44:13.590 --> 00:44:15.300 A:middle L:90%
get the gate I needed here. That reveals a

847
00:44:15.300 --> 00:44:19.110 A:middle L:90%
lot of information. It says, well what path

848
00:44:19.489 --> 00:44:22.159 A:middle L:90%
the circuit you were evaluating? Um The circuit could

849
00:44:22.159 --> 00:44:24.050 A:middle L:90%
be constructed to make it fail on some inputs,

850
00:44:24.050 --> 00:44:27.119 A:middle L:90%
but not others. So one of the important things

851
00:44:27.119 --> 00:44:28.690 A:middle L:90%
about the protocol, which which I didn't mention it

852
00:44:28.699 --> 00:44:30.840 A:middle L:90%
, it's good that you bring up, even if

853
00:44:30.849 --> 00:44:32.500 A:middle L:90%
the semi honest parts don't finish, you have to

854
00:44:32.510 --> 00:44:35.780 A:middle L:90%
pretend to keep going, right? So you have

855
00:44:35.780 --> 00:44:37.090 A:middle L:90%
to, as a participant in these protocols, you

856
00:44:37.090 --> 00:44:39.599 A:middle L:90%
have to run through the end. Um because if

857
00:44:39.599 --> 00:44:43.769 A:middle L:90%
you stop in the middle and reveal that something's broken

858
00:44:43.780 --> 00:44:46.429 A:middle L:90%
, that potentially leaks information, the quality test has

859
00:44:46.429 --> 00:44:50.980 A:middle L:90%
to be done um with a malicious security level,

860
00:44:50.989 --> 00:44:52.199 A:middle L:90%
so you can't do that if you did the quality

861
00:44:52.199 --> 00:44:54.980 A:middle L:90%
test at the semi honest level then you're not really

862
00:44:54.980 --> 00:44:59.250 A:middle L:90%
getting anything. Um The interesting thing about the quality

863
00:44:59.250 --> 00:45:00.059 A:middle L:90%
test you can also do that as a dual execution

864
00:45:00.059 --> 00:45:04.269 A:middle L:90%
protocol and that's one way to get the malicious level

865
00:45:04.269 --> 00:45:06.539 A:middle L:90%
security. There are more efficient ways to do it

866
00:45:06.550 --> 00:45:08.699 A:middle L:90%
because it's a simple there's custom protocols to do a

867
00:45:08.699 --> 00:45:10.829 A:middle L:90%
quality test and there's there's one we described in the

868
00:45:10.829 --> 00:45:15.659 A:middle L:90%
paper that does equality tests with militia security so it

869
00:45:15.670 --> 00:45:17.849 A:middle L:90%
provides the correct result. Even if the parties don't

870
00:45:17.860 --> 00:45:22.809 A:middle L:90%
uh it doesn't leak information and it will provide the

871
00:45:22.820 --> 00:45:25.690 A:middle L:90%
correct result. Um Even if the parties are attempting

872
00:45:25.690 --> 00:45:29.159 A:middle L:90%
not to follow the rules. Um And you need

873
00:45:29.159 --> 00:45:30.800 A:middle L:90%
to if you end the semi honest and you don't

874
00:45:30.800 --> 00:45:34.440 A:middle L:90%
have an output because it failed. You have to

875
00:45:34.449 --> 00:45:37.019 A:middle L:90%
make up a random output to pretend to continue with

876
00:45:37.019 --> 00:45:39.440 A:middle L:90%
that protocol and you'll get that you don't have equality

877
00:45:39.449 --> 00:45:42.139 A:middle L:90%
, you'll still like that one bit but you won't

878
00:45:42.139 --> 00:45:53.309 A:middle L:90%
leak more by pretending to continue the protocol. Yes

879
00:46:09.210 --> 00:46:10.869 A:middle L:90%
. Okay. Yes. So the question is could

880
00:46:10.869 --> 00:46:15.599 A:middle L:90%
you um make things more efficient by implementing these circuits

881
00:46:15.610 --> 00:46:16.280 A:middle L:90%
with an F. P. G. A.

882
00:46:17.139 --> 00:46:22.650 A:middle L:90%
And the reason that you really wouldn't want to do

883
00:46:22.650 --> 00:46:24.800 A:middle L:90%
that is um this property that we have for garbled

884
00:46:24.800 --> 00:46:28.570 A:middle L:90%
circuits that we don't reuse gates. All right.

885
00:46:28.570 --> 00:46:31.699 A:middle L:90%
So um if you you know for each gate that

886
00:46:31.699 --> 00:46:36.199 A:middle L:90%
you evaluate in the garbled circuit you're doing encryption operations

887
00:46:36.579 --> 00:46:37.489 A:middle L:90%
you can certainly maybe make those faster. If you

888
00:46:37.489 --> 00:46:40.030 A:middle L:90%
had an F P G a designed to do do

889
00:46:40.030 --> 00:46:44.440 A:middle L:90%
encryption. Um But the circuits that we're building we

890
00:46:44.440 --> 00:46:46.769 A:middle L:90%
can only use once so. Um and each each

891
00:46:46.769 --> 00:46:51.280 A:middle L:90%
gate is not a gate that we would implement as

892
00:46:51.280 --> 00:46:53.050 A:middle L:90%
a small amount of logic in an FDA it's doing

893
00:46:53.050 --> 00:46:55.869 A:middle L:90%
encryption. Um So it doesn't really make sense to

894
00:46:55.869 --> 00:46:59.619 A:middle L:90%
try to build these circuits in hardware. Um In

895
00:46:59.619 --> 00:47:01.150 A:middle L:90%
terms of designing the circuits we can learn a lot

896
00:47:01.150 --> 00:47:05.599 A:middle L:90%
by looking at the ways hardware circuits are designed but

897
00:47:05.599 --> 00:47:07.949 A:middle L:90%
the constraints are quite different for this um Especially because

898
00:47:07.949 --> 00:47:09.860 A:middle L:90%
of, you know, not being able to reuse

899
00:47:09.869 --> 00:47:30.409 A:middle L:90%
any gate. Yes, I wonder thinking of his

900
00:47:30.579 --> 00:47:45.460 A:middle L:90%
or run them. My where? Yes. Yeah

901
00:47:45.469 --> 00:47:47.760 A:middle L:90%
. So there's there's a great question. So the

902
00:47:47.760 --> 00:47:51.510 A:middle L:90%
question is about, you know, what's the connection

903
00:47:51.510 --> 00:47:57.530 A:middle L:90%
between private computation and side channel resistance? Um And

904
00:47:57.539 --> 00:48:00.119 A:middle L:90%
one of the great properties of of being able to

905
00:48:00.119 --> 00:48:01.260 A:middle L:90%
do say the A. E. S encryption as

906
00:48:01.260 --> 00:48:06.079 A:middle L:90%
a private computation is the properties that private computation has

907
00:48:06.670 --> 00:48:08.360 A:middle L:90%
. I guarantee you there's there's no side channel leaks

908
00:48:08.360 --> 00:48:12.650 A:middle L:90%
as well because the whole computation doesn't depend on the

909
00:48:12.650 --> 00:48:14.929 A:middle L:90%
data at all. Um There's no way it could

910
00:48:14.929 --> 00:48:17.539 A:middle L:90%
be leaking anything about that data because uh as long

911
00:48:17.539 --> 00:48:20.650 A:middle L:90%
as the properties is a secure computation is supposed to

912
00:48:20.650 --> 00:48:23.289 A:middle L:90%
have are true. However, you implement it is

913
00:48:23.289 --> 00:48:25.639 A:middle L:90%
not leaking anything about the data because nothing about the

914
00:48:25.639 --> 00:48:30.690 A:middle L:90%
computation actually depends on the data. Um So that's

915
00:48:30.699 --> 00:48:32.329 A:middle L:90%
at least one interesting case where there's a strong connection

916
00:48:32.329 --> 00:48:37.530 A:middle L:90%
between doing computations in this way and knowing that you

917
00:48:37.530 --> 00:48:40.420 A:middle L:90%
don't have any side channel leaks. Um and there

918
00:48:40.420 --> 00:48:45.329 A:middle L:90%
are probably others thinking about uh So so the other

919
00:48:45.340 --> 00:48:49.530 A:middle L:90%
two other interesting connections. One is with verifiable computation

920
00:48:49.539 --> 00:48:52.570 A:middle L:90%
and there are works in progress to be able to

921
00:48:52.570 --> 00:48:54.329 A:middle L:90%
prove that you did the computation, you said you

922
00:48:54.329 --> 00:48:58.949 A:middle L:90%
did as part of a secure computation. Um This

923
00:48:58.960 --> 00:49:01.059 A:middle L:90%
protocol doesn't have that property, but there are other

924
00:49:01.059 --> 00:49:04.260 A:middle L:90%
protocols that as you do the computation, you're also

925
00:49:04.260 --> 00:49:06.880 A:middle L:90%
building up a proof that you did the computation you

926
00:49:06.880 --> 00:49:09.019 A:middle L:90%
were supposed to do. Um So that's a maybe

927
00:49:09.030 --> 00:49:12.599 A:middle L:90%
not directly connected with the question you asked, but

928
00:49:12.610 --> 00:49:16.710 A:middle L:90%
another application of security computation to the problem of verifiable

929
00:49:16.710 --> 00:49:19.869 A:middle L:90%
computation of. Now, you're not so worried about

930
00:49:19.869 --> 00:49:22.690 A:middle L:90%
privacy, you're worried about did you do the computation

931
00:49:22.690 --> 00:49:35.440 A:middle L:90%
you were supposed to thank you, David for.

932
00:49:37.570 --> 00:49:39.090 A:middle L:90%
Okay. Thank you.