1
00:00:00,860 --> 00:00:06,240
Welcome. Our first speaker today is Matt Chang. He's talking about hacking on multi-party

2
00:00:06,240 --> 00:00:11,940
computation. It's okay to take pictures of the speaker. For this talk, give it up for Matt

3
00:00:11,940 --> 00:00:24,400
Chang. All right. Thank you. Okay. So I'm going to talk a little bit about my experience with

4
00:00:24,400 --> 00:00:29,980
multi-party computation. It's something that I first encountered about six years ago. And

5
00:00:29,980 --> 00:00:37,340
I thought it was a really cool topic and wanted to share it with you guys. So what is multi-party

6
00:00:37,340 --> 00:00:43,960
computation? Well, the idea is that you might have multiple parties that want to have private

7
00:00:43,960 --> 00:00:48,820
inputs to a function, but they want to jointly compute that function without revealing what it

8
00:00:48,820 --> 00:00:58,000
is they're computing. And when I first heard this, I know that sounded like magic. But of course,

9
00:00:58,000 --> 00:00:59,000
it's just math, right?

10
00:00:59,440 --> 00:00:59,960
Yeah.

11
00:00:59,960 --> 00:01:05,180
It's just something that might be just as good as magic. So a little bit of history. One of the

12
00:01:05,180 --> 00:01:11,380
first problems that was posed in the area of multi-party computation is called the millionaire's

13
00:01:11,380 --> 00:01:15,820
problem. And I guess nowadays it would probably be the billionaire's problem because millionaire,

14
00:01:16,060 --> 00:01:22,840
that's no big deal now, right? So the idea is that you have two millionaires. They want to

15
00:01:22,840 --> 00:01:29,180
compare their net worth, but they don't want to reveal what that net worth is. So how can they

16
00:01:30,420 --> 00:01:38,680
determine who is the winner in that without revealing it? And so the answer that was first

17
00:01:38,680 --> 00:01:44,340
developed was to use something called garbled circuits. That's a pretty fancy name, but

18
00:01:45,200 --> 00:01:51,220
basically it takes a Boolean circuit and turns it into some sort of encrypted Boolean circuit.

19
00:01:51,380 --> 00:01:58,720
And we'll see a little bit about how they do that. But first, one of the key concepts,

20
00:01:59,760 --> 00:02:07,160
in order to make this work, is called oblivious transfer. And so the idea here, and this is,

21
00:02:07,240 --> 00:02:14,860
I think, one of the first things I was like, well, this is magic, is that say I have two pieces

22
00:02:14,860 --> 00:02:21,040
of information, and you want to request one of them without telling me which one you requested,

23
00:02:22,140 --> 00:02:27,800
and I want to send it to you, but without revealing the one that you didn't request. And so

24
00:02:29,840 --> 00:02:34,700
that's what oblivious transfer does. It allows you to request a piece of information and only get

25
00:02:34,700 --> 00:02:41,440
back what you requested without telling me which one you requested. And this is just like in more

26
00:02:41,440 --> 00:02:50,740
formal language what that is. Okay, so what is the whole garbled circuit protocol? So first,

27
00:02:50,940 --> 00:02:59,160
you have to take your function and describe it as a Boolean circuit. So in the case of the millionaires,

28
00:02:59,180 --> 00:03:05,800
problem, you want to create the greater than comparator operator in terms of the Boolean

29
00:03:05,800 --> 00:03:13,640
circuit. And then, of course, this is a cryptography, so our two players in this protocol are Alice

30
00:03:13,640 --> 00:03:20,700
and Bob. And so Alice garbles or encrypts the circuit, and she sends this garbled circuit

31
00:03:20,700 --> 00:03:29,100
to Bob along with her encrypted inputs. Bob receives the encrypted inputs and does oblivious

32
00:03:29,180 --> 00:03:38,100
transfer to get his encrypted outputs. Or, sorry, you get the encrypted inputs through

33
00:03:38,100 --> 00:03:46,980
oblivious transfer. Bob then evaluates the circuit, and then he needs to communicate back

34
00:03:46,980 --> 00:03:53,180
with Alice to determine what the output of the function is. And this can either be done by just

35
00:03:53,180 --> 00:03:57,980
having Alice find out what the answer is, or they could share the answer. But

36
00:03:59,520 --> 00:04:06,820
this allows evaluation of essentially arbitrary Boolean circuits, but it is relatively so. It

37
00:04:06,820 --> 00:04:17,000
requires a lot of communication. So a different mechanism for doing this kind of multi-party

38
00:04:17,000 --> 00:04:23,540
computation is what's known as homomorphic encryption. And this is something that was

39
00:04:23,540 --> 00:04:29,160
observed early on with one of the first public-key cryptosystems already. And this is a

40
00:04:29,180 --> 00:04:41,520
RSA. And it was observed that RSA exhibits a multiplicatively homomorphic property. Also,

41
00:04:41,640 --> 00:04:48,280
another encryption scheme which isn't quite as widely used, but was defined about the

42
00:04:48,280 --> 00:04:58,340
same time, was Algomol. So they both have this multiplicative property. And just to give a brief

43
00:04:58,340 --> 00:04:59,160
overview of what RSA is, RSA is a multi-party encryption scheme. And RSA is a multi-party

44
00:04:59,180 --> 00:05:04,940
encryption system. I'm not sure if you've heard of this. Briefly, an RSA public key

45
00:05:05,620 --> 00:05:18,180
is a pair of numbers, N and E. And, without getting into details about E and everything,

46
00:05:19,440 --> 00:05:27,600
N is a product of two large primes, P and Q. And to encrypt a message, we simply raise,

47
00:05:27,600 --> 00:05:37,560
We view the message as a number from 0 to N and raise M to the E power.

48
00:05:40,400 --> 00:05:46,560
And it was observed that if you take the ciphertext of two of the two ciphertexts and you multiply them together,

49
00:05:46,780 --> 00:05:52,440
just because of the way that multiplying two numbers with raise the same power works,

50
00:05:52,660 --> 00:05:54,900
that's the same thing as encrypting the product.

51
00:05:54,900 --> 00:05:58,680
So, you have this property.

52
00:05:59,140 --> 00:06:05,080
I could give you two, or you could give me two values that have been encrypted with RSA,

53
00:06:05,300 --> 00:06:07,640
and I can just multiply them together and give that back to you,

54
00:06:07,700 --> 00:06:12,220
and then that's an encryption of the product of the original numbers.

55
00:06:14,140 --> 00:06:20,260
Now, this is, again, with unpadded RSA, sort of a textbook RSA,

56
00:06:20,400 --> 00:06:22,660
but it's an interesting property to observe.

57
00:06:25,300 --> 00:06:32,260
Algamal is a different scheme that isn't as widely used,

58
00:06:32,400 --> 00:06:35,460
and I'm glossing over a bunch of details here,

59
00:06:35,620 --> 00:06:42,760
but the main point is that there's a public key that specifies a prime number,

60
00:06:44,700 --> 00:06:47,080
and I guess there should also be a generator there,

61
00:06:47,140 --> 00:06:50,720
and a public value Y,

62
00:06:51,520 --> 00:06:53,160
and to encrypt...

63
00:06:54,960 --> 00:06:57,380
Each time that somebody encrypts a message,

64
00:06:57,560 --> 00:07:00,040
they generate a random number R,

65
00:07:01,060 --> 00:07:03,260
raise G to the Rth power, mod P,

66
00:07:03,520 --> 00:07:08,260
and multiply the message, M, by Y to the Rth power.

67
00:07:09,000 --> 00:07:11,880
And just like with RSA, this has a multiplicative property.

68
00:07:11,980 --> 00:07:13,640
If you do component-wise multiplication,

69
00:07:15,260 --> 00:07:18,120
in the first component, the exponents add,

70
00:07:18,240 --> 00:07:21,040
but that's just another G to random number.

71
00:07:21,400 --> 00:07:23,940
And in the second component, you have...

72
00:07:24,900 --> 00:07:29,100
The M1 and M2 multiply together, times Y to that same random number

73
00:07:29,100 --> 00:07:30,360
that G is being raised to.

74
00:07:30,820 --> 00:07:36,460
So, it's, again, multiplicatively homomorphic.

75
00:07:36,920 --> 00:07:40,460
But, something that's perhaps a little bit more useful,

76
00:07:41,980 --> 00:07:44,600
and at least something that I actually had used before,

77
00:07:44,780 --> 00:07:46,900
was absolutely homomorphic encryption schemes.

78
00:07:47,720 --> 00:07:48,280
So...

79
00:07:48,860 --> 00:07:50,140
Whoa, that's loud.

80
00:07:53,040 --> 00:07:54,880
The first one is...

81
00:07:55,600 --> 00:07:56,480
Additive Algamal.

82
00:07:56,600 --> 00:08:00,500
So, we could actually modify the Algamal scheme that we saw before

83
00:08:01,040 --> 00:08:03,580
to produce an additively homomorphic scheme.

84
00:08:05,020 --> 00:08:07,140
And then there's also PiA,

85
00:08:07,280 --> 00:08:10,040
which actually works out a little bit better.

86
00:08:10,200 --> 00:08:11,860
But, we'll start off with Additive Algamal.

87
00:08:12,720 --> 00:08:17,320
So, this just requires a slight tweak to the original scheme.

88
00:08:17,480 --> 00:08:21,080
So, instead of multiplying just by the message,

89
00:08:21,180 --> 00:08:24,840
we're going to raise the generator G to the Mth power,

90
00:08:24,900 --> 00:08:29,900
and then, when we multiply component-wise,

91
00:08:30,120 --> 00:08:31,880
the addition will happen in the exponent.

92
00:08:32,740 --> 00:08:37,700
And, though, there is a little bit of a problem with this scheme,

93
00:08:37,820 --> 00:08:41,020
in that, when you try to do the decryption,

94
00:08:41,180 --> 00:08:43,060
you'll do the same process as you do normally,

95
00:08:43,180 --> 00:08:49,180
where what you do to decrypt is raise the first component,

96
00:08:49,320 --> 00:08:52,080
the G, to the X power, that's the private key.

97
00:08:52,860 --> 00:08:53,340
And...

98
00:08:54,400 --> 00:08:54,880
That...

99
00:08:54,900 --> 00:08:58,720
That will give you the Y to the R1 plus R2,

100
00:08:58,800 --> 00:09:00,140
and then you compute its inverse,

101
00:09:00,900 --> 00:09:01,880
do that multiplication,

102
00:09:02,120 --> 00:09:04,760
and you're left with G to the M1 plus M2.

103
00:09:05,400 --> 00:09:09,100
And that is not easy to come up with,

104
00:09:09,200 --> 00:09:12,620
because, in fact, the entire security around this scheme

105
00:09:12,620 --> 00:09:16,080
is that it's hard to determine what the exponent is,

106
00:09:16,160 --> 00:09:18,460
given just the number.

107
00:09:18,560 --> 00:09:22,400
So, that's what's referred to as the discrete log problem.

108
00:09:23,800 --> 00:09:24,320
Um...

109
00:09:25,000 --> 00:09:27,340
But, there's still useful cases for this.

110
00:09:28,140 --> 00:09:28,460
Um...

111
00:09:29,120 --> 00:09:30,240
PiA, on the other hand...

112
00:09:30,240 --> 00:09:33,060
Okay, this is a much longer key generation scheme.

113
00:09:33,500 --> 00:09:33,980
Um...

114
00:09:33,980 --> 00:09:37,440
It uses, uh, in, like, an RSA-style modulus.

115
00:09:38,880 --> 00:09:39,360
Um...

116
00:09:39,360 --> 00:09:40,960
And a bunch of technical details here

117
00:09:41,880 --> 00:09:42,840
that, um...

118
00:09:43,460 --> 00:09:45,100
I'm just having for your sake,

119
00:09:45,180 --> 00:09:47,040
but I don't think that I really need to

120
00:09:47,800 --> 00:09:49,100
talk about all the details.

121
00:09:49,760 --> 00:09:50,240
Um...

122
00:09:53,260 --> 00:09:54,340
A lot of feedback.

123
00:09:55,220 --> 00:09:57,280
Okay, so, um...

124
00:09:58,240 --> 00:10:00,780
But, the upshot of all this...

125
00:10:00,780 --> 00:10:03,500
So, this is the encryption, uh, algorithm.

126
00:10:04,080 --> 00:10:06,940
And then, to decrypt,

127
00:10:07,800 --> 00:10:10,340
it has this nice property that...

128
00:10:10,340 --> 00:10:11,400
Okay, just going back.

129
00:10:11,680 --> 00:10:14,260
You see that, just like with the additive Elgamol,

130
00:10:14,340 --> 00:10:17,860
the message goes in the exponent of this G value.

131
00:10:18,320 --> 00:10:21,280
And so, when you multiply ciphertext together,

132
00:10:22,400 --> 00:10:23,680
you'll have that additive property.

133
00:10:23,680 --> 00:10:27,440
But, um, this essentially allows you

134
00:10:27,440 --> 00:10:31,360
to compute discrete logs, uh, easily

135
00:10:31,360 --> 00:10:34,000
if you have the private key information.

136
00:10:35,860 --> 00:10:36,340
Um...

137
00:10:37,520 --> 00:10:38,000
So...

138
00:10:38,940 --> 00:10:40,660
Uh, so far, I've just talked about

139
00:10:40,660 --> 00:10:42,160
a multiplicatively homomorphic scheme

140
00:10:42,160 --> 00:10:43,580
or an additively homomorphic scheme.

141
00:10:44,060 --> 00:10:46,360
But, um, what would be really nice

142
00:10:46,360 --> 00:10:48,160
is to be able to do both

143
00:10:48,160 --> 00:10:49,660
or have a fully homomorphic scheme.

144
00:10:49,760 --> 00:10:52,620
So, have it so that it, um, can...

145
00:10:53,680 --> 00:10:56,020
the, um, compute addition and multiplication

146
00:10:56,020 --> 00:10:57,120
on the ciphertext.

147
00:10:57,400 --> 00:11:01,040
Um, it turns out that, uh...

148
00:11:01,750 --> 00:11:02,320
So, this is...

149
00:11:02,320 --> 00:11:04,740
This was, I think, first accomplished in 2009

150
00:11:04,740 --> 00:11:06,060
by Craig Gentry.

151
00:11:06,260 --> 00:11:09,380
And what he did was, um...

152
00:11:09,890 --> 00:11:12,280
He used this last-based encryption scheme,

153
00:11:12,480 --> 00:11:15,860
um, that was somewhat homomorphic...

154
00:11:15,860 --> 00:11:16,940
somewhat fully homomorphic.

155
00:11:16,980 --> 00:11:20,120
And what that means is that, um...

156
00:11:20,120 --> 00:11:21,560
you can do addition and multiplication

157
00:11:21,560 --> 00:11:23,480
up to a point, uh,

158
00:11:23,680 --> 00:11:25,000
in particular, you can evaluate

159
00:11:25,720 --> 00:11:27,320
polynomials up to a certain degree.

160
00:11:27,740 --> 00:11:30,000
And it turns out that with his scheme,

161
00:11:30,600 --> 00:11:34,720
um, you could write the decryption circuit

162
00:11:34,720 --> 00:11:39,280
in terms of, uh, this, um...

163
00:11:39,780 --> 00:11:41,220
in terms of polynomials that's small enough

164
00:11:41,220 --> 00:11:44,260
so that you can, um, sort of decrypt

165
00:11:44,880 --> 00:11:47,200
while, uh, homomorphically.

166
00:11:47,660 --> 00:11:49,980
Uh, and then doing one more operation.

167
00:11:50,400 --> 00:11:52,420
So, um...

168
00:11:53,680 --> 00:11:54,900
You can sort of imagine this as

169
00:11:54,900 --> 00:11:57,440
you have, like, two locked boxes,

170
00:11:57,500 --> 00:11:58,700
one inside of the other,

171
00:11:58,820 --> 00:12:02,820
and you're able to unlock the inner box

172
00:12:02,820 --> 00:12:04,860
without having to unlock the outer box.

173
00:12:05,880 --> 00:12:06,440
Um...

174
00:12:07,080 --> 00:12:09,900
So that's, uh, how that works.

175
00:12:10,180 --> 00:12:12,240
Currently, it's still pretty slow.

176
00:12:12,420 --> 00:12:13,800
I know that there have been some improvements,

177
00:12:13,980 --> 00:12:15,260
but, um...

178
00:12:15,940 --> 00:12:17,860
It's generally a pretty slow procedure.

179
00:12:19,180 --> 00:12:19,740
Um...

180
00:12:21,420 --> 00:12:21,980
Now...

181
00:12:22,980 --> 00:12:23,660
This is...

182
00:12:23,680 --> 00:12:27,280
So there was actually a tool that I've used in the past,

183
00:12:27,400 --> 00:12:29,680
although it was pretty tricky to get to work,

184
00:12:29,860 --> 00:12:31,060
but, um...

185
00:12:31,060 --> 00:12:34,600
It's the Tool for Automating Secure Two-Party Computation,

186
00:12:34,660 --> 00:12:35,820
or TASTY for short.

187
00:12:36,320 --> 00:12:36,920
Um...

188
00:12:36,920 --> 00:12:37,880
And...

189
00:12:38,840 --> 00:12:42,340
The language for it was a Python-like language,

190
00:12:42,540 --> 00:12:45,800
um, and what you do is specify

191
00:12:45,800 --> 00:12:48,940
what the client and server operations are,

192
00:12:49,080 --> 00:12:52,080
and it would compile two separate binaries,

193
00:12:52,100 --> 00:12:53,660
a client and server, for you,

194
00:12:53,680 --> 00:12:57,220
um, and it actually supported

195
00:12:57,220 --> 00:12:58,880
both additively homomorphic encryption

196
00:12:58,880 --> 00:13:00,640
and garbled circuits,

197
00:13:00,960 --> 00:13:04,200
so you could actually combine those two operations

198
00:13:04,200 --> 00:13:05,340
into a single protocol.

199
00:13:05,840 --> 00:13:06,480
Um...

200
00:13:06,480 --> 00:13:09,320
So one example of how this might be useful is,

201
00:13:10,200 --> 00:13:12,780
um, say, uh...

202
00:13:13,760 --> 00:13:15,100
This is an example I can think of,

203
00:13:15,140 --> 00:13:17,600
that, uh, in machine learning,

204
00:13:17,820 --> 00:13:20,400
uh, oftentimes, uh,

205
00:13:20,580 --> 00:13:22,360
when you're doing some, like, say, a classification,

206
00:13:22,360 --> 00:13:24,020
um, procedure,

207
00:13:24,680 --> 00:13:25,280
you...

208
00:13:25,280 --> 00:13:27,780
After you've trained your algorithm,

209
00:13:27,980 --> 00:13:29,580
you have some vector

210
00:13:29,580 --> 00:13:34,020
that, um, represents information about your...

211
00:13:34,020 --> 00:13:36,460
what, um, your algorithm is trained,

212
00:13:36,640 --> 00:13:40,460
um, and this may be some sort of proprietary information

213
00:13:40,460 --> 00:13:41,380
that you don't want to share,

214
00:13:41,580 --> 00:13:43,700
um, and correspondingly,

215
00:13:43,720 --> 00:13:46,180
somebody who might want to, um,

216
00:13:46,780 --> 00:13:49,980
run their information against your classifier

217
00:13:49,980 --> 00:13:51,600
doesn't want to actually share the information,

218
00:13:51,600 --> 00:13:54,220
so what you could do is, um,

219
00:13:54,520 --> 00:13:57,700
the client could encrypt their, uh,

220
00:13:58,890 --> 00:14:00,820
the information that would go into the algorithm

221
00:14:00,820 --> 00:14:02,100
and submit it,

222
00:14:02,180 --> 00:14:03,320
and on the server side,

223
00:14:03,520 --> 00:14:08,900
they, uh, keep the, uh, vector in plain text,

224
00:14:09,080 --> 00:14:12,220
and, uh, with an additively homomorphic scheme,

225
00:14:12,440 --> 00:14:15,900
you can compute the inner product of two vectors,

226
00:14:16,100 --> 00:14:18,300
um, where one is encrypted

227
00:14:18,300 --> 00:14:20,480
and the other is just a plain text vector,

228
00:14:20,640 --> 00:14:21,580
because, um,

229
00:14:22,720 --> 00:14:25,340
if you multiply a...

230
00:14:25,340 --> 00:14:27,600
an encrypted number by...

231
00:14:27,600 --> 00:14:29,820
an encrypted value by just a number,

232
00:14:30,020 --> 00:14:33,300
um, then that just works like, uh,

233
00:14:33,560 --> 00:14:36,280
the way that you would think about from grade school

234
00:14:36,280 --> 00:14:37,420
how multiplication works, right,

235
00:14:37,480 --> 00:14:40,940
where you define multiplication as repeated addition,

236
00:14:41,200 --> 00:14:42,620
so you can do the same thing

237
00:14:42,620 --> 00:14:44,140
with an additively homomorphic scheme.

238
00:14:44,540 --> 00:14:47,800
So, um, you could first do that

239
00:14:47,800 --> 00:14:50,060
to come up with a, um,

240
00:14:51,720 --> 00:14:53,840
a value, and then, um,

241
00:14:56,040 --> 00:14:58,360
what you often have to do is compare that to

242
00:14:58,800 --> 00:15:01,440
whether or not, uh, it's greater than or less than

243
00:15:01,440 --> 00:15:03,480
a particular value, so you could then use a garbled circuit

244
00:15:04,460 --> 00:15:08,580
to, uh, compare the, uh, resulting value

245
00:15:08,580 --> 00:15:10,520
with what, um,

246
00:15:12,300 --> 00:15:14,580
the algorithm wants, so, um,

247
00:15:16,680 --> 00:15:17,080
it's...

248
00:15:17,080 --> 00:15:18,740
it was difficult to use, I found.

249
00:15:18,820 --> 00:15:20,900
I think I was only able to get this thing to work

250
00:15:20,900 --> 00:15:21,580
using Gentile,

251
00:15:21,600 --> 00:15:25,140
uh, and a lot of painful work, um,

252
00:15:25,440 --> 00:15:26,620
but, um,

253
00:15:28,200 --> 00:15:30,140
part of the point of this talk was

254
00:15:30,140 --> 00:15:31,840
to show that, um,

255
00:15:32,080 --> 00:15:33,420
there are actually some tools out there

256
00:15:33,420 --> 00:15:35,760
where you can start playing with these kinds of, um,

257
00:15:35,880 --> 00:15:37,400
algorithms and techniques.

258
00:15:38,200 --> 00:15:38,680
Um,

259
00:15:39,680 --> 00:15:41,840
we're going to take a little bit of a detour

260
00:15:41,840 --> 00:15:42,780
from, um,

261
00:15:43,400 --> 00:15:45,680
the hardcore computational aspects

262
00:15:46,220 --> 00:15:47,160
and, um,

263
00:15:47,340 --> 00:15:49,820
talk a little bit about zero knowledge proofs.

264
00:15:50,000 --> 00:15:51,420
So I'm going to, like, speed run

265
00:15:51,420 --> 00:15:54,620
through, um, a blog posting by Matthew Green.

266
00:15:54,800 --> 00:15:57,580
I'm really cribbing this section from his blog post.

267
00:15:57,760 --> 00:15:59,620
Um, he wrote, uh, an awesome blog.

268
00:15:59,760 --> 00:16:02,780
He, uh, I have listed in the references slide,

269
00:16:02,900 --> 00:16:05,660
uh, that explains, uh,

270
00:16:05,860 --> 00:16:07,300
what zero knowledge is all about,

271
00:16:07,420 --> 00:16:11,240
and so the, the main idea behind it is that,

272
00:16:11,260 --> 00:16:15,160
um, I want to convince somebody that I know some information,

273
00:16:15,440 --> 00:16:18,460
uh, but without revealing what that information is,

274
00:16:18,580 --> 00:16:21,400
and we're going to go through a particular example that he wrote.

275
00:16:21,400 --> 00:16:29,440
went through in his blog posting. And so there are three properties of zero knowledge. Completeness,

276
00:16:29,600 --> 00:16:36,340
that means that if I actually know the information that I'm trying to prove, then I can prove

277
00:16:36,340 --> 00:16:42,380
it to you. Soundness means that, in fact, I can only convince you that I know the answer

278
00:16:42,760 --> 00:16:48,140
if I do know the answer to the problem. And the zero knowledge is the part where you're

279
00:16:48,140 --> 00:16:53,960
not able to extract information about the solution from my proof.

280
00:16:56,160 --> 00:17:07,420
So the example Matthew Green gave was a graph recoloring problem. So he picked Google. He

281
00:17:07,420 --> 00:17:15,620
said, like, maybe some customer comes to Google and says, I want you to use all of your computational

282
00:17:15,620 --> 00:17:18,120
power to find the answer to the problem. And so he's like, well, I don't know. I don't

283
00:17:18,120 --> 00:17:18,380
know. I'm gonna try to find the answer to the problem. And so they do, and they find

284
00:17:18,380 --> 00:17:20,900
find the answer. And so they find the three coloring of a graph. And this could be useful

285
00:17:20,900 --> 00:17:26,320
for cell phone providers to make sure that they're not overlapping frequencies at cell

286
00:17:26,320 --> 00:17:32,540
towers. But Google doesn't want to do all this work and then just give it away. And

287
00:17:32,540 --> 00:17:37,340
likewise, their client doesn't want to pay for it unless they are actually sure that

288
00:17:37,340 --> 00:17:45,340
Google did the problem. Right? So you have some graph here, and you have to make sure

289
00:17:45,340 --> 00:17:47,980
that you can find coloring.

290
00:17:47,980 --> 00:17:55,920
colorings with only three colors so that no two colors share an edge. Here's an example

291
00:17:56,540 --> 00:18:04,660
coloring of that graph. This is a small graph, so this is one that would be fairly easy to

292
00:18:04,660 --> 00:18:13,640
just do by hand, but imagine you have a much larger one. Google wants to hide all information,

293
00:18:13,640 --> 00:18:20,260
so it's going to put hats on top of its graph. You imagine that they have this big room with

294
00:18:20,260 --> 00:18:26,160
the graph laid out, and underneath it's colored, but they're going to cover it up with hats,

295
00:18:26,280 --> 00:18:30,600
and what they're going to do to prove that they've solved the problem is say to the customer,

296
00:18:30,780 --> 00:18:39,200
I'll let you pick two hats to reveal what colors they are. And if the customer does

297
00:18:39,200 --> 00:18:43,320
this enough times, they will ultimately be convinced that Google did

298
00:18:43,680 --> 00:18:51,820
actually do the three coloring. So they pick up those two and they see, okay, node seven is

299
00:18:51,820 --> 00:18:59,180
purple and node eight is blue. But one thing that Google doesn't want, so the client's like,

300
00:18:59,280 --> 00:19:03,280
okay, well I might have just gotten lucky that one time. I want you to prove it to me by letting

301
00:19:03,280 --> 00:19:08,320
me do it more times. But if we just left the coloring the same, then they could learn most

302
00:19:08,320 --> 00:19:13,120
of the coloring and maybe even be able to figure out the rest of it on their own.

303
00:19:13,640 --> 00:19:19,400
So what Google does is each time the customer picks up those two hats and puts them back

304
00:19:19,400 --> 00:19:25,960
down, they randomly recolor it, but still making it a valid three coloring. And so

305
00:19:26,730 --> 00:19:33,060
no information about which colors were in the first try will help somebody on the second

306
00:19:33,060 --> 00:19:37,560
try learning more information about the three coloring. At least that's what we hoped for.

307
00:19:38,760 --> 00:19:40,780
And so the...

308
00:19:43,640 --> 00:19:49,760
I hope it's fairly clear that the completeness and soundness portion should be fairly clear

309
00:19:49,760 --> 00:19:55,000
here. The interesting thing is how do we know that this is really not leaking any information

310
00:19:55,000 --> 00:20:01,320
about the three coloring? And so that's where the blog post was really informative for me

311
00:20:01,320 --> 00:20:06,560
was that it illustrates that the way that you have to think about it is how could you

312
00:20:06,560 --> 00:20:11,840
cheat this protocol? And so Matthew Green's solution was time machines.

313
00:20:16,080 --> 00:20:22,280
Now, what does he mean by that? Well, suppose that Google was cheating and just came up

314
00:20:22,280 --> 00:20:26,640
with a random coloring. And any time they got caught, they hop into a DeLorean, go

315
00:20:26,640 --> 00:20:31,620
back in time, and change the coloring. They know which two hats they're going to be picking,

316
00:20:31,720 --> 00:20:34,500
so they're like, all right, we're just going to make sure that those two colors are different.

317
00:20:37,060 --> 00:20:43,260
Now it turns out that this procedure would be indistinguishable from if they had actually

318
00:20:43,260 --> 00:20:50,940
done it correctly. So the point being that if the customer was able to figure out information

319
00:20:50,940 --> 00:20:55,520
about the three coloring from this protocol, then they would have been able to do it from

320
00:20:55,520 --> 00:21:02,000
the cheating protocol with the time machine. But that was garbage. So that's the general

321
00:21:02,000 --> 00:21:06,400
idea of the proof of that. They're not able to extract it when it's actually done correctly.

322
00:21:09,660 --> 00:21:11,640
So this is, again, another tool.

323
00:21:13,260 --> 00:21:19,540
It's developed by the folks at JHU, and Matthew Green in particular, which I haven't had a

324
00:21:19,540 --> 00:21:25,760
chance to play with yet, but I've been meaning to. It's called Charm, and it supports a number

325
00:21:25,760 --> 00:21:33,660
of crypto primitives, including, as it says here, some basic math things, rings and fields,

326
00:21:34,360 --> 00:21:42,820
elliptic curves, and zero-knowledge proofs, all that kind of good stuff. So something

327
00:21:42,820 --> 00:21:43,660
to take a look at.

328
00:21:45,720 --> 00:21:52,280
So why do we go off on this zero-knowledge stuff? Well, there are two security models

329
00:21:52,750 --> 00:22:00,460
for these protocols. There's honest but curious and then the malicious model. And honest but

330
00:22:00,460 --> 00:22:03,780
curious is what you might think. It's just, I'm going to run through the protocol correctly,

331
00:22:03,960 --> 00:22:11,900
and I want to get information about what the other person had put into it, but I'm

332
00:22:11,900 --> 00:22:12,620
not going to try and cheat.

333
00:22:12,820 --> 00:22:15,800
And the malicious one is, I'm going to try and cheat as much as I can, and you have to

334
00:22:15,800 --> 00:22:16,680
try and catch me.

335
00:22:17,440 --> 00:22:22,120
And so that's where the zero-knowledge proofs come in, is that the zero-knowledge proofs

336
00:22:22,120 --> 00:22:26,640
are used to detect cheating and allow somebody to abort if the cheating is detected.

337
00:22:30,100 --> 00:22:35,020
So I'm going to briefly talk about, like, really briefly talk about this protocol that

338
00:22:35,740 --> 00:22:42,480
I helped do some implementation work with six years ago. This is called, it was a secure-text

339
00:22:42,480 --> 00:22:42,720
pattern.

340
00:22:42,820 --> 00:22:50,060
It's a matching algorithm called 5PM. And I'll briefly illustrate. This is the sort

341
00:22:50,060 --> 00:22:56,940
of insecure version of it. The idea behind this protocol is that you set up these what

342
00:22:56,940 --> 00:23:03,580
are called character delay vectors that tell you that if a letter in the pattern that you're

343
00:23:03,580 --> 00:23:09,180
looking for is found, then let's just assume that we found it in our pattern, how many

344
00:23:09,180 --> 00:23:12,800
steps further would we have to go before we reach the end of the pattern? And then we're

345
00:23:12,800 --> 00:23:20,280
going to put a 1 there. And so that's what the vectors over on the left are. And we just

346
00:23:20,280 --> 00:23:30,360
go through the text on the server side, and we add and shift down. And we can use an additively

347
00:23:30,360 --> 00:23:35,660
homomorphic encryption scheme to replace the, replace this insecure version with a version

348
00:23:35,660 --> 00:23:42,780
that operates on encrypted data. And so you can use PyA or, you know, whatever you want.

349
00:23:42,800 --> 00:23:51,420
Additive Algemol, Elliptic Curved Algemol. And that's how the honest but curious version

350
00:23:51,420 --> 00:23:57,200
works. In the malicious model, we use a couple of things. One thing is called threshold encryption,

351
00:23:57,480 --> 00:24:03,760
which allows the two players to jointly come up with an encryption key that they will then

352
00:24:03,760 --> 00:24:11,220
use to encrypt both of their inputs. They actually swap, both go through that same,

353
00:24:12,800 --> 00:24:17,760
you know, text search protocol using some linear algebra, and then they use zero knowledge

354
00:24:17,760 --> 00:24:23,240
proofs to detect if one or the other is cheating and abort in that case. And so I'll quickly

355
00:24:23,800 --> 00:24:31,880
conclude with saying that cryptography generally is kind of about any time that you want, you

356
00:24:31,880 --> 00:24:37,380
wish you had some third, trusted third party who could handle information for you, we're going to

357
00:24:37,380 --> 00:24:42,120
use cryptography to do that instead. And there are some tools out there that you can try to use

358
00:24:43,520 --> 00:24:47,760
some of your own communications. I actually just recently redid the honest but curious

359
00:24:47,760 --> 00:24:53,940
version of that protocol in Python, like during a hackathon at night really quick. But of course,

360
00:24:54,000 --> 00:24:59,900
don't lie on anything that's not been verified. And with that, there are some references, but I'll

361
00:24:59,900 --> 00:25:06,900
be releasing the slides after the talk, so. And I'll tweet about that at Crypto Village. So I

362
00:25:06,900 --> 00:25:09,180
think I'm just out of time. So thank you.

363
00:25:12,120 --> 00:25:12,260
Thank you.