0 00:00:00,000 --> 00:00:30,000 Dear viewer, these subtitles were generated by a machine via the service Trint and therefore are (very) buggy. If you are capable, please help us to create good quality subtitles: https://c3subtitles.de/talk/396 Thanks! 1 00:00:11,380 --> 00:00:13,809 OK, ladies and gentlemen, 2 00:00:13,810 --> 00:00:16,089 our next talk is coming up, 3 00:00:16,090 --> 00:00:18,639 DPE five Pray 4 00:00:18,640 --> 00:00:21,399 for privacy preserving presents, 5 00:00:21,400 --> 00:00:23,589 a framework that allows you to 6 00:00:23,590 --> 00:00:25,899 have better control of your privacy 7 00:00:27,340 --> 00:00:29,649 if you have a space as free 8 00:00:29,650 --> 00:00:30,729 seat next to you. 9 00:00:30,730 --> 00:00:32,438 Could you please raise your hands so 10 00:00:32,439 --> 00:00:34,689 anyone can find seats really 11 00:00:34,690 --> 00:00:36,789 quickly, even for the 12 00:00:36,790 --> 00:00:39,130 people coming in right now? 13 00:00:40,970 --> 00:00:43,279 Now, there will be a notice 14 00:00:43,280 --> 00:00:45,449 about the translation as gift from 15 00:00:45,450 --> 00:00:47,839 D.M. English and talk I Nahdlatul love 16 00:00:47,840 --> 00:00:50,209 about that song Betoota 17 00:00:50,210 --> 00:00:52,519 Steck, Tel Naiman on 18 00:00:52,520 --> 00:00:54,319 Canale Art and Science. 19 00:00:54,320 --> 00:00:56,389 Vean on Don't follow through but 20 00:00:56,390 --> 00:00:57,919 that's about that's fun. 21 00:00:57,920 --> 00:00:59,429 English Nadege. 22 00:00:59,430 --> 00:01:02,179 OK, so we are ready to start 23 00:01:02,180 --> 00:01:04,369 here. We have Ian and 24 00:01:04,370 --> 00:01:06,679 George and let's give them a warm 25 00:01:06,680 --> 00:01:07,910 round of applause. 26 00:01:16,100 --> 00:01:17,719 OK, this is fine. 27 00:01:17,720 --> 00:01:19,009 Yes, all right. 28 00:01:19,010 --> 00:01:20,659 Hi, everyone. I'm Engleberg. 29 00:01:20,660 --> 00:01:22,639 I'm from the University of Waterloo in 30 00:01:22,640 --> 00:01:24,919 Canada. And this is George Denise's from 31 00:01:24,920 --> 00:01:27,769 University College London in London. 32 00:01:27,770 --> 00:01:29,119 Our colleague Nikita Borshoff, 33 00:01:29,120 --> 00:01:30,589 unfortunately, could not be with us 34 00:01:30,590 --> 00:01:32,869 today. So it's just the two of us. 35 00:01:32,870 --> 00:01:34,819 So we're going to be talking about DPE 36 00:01:34,820 --> 00:01:37,009 five PR for privacy preserving 37 00:01:37,010 --> 00:01:38,389 president presents. 38 00:01:38,390 --> 00:01:40,489 No, I 39 00:01:40,490 --> 00:01:42,709 will be talking about PR or private 40 00:01:42,710 --> 00:01:44,659 information retrieval for the first part 41 00:01:44,660 --> 00:01:46,369 of the talk and then we'll turn it over 42 00:01:46,370 --> 00:01:47,059 to George. 43 00:01:47,060 --> 00:01:49,279 Something popped up there doesn't 44 00:01:49,280 --> 00:01:50,280 matter. 45 00:01:50,870 --> 00:01:53,509 And we'll turn it over to George, who 46 00:01:53,510 --> 00:01:55,789 we'll talk about deep five. 47 00:01:55,790 --> 00:01:58,159 So first PR, 48 00:01:58,160 --> 00:01:59,099 what is PR? 49 00:01:59,100 --> 00:02:01,159 So imagine an online 50 00:02:01,160 --> 00:02:01,939 database. 51 00:02:01,940 --> 00:02:03,319 Not too hard to imagine. 52 00:02:03,320 --> 00:02:05,239 There are all kinds of online databases. 53 00:02:05,240 --> 00:02:07,639 Let's say this is a database of patents. 54 00:02:07,640 --> 00:02:09,409 Right. So we have an online database of 55 00:02:09,410 --> 00:02:11,749 all the, say, US patents. 56 00:02:11,750 --> 00:02:13,579 And again, you don't have to imagine too 57 00:02:13,580 --> 00:02:15,319 hard because there really are these 58 00:02:15,320 --> 00:02:17,839 online databases you can query. 59 00:02:17,840 --> 00:02:19,919 OK, and here's Alice. 60 00:02:19,920 --> 00:02:22,009 Alice is a researcher and Alice 61 00:02:22,010 --> 00:02:24,289 wants to look at patent six three six 62 00:02:24,290 --> 00:02:26,359 eight two two seven method of swinging 63 00:02:26,360 --> 00:02:28,489 on a swing. This is a real patent. 64 00:02:28,490 --> 00:02:30,499 It covers pulling the chains of a swing 65 00:02:30,500 --> 00:02:32,659 sideways. So you swing 66 00:02:32,660 --> 00:02:34,339 left to right instead of forward and 67 00:02:34,340 --> 00:02:36,409 backward. Again, this is a real 68 00:02:36,410 --> 00:02:37,410 patent. 69 00:02:38,030 --> 00:02:40,189 It has since been revoked on the grounds 70 00:02:40,190 --> 00:02:41,190 of stupidity, 71 00:02:42,380 --> 00:02:43,550 but it was issued. 72 00:02:48,610 --> 00:02:50,889 So Alice wants 73 00:02:50,890 --> 00:02:52,989 to hook up this patent, but 74 00:02:52,990 --> 00:02:55,059 Alice does not want to 75 00:02:55,060 --> 00:02:57,159 let the database server 76 00:02:57,160 --> 00:02:59,229 know that swings are a 77 00:02:59,230 --> 00:03:01,719 hot new research topic. 78 00:03:01,720 --> 00:03:03,879 OK, now swings, of course, 79 00:03:03,880 --> 00:03:06,009 this is a silly example, 80 00:03:06,010 --> 00:03:08,199 but if you replace swing by like 81 00:03:08,200 --> 00:03:10,659 one three dimethyl mumble, mumble 82 00:03:10,660 --> 00:03:12,009 Alman. All right. 83 00:03:12,010 --> 00:03:13,449 Some some 84 00:03:14,950 --> 00:03:17,079 pharmacological molecule or something 85 00:03:17,080 --> 00:03:18,999 like this, then you can see it might be 86 00:03:19,000 --> 00:03:21,339 very important to be able to look 87 00:03:21,340 --> 00:03:23,469 up things in this database without 88 00:03:23,470 --> 00:03:25,569 revealing to the database what you 89 00:03:25,570 --> 00:03:26,859 were looking for. 90 00:03:26,860 --> 00:03:29,259 Right. Otherwise, the database operator 91 00:03:29,260 --> 00:03:31,569 could themselves then go 92 00:03:31,570 --> 00:03:33,879 and say, oh, someone 93 00:03:33,880 --> 00:03:36,099 is interested in this drug. 94 00:03:36,100 --> 00:03:38,139 We may as well go research that 95 00:03:38,140 --> 00:03:39,069 ourselves. 96 00:03:39,070 --> 00:03:41,529 Right. Or we saw examples 97 00:03:41,530 --> 00:03:43,299 long ago called domain frontrunning. 98 00:03:43,300 --> 00:03:44,889 When you would look up, you would do who 99 00:03:44,890 --> 00:03:46,959 is to see if your favorite 100 00:03:46,960 --> 00:03:48,819 domain name was available. 101 00:03:48,820 --> 00:03:51,159 And the act of doing the WHO is 102 00:03:51,160 --> 00:03:53,739 would cause some unscrupulous 103 00:03:53,740 --> 00:03:55,869 network operators to then go register 104 00:03:55,870 --> 00:03:58,029 it before you can register it and 105 00:03:58,030 --> 00:04:00,429 then sell it to you at an inflated price. 106 00:04:00,430 --> 00:04:02,049 Right. So you want to be able to look up 107 00:04:02,050 --> 00:04:04,119 things in the database without 108 00:04:04,120 --> 00:04:06,579 letting the database itself 109 00:04:06,580 --> 00:04:08,349 know what you asked for. 110 00:04:08,350 --> 00:04:10,239 OK, this is private information 111 00:04:10,240 --> 00:04:11,240 retrieval. 112 00:04:11,860 --> 00:04:13,419 OK, no to that. 113 00:04:13,420 --> 00:04:15,789 We're not talking about anonymity. 114 00:04:15,790 --> 00:04:18,099 We're not hiding Alice's identity here. 115 00:04:18,100 --> 00:04:20,139 The problem isn't that we're hiding the 116 00:04:20,140 --> 00:04:22,149 fact that Alice is the one looking up 117 00:04:22,150 --> 00:04:24,369 swing's what we're trying to hide 118 00:04:24,370 --> 00:04:27,249 is that swings are interesting, 119 00:04:27,250 --> 00:04:29,499 right? That anybody is looking up swings 120 00:04:29,500 --> 00:04:31,719 at all. Of course, if you want 121 00:04:31,720 --> 00:04:32,720 to 122 00:04:33,820 --> 00:04:36,339 add anonymity on top of this, no problem. 123 00:04:36,340 --> 00:04:38,469 You just add Tor to it or something like 124 00:04:38,470 --> 00:04:40,599 that and it works just fine, 125 00:04:40,600 --> 00:04:42,609 but you don't have to. 126 00:04:42,610 --> 00:04:44,679 And in fact, you can have business models 127 00:04:44,680 --> 00:04:46,929 based on PR that have that 128 00:04:46,930 --> 00:04:49,309 allow us to pay for these private 129 00:04:49,310 --> 00:04:51,489 workups. So Alice logs 130 00:04:51,490 --> 00:04:53,199 in, authenticates herself, then does a 131 00:04:53,200 --> 00:04:54,819 private look up and may pay for the 132 00:04:54,820 --> 00:04:57,339 privilege of doing a private lookup. 133 00:04:57,340 --> 00:04:59,740 OK, so. 134 00:05:01,220 --> 00:05:04,729 Alice, does this PR query 135 00:05:04,730 --> 00:05:07,069 and the idea is that 136 00:05:07,070 --> 00:05:09,409 the server has no idea what 137 00:05:09,410 --> 00:05:11,689 it was, Alice looked up. 138 00:05:11,690 --> 00:05:14,059 OK, now you may be thinking to yourself, 139 00:05:14,060 --> 00:05:16,919 this is clearly impossible. 140 00:05:16,920 --> 00:05:18,229 Who's thinking this is clearly 141 00:05:18,230 --> 00:05:19,369 impossible? 142 00:05:19,370 --> 00:05:20,389 Right. Right. 143 00:05:20,390 --> 00:05:22,189 It is clearly impossible. 144 00:05:22,190 --> 00:05:24,529 Yet the magic of cryptography 145 00:05:24,530 --> 00:05:26,329 is such that things that are clearly 146 00:05:26,330 --> 00:05:28,789 impossible are often straightforward 147 00:05:28,790 --> 00:05:29,870 and vice versa. 148 00:05:35,400 --> 00:05:37,529 So here's a simple example 149 00:05:37,530 --> 00:05:40,109 called the trivial PR protocol 150 00:05:40,110 --> 00:05:42,929 to show you that it's not impossible. 151 00:05:42,930 --> 00:05:45,089 Alice connects to the server, says, 152 00:05:45,090 --> 00:05:47,159 I would like a patent, please, on the 153 00:05:47,160 --> 00:05:49,229 server, says, OK, here's all the 154 00:05:49,230 --> 00:05:52,019 patents. Look it up yourself. 155 00:05:52,020 --> 00:05:54,629 OK, clearly this is completely 156 00:05:54,630 --> 00:05:57,269 private. The server hustla no information 157 00:05:57,270 --> 00:06:00,239 about what patent Alice was looking for, 158 00:06:00,240 --> 00:06:01,649 but at the same time, this is a 159 00:06:01,650 --> 00:06:03,209 ridiculous protocol. 160 00:06:03,210 --> 00:06:05,429 Why it sends way too much 161 00:06:05,430 --> 00:06:08,189 data right off the databases 162 00:06:08,190 --> 00:06:09,930 of any reasonable size. 163 00:06:11,950 --> 00:06:13,809 You're not going to be able to send all 164 00:06:13,810 --> 00:06:15,669 that information to house in a reasonable 165 00:06:15,670 --> 00:06:17,349 amount of time. 166 00:06:17,350 --> 00:06:19,509 OK, and there are other objections 167 00:06:19,510 --> 00:06:21,869 to the to the trivial 168 00:06:21,870 --> 00:06:24,549 Pyaar protocol as well. 169 00:06:24,550 --> 00:06:26,979 So what we aim for 170 00:06:26,980 --> 00:06:29,169 in better PR protocols is 171 00:06:29,170 --> 00:06:32,199 to achieve the same level of privacy 172 00:06:32,200 --> 00:06:34,360 while sending much less data. 173 00:06:36,130 --> 00:06:38,409 OK, and we're going to see a simple 174 00:06:38,410 --> 00:06:40,599 example of a protocol in 175 00:06:40,600 --> 00:06:42,849 a few minutes just to let you know 176 00:06:42,850 --> 00:06:45,609 that this is a real possible thing. 177 00:06:45,610 --> 00:06:47,799 OK, there are a couple 178 00:06:47,800 --> 00:06:50,079 of main categories 179 00:06:50,080 --> 00:06:52,929 of PR protocols. 180 00:06:52,930 --> 00:06:55,659 The first is called computational PR. 181 00:06:55,660 --> 00:06:58,329 And this is where the security 182 00:06:58,330 --> 00:07:00,489 of the PR system relies on 183 00:07:00,490 --> 00:07:02,829 the fact that the 184 00:07:02,830 --> 00:07:05,319 server who is your adversary, 185 00:07:05,320 --> 00:07:07,449 the server is trying to learn what you're 186 00:07:07,450 --> 00:07:09,729 asking for and you're trying to not let 187 00:07:09,730 --> 00:07:10,869 it. 188 00:07:10,870 --> 00:07:12,849 So you're relying on the fact in 189 00:07:12,850 --> 00:07:15,009 computational PR that the 190 00:07:15,010 --> 00:07:17,169 server is computationally limited, it 191 00:07:17,170 --> 00:07:19,509 doesn't have an infinite computing 192 00:07:19,510 --> 00:07:22,089 power, and in particular, it can't break 193 00:07:22,090 --> 00:07:24,370 certain types of public key cryptography. 194 00:07:25,740 --> 00:07:28,379 OK, so a brief taste 195 00:07:28,380 --> 00:07:29,879 of how it works, I won't go into the 196 00:07:29,880 --> 00:07:31,649 details on this one. 197 00:07:31,650 --> 00:07:34,199 Basically, Alice takes her query 198 00:07:35,220 --> 00:07:37,949 and encrypts it. 199 00:07:37,950 --> 00:07:40,469 But unlike the case where Alice 200 00:07:40,470 --> 00:07:42,809 is, say, connecting to the server 201 00:07:42,810 --> 00:07:45,389 over, for example, tells 202 00:07:45,390 --> 00:07:47,519 where what Alice would do is 203 00:07:47,520 --> 00:07:50,069 take the query, encrypt it to the servers 204 00:07:50,070 --> 00:07:52,319 publicly and send it so 205 00:07:52,320 --> 00:07:54,659 that third parties can read it 206 00:07:54,660 --> 00:07:57,119 here. Alice is trying to protect 207 00:07:57,120 --> 00:08:00,059 the query from the server itself. 208 00:08:00,060 --> 00:08:02,589 And so Alice doesn't encrypt 209 00:08:02,590 --> 00:08:04,019 the query to the servers. 210 00:08:04,020 --> 00:08:06,299 Public key Alice encrypts the query 211 00:08:06,300 --> 00:08:08,879 to her own public key. 212 00:08:08,880 --> 00:08:09,989 This is weird. 213 00:08:09,990 --> 00:08:11,519 How is the server going to be able to 214 00:08:11,520 --> 00:08:12,599 read it? Well, that's the point. 215 00:08:12,600 --> 00:08:14,489 The server isn't going to be able to read 216 00:08:14,490 --> 00:08:16,769 it. And then Alice sends the encrypted 217 00:08:16,770 --> 00:08:18,719 query over to the server. 218 00:08:18,720 --> 00:08:20,549 So what can the server do with this 219 00:08:20,550 --> 00:08:22,439 encrypt encrypted query? 220 00:08:22,440 --> 00:08:24,629 Well, it turns out there's some kinds 221 00:08:24,630 --> 00:08:26,849 of public key encryption that 222 00:08:26,850 --> 00:08:28,949 allow for an operation 223 00:08:28,950 --> 00:08:31,139 that's technically called home amorphous. 224 00:08:31,140 --> 00:08:32,699 And you might have heard in the news 225 00:08:32,700 --> 00:08:34,918 about recent results in so-called 226 00:08:34,919 --> 00:08:37,288 fully Haoma morphic cryptography, 227 00:08:37,289 --> 00:08:39,538 which promises to allow all kinds 228 00:08:39,539 --> 00:08:41,939 of crazy computation, not only exorbitant 229 00:08:41,940 --> 00:08:42,940 costs. 230 00:08:44,550 --> 00:08:46,949 But this isn't that this is 231 00:08:46,950 --> 00:08:48,989 the simpler kind of what's called 232 00:08:48,990 --> 00:08:51,029 partially homo morphic cryptography 233 00:08:51,030 --> 00:08:53,129 that's actually totally reasonable. 234 00:08:53,130 --> 00:08:55,259 And what it allows 235 00:08:55,260 --> 00:08:57,419 is for the server to take the encrypted 236 00:08:57,420 --> 00:09:00,059 query encrypted with Alice's public key 237 00:09:00,060 --> 00:09:02,339 and the plain text database and 238 00:09:02,340 --> 00:09:04,349 combine them to form an encrypted 239 00:09:04,350 --> 00:09:06,749 response still encrypted with Alice's 240 00:09:06,750 --> 00:09:09,029 public key, even though the database 241 00:09:09,030 --> 00:09:11,369 can't decrypt the query or 242 00:09:11,370 --> 00:09:12,659 the response. 243 00:09:12,660 --> 00:09:14,759 And then the database sends that 244 00:09:14,760 --> 00:09:16,379 encrypted response back to Alice, who 245 00:09:16,380 --> 00:09:16,989 decrypt it. 246 00:09:16,990 --> 00:09:18,959 So that's the general structure of 247 00:09:18,960 --> 00:09:20,640 computational pyaar. 248 00:09:21,730 --> 00:09:23,819 Now, these Haoma morphic operations are 249 00:09:23,820 --> 00:09:26,070 somewhat expensive, and so 250 00:09:27,150 --> 00:09:29,609 it kind of sometimes costs a lot 251 00:09:29,610 --> 00:09:32,459 to do these kind of computational 252 00:09:32,460 --> 00:09:33,899 pyaar queries. 253 00:09:33,900 --> 00:09:35,969 So there's another kind of picture 254 00:09:35,970 --> 00:09:38,229 called information theoretic, Piara. 255 00:09:38,230 --> 00:09:40,289 It's here and 256 00:09:40,290 --> 00:09:41,290 here. 257 00:09:42,030 --> 00:09:44,819 What you have is that 258 00:09:44,820 --> 00:09:47,009 the servers are no 259 00:09:47,010 --> 00:09:48,809 longer computationally limited. 260 00:09:48,810 --> 00:09:51,089 Now the servers are allowed 261 00:09:51,090 --> 00:09:53,289 to have unlimited computational power, 262 00:09:53,290 --> 00:09:55,739 a quantum computer, magic computer, 263 00:09:55,740 --> 00:09:57,719 whatever. They can compute anything they 264 00:09:57,720 --> 00:10:00,059 want in no time and. 265 00:10:01,080 --> 00:10:03,599 Alice's query is still protected, 266 00:10:03,600 --> 00:10:05,549 even against unlimited computational 267 00:10:05,550 --> 00:10:08,219 power. How can that possibly be? 268 00:10:08,220 --> 00:10:10,739 Well, we use a different security 269 00:10:10,740 --> 00:10:12,629 assumption, not one based on 270 00:10:12,630 --> 00:10:14,759 cryptography, but one based on 271 00:10:14,760 --> 00:10:17,159 information theory and same information 272 00:10:17,160 --> 00:10:18,160 theoretic. 273 00:10:19,140 --> 00:10:20,879 And here the idea is you have to have 274 00:10:20,880 --> 00:10:23,009 multiple servers. 275 00:10:23,010 --> 00:10:25,559 And Alice asks a question 276 00:10:25,560 --> 00:10:27,809 of each of the servers 277 00:10:27,810 --> 00:10:30,269 and gets back the responses 278 00:10:30,270 --> 00:10:33,269 and then combines those responses 279 00:10:34,500 --> 00:10:36,779 in order to 280 00:10:36,780 --> 00:10:39,299 get her her answer. 281 00:10:39,300 --> 00:10:41,669 Now, the security property 282 00:10:41,670 --> 00:10:44,579 we have is a non collusion assumption. 283 00:10:44,580 --> 00:10:47,369 So we have to assume that some, 284 00:10:47,370 --> 00:10:49,499 at least some threshold of 285 00:10:49,500 --> 00:10:51,749 these various servers are honest 286 00:10:51,750 --> 00:10:53,669 and not colluding with each other. 287 00:10:53,670 --> 00:10:55,949 To try to break Alice's 288 00:10:55,950 --> 00:10:57,779 privacy in this kind of non collusion 289 00:10:57,780 --> 00:10:59,999 assumption is common 290 00:11:00,000 --> 00:11:02,669 in privacy enhancing technologies. 291 00:11:02,670 --> 00:11:04,379 Things like Tor, of course, use it. 292 00:11:04,380 --> 00:11:06,299 If all of the servers and you're in your 293 00:11:06,300 --> 00:11:07,799 path are colluding against you, you're 294 00:11:07,800 --> 00:11:09,659 kind of scrod. 295 00:11:09,660 --> 00:11:10,920 How did that come up on the. 296 00:11:13,620 --> 00:11:15,389 Yeah. If all the servers are colluding 297 00:11:15,390 --> 00:11:16,779 against you, that's bad. 298 00:11:16,780 --> 00:11:18,899 And some kinds of 299 00:11:18,900 --> 00:11:20,639 electronic voting have this kind of non 300 00:11:20,640 --> 00:11:22,019 collusion assumption. So this is a pretty 301 00:11:22,020 --> 00:11:23,020 typical assumption. 302 00:11:24,220 --> 00:11:26,999 So and then there are ways that 303 00:11:27,000 --> 00:11:29,189 combine these to combine a little bit 304 00:11:29,190 --> 00:11:31,319 of computational protection with a little 305 00:11:31,320 --> 00:11:33,369 bit of information theoretic protection 306 00:11:33,370 --> 00:11:35,219 if you want a bit of each. 307 00:11:35,220 --> 00:11:37,649 OK, so that's information 308 00:11:37,650 --> 00:11:39,209 information theoretic, Piara. 309 00:11:39,210 --> 00:11:41,279 And the advantage of it is 310 00:11:41,280 --> 00:11:43,709 it's much faster, like 70 to 100 times 311 00:11:43,710 --> 00:11:46,739 faster than computational K.R.. 312 00:11:46,740 --> 00:11:48,869 Right. So that's a bit 313 00:11:48,870 --> 00:11:50,879 of an advantage there. 314 00:11:50,880 --> 00:11:53,369 OK, but on the downside, you need these 315 00:11:53,370 --> 00:11:55,919 multiple servers. 316 00:11:55,920 --> 00:11:57,420 So that's the tradeoff you're making. 317 00:11:58,660 --> 00:12:00,959 OK, so let's 318 00:12:00,960 --> 00:12:03,989 look at a simple example 319 00:12:03,990 --> 00:12:06,179 of an information theoretic picture 320 00:12:06,180 --> 00:12:07,259 just so you can have a little taste. 321 00:12:07,260 --> 00:12:09,959 And I'm going to do a little bit of math. 322 00:12:09,960 --> 00:12:11,519 Who's scared? Who likes math? 323 00:12:11,520 --> 00:12:12,520 Yay, math. 324 00:12:13,560 --> 00:12:15,749 OK, it's going to be pretty easy math. 325 00:12:15,750 --> 00:12:17,849 Like in some countries, high 326 00:12:17,850 --> 00:12:19,499 school math and other countries may be 327 00:12:19,500 --> 00:12:20,999 first year college math. 328 00:12:21,000 --> 00:12:22,649 OK, so depen. 329 00:12:22,650 --> 00:12:24,149 Yeah, it depends where you are. 330 00:12:24,150 --> 00:12:25,199 It's around then. 331 00:12:25,200 --> 00:12:27,329 So it's, it's vectors and matrices. 332 00:12:27,330 --> 00:12:29,349 Who's happy with vectors and matrices. 333 00:12:29,350 --> 00:12:31,889 Who. OK, so vectors 334 00:12:31,890 --> 00:12:33,449 and matrices. 335 00:12:33,450 --> 00:12:35,429 So this will be if you're happy with that 336 00:12:35,430 --> 00:12:37,679 it'll be easy if not just come along 337 00:12:37,680 --> 00:12:39,509 and, and pretend you know the words. 338 00:12:39,510 --> 00:12:40,510 So 339 00:12:42,210 --> 00:12:44,189 we're going to say our database, we're 340 00:12:44,190 --> 00:12:46,619 going to represent it as a matrix, 341 00:12:46,620 --> 00:12:49,469 like a matrix is just a rectangular 342 00:12:49,470 --> 00:12:51,779 block of in this case, bits, 343 00:12:51,780 --> 00:12:53,909 zeros and ones where each 344 00:12:53,910 --> 00:12:56,939 row is one record of the database. 345 00:12:56,940 --> 00:12:58,889 So the first row is record one, the next 346 00:12:58,890 --> 00:13:00,449 rose record to the next rose, record 347 00:13:00,450 --> 00:13:01,079 three and so on. 348 00:13:01,080 --> 00:13:03,149 And let's say there are rows in this 349 00:13:03,150 --> 00:13:05,579 database and each 350 00:13:05,580 --> 00:13:07,529 record is SBX long. 351 00:13:07,530 --> 00:13:10,669 So this is an R by S matrix, 352 00:13:10,670 --> 00:13:11,670 OK? 353 00:13:12,120 --> 00:13:14,849 And what the queerer wants to do 354 00:13:14,850 --> 00:13:17,099 is retrieve one of the records. 355 00:13:17,100 --> 00:13:19,229 Right. Say the third one, this one 356 00:13:19,230 --> 00:13:21,059 here. So it wants to retrieve one of the 357 00:13:21,060 --> 00:13:23,579 rows of the database. 358 00:13:23,580 --> 00:13:25,649 OK, so in 359 00:13:25,650 --> 00:13:28,289 order for this PR system to work, 360 00:13:28,290 --> 00:13:30,719 we just need to recall two facts 361 00:13:30,720 --> 00:13:32,879 from maybe high school, maybe first year 362 00:13:32,880 --> 00:13:33,880 college math. 363 00:13:35,100 --> 00:13:37,169 One is if you take 364 00:13:37,170 --> 00:13:38,759 the elementary vector, 365 00:13:39,900 --> 00:13:42,959 if you take the elementary vector II, 366 00:13:42,960 --> 00:13:45,129 which is all zeros except for 367 00:13:45,130 --> 00:13:47,189 a one in the eighth place. 368 00:13:47,190 --> 00:13:49,739 Right. So this would be three here. 369 00:13:49,740 --> 00:13:50,969 Right. 370 00:13:50,970 --> 00:13:53,219 If you take eEye, this vector 371 00:13:53,220 --> 00:13:55,409 of length R 372 00:13:55,410 --> 00:13:59,009 and multiply it by this matrix. 373 00:13:59,010 --> 00:14:00,359 In fact, when's the last time I did 374 00:14:00,360 --> 00:14:01,499 matrix math? 375 00:14:01,500 --> 00:14:02,519 How does this go? 376 00:14:02,520 --> 00:14:04,799 You turn sideways and you multiply anyway 377 00:14:04,800 --> 00:14:05,789 you can trust me. 378 00:14:05,790 --> 00:14:08,219 What comes out is the throw 379 00:14:08,220 --> 00:14:10,619 of the matrix 380 00:14:10,620 --> 00:14:12,689 i.e. block I of the 381 00:14:12,690 --> 00:14:13,899 database. 382 00:14:13,900 --> 00:14:16,049 OK, so of course 383 00:14:16,050 --> 00:14:17,849 you could say, well that's our protocol. 384 00:14:17,850 --> 00:14:20,609 Then you, you construct this 385 00:14:20,610 --> 00:14:23,429 vector containing the, 386 00:14:23,430 --> 00:14:25,619 the index of 387 00:14:25,620 --> 00:14:27,749 the record you're interested in, you send 388 00:14:27,750 --> 00:14:30,059 it to the server, the server multiplies 389 00:14:30,060 --> 00:14:32,159 it by D and sends you your answer. 390 00:14:32,160 --> 00:14:34,169 But of course that's not private. 391 00:14:34,170 --> 00:14:36,269 Right. The server can just look at 392 00:14:36,270 --> 00:14:38,369 this vector and say, oh, the one is in 393 00:14:38,370 --> 00:14:40,379 the third place. You're looking up record 394 00:14:40,380 --> 00:14:42,329 three, no privacy. 395 00:14:42,330 --> 00:14:44,699 So the second piece of 396 00:14:44,700 --> 00:14:46,049 high school math we need is the 397 00:14:46,050 --> 00:14:47,070 distributive law. 398 00:14:48,270 --> 00:14:49,899 OK, you may recognize the distributive 399 00:14:49,900 --> 00:14:52,079 law as working on numbers, 400 00:14:52,080 --> 00:14:54,389 but it also works on on vectors 401 00:14:54,390 --> 00:14:55,949 and matrices. It works just fine. 402 00:14:55,950 --> 00:14:58,139 So what's the distributive V one 403 00:14:58,140 --> 00:15:00,149 time Z plus be two times D plus did it 404 00:15:00,150 --> 00:15:00,569 plus V. 405 00:15:00,570 --> 00:15:03,089 All times the is the some of the veejays 406 00:15:03,090 --> 00:15:05,299 times D so how 407 00:15:05,300 --> 00:15:07,709 are we going to make a PR 408 00:15:07,710 --> 00:15:08,699 protocol? 409 00:15:08,700 --> 00:15:10,739 You may be able to see it just from these 410 00:15:10,740 --> 00:15:13,109 lines. So here's how it's going to work 411 00:15:13,110 --> 00:15:14,910 out. Let's say Alice wants 412 00:15:15,930 --> 00:15:17,309 row three of the database. 413 00:15:17,310 --> 00:15:19,379 Alice constructs II doesn't send it 414 00:15:19,380 --> 00:15:20,819 to anybody. 415 00:15:20,820 --> 00:15:23,249 Alice then picks that say there are 416 00:15:23,250 --> 00:15:24,419 L servers. 417 00:15:25,500 --> 00:15:28,109 Alice picks L completely 418 00:15:28,110 --> 00:15:30,179 random vectors zero one 419 00:15:30,180 --> 00:15:32,879 vectors under the condition 420 00:15:32,880 --> 00:15:35,399 that they add up to eEye 421 00:15:35,400 --> 00:15:37,529 mod to all 422 00:15:37,530 --> 00:15:39,569 binaries are going to mod two. 423 00:15:39,570 --> 00:15:40,859 OK, so how does she do that? 424 00:15:40,860 --> 00:15:43,139 The easiest way is just pick L minus one 425 00:15:43,140 --> 00:15:45,419 completely random vectors 426 00:15:45,420 --> 00:15:47,519 and then figure out what the last 427 00:15:47,520 --> 00:15:49,619 one has to be so they all add up. 428 00:15:49,620 --> 00:15:51,869 So eEye minus the some of the ones 429 00:15:51,870 --> 00:15:54,509 you have already right now, you have l 430 00:15:54,510 --> 00:15:56,759 completely random vectors and you send 431 00:15:56,760 --> 00:15:58,409 V one to serve one, V two to serve or 432 00:15:58,410 --> 00:16:00,689 two. V three to serve a three and so on. 433 00:16:00,690 --> 00:16:02,789 And each server is getting just a 434 00:16:02,790 --> 00:16:04,949 random string and that if 435 00:16:04,950 --> 00:16:06,989 you work it out, contains very formally 436 00:16:06,990 --> 00:16:09,299 absolutely no information 437 00:16:09,300 --> 00:16:11,670 about this number three here. 438 00:16:13,080 --> 00:16:15,269 OK, so each server gets absolutely no 439 00:16:15,270 --> 00:16:18,299 information. In fact, any coalition 440 00:16:18,300 --> 00:16:20,399 of as many servers as you 441 00:16:20,400 --> 00:16:22,769 want, as long as it's not all of them 442 00:16:22,770 --> 00:16:25,469 has no information about AI. 443 00:16:25,470 --> 00:16:27,209 And then what is the protocol? 444 00:16:27,210 --> 00:16:29,729 Each server just multiplies the V, 445 00:16:29,730 --> 00:16:31,440 it gets by the database. 446 00:16:32,490 --> 00:16:34,309 Gets the answer, sends the answer back to 447 00:16:34,310 --> 00:16:36,689 Alice, like this one, Alice just adds 448 00:16:36,690 --> 00:16:38,939 up the answers by the distributor FVA 449 00:16:38,940 --> 00:16:41,489 That's the sum of the Veejays Times D 450 00:16:41,490 --> 00:16:43,199 But the some of the veejays we chose to 451 00:16:43,200 --> 00:16:45,419 buy, which is this Anei Times 452 00:16:45,420 --> 00:16:47,009 D is Bloche Puf. 453 00:16:52,390 --> 00:16:54,729 OK, so is this actually 454 00:16:54,730 --> 00:16:56,799 more efficient transfers, 455 00:16:56,800 --> 00:16:59,229 less information than 456 00:16:59,230 --> 00:17:01,419 the naïf, just download 457 00:17:01,420 --> 00:17:04,358 the entire thing, the trivial protocol? 458 00:17:04,359 --> 00:17:06,489 Well, how much data does Alice 459 00:17:06,490 --> 00:17:07,779 send each server? 460 00:17:07,780 --> 00:17:10,479 It's a vector of length are 461 00:17:10,480 --> 00:17:12,549 so Alice sends are bits to each 462 00:17:12,550 --> 00:17:14,618 server. And how much does she get back? 463 00:17:14,619 --> 00:17:16,749 Well, this time this is 464 00:17:16,750 --> 00:17:18,319 a is a vector of length. 465 00:17:19,990 --> 00:17:22,629 So Alice gets bits back. 466 00:17:22,630 --> 00:17:24,709 OK, so are plus 467 00:17:24,710 --> 00:17:27,338 s bits are transferred between 468 00:17:27,339 --> 00:17:29,079 Alice and each server. 469 00:17:29,080 --> 00:17:30,459 And how many bits are there in the 470 00:17:30,460 --> 00:17:33,249 database. It's our times s bits 471 00:17:33,250 --> 00:17:35,529 which is much, much bigger for 472 00:17:35,530 --> 00:17:37,989 any reasonable use of our in us. 473 00:17:37,990 --> 00:17:41,139 Right. And in fact we get the best 474 00:17:41,140 --> 00:17:43,209 protocol if our interests 475 00:17:43,210 --> 00:17:44,979 are about equal. If this database is 476 00:17:44,980 --> 00:17:46,959 squarish, then you're sending about the 477 00:17:46,960 --> 00:17:48,999 square root of the size of the database 478 00:17:49,000 --> 00:17:51,129 to each server and receiving the square 479 00:17:51,130 --> 00:17:52,130 root back. 480 00:17:53,990 --> 00:17:56,059 OK, so two times the square root 481 00:17:56,060 --> 00:17:57,679 of N if and is the number of bits of the 482 00:17:57,680 --> 00:17:59,869 database times l 483 00:17:59,870 --> 00:18:02,059 the number of servers as opposed to 484 00:18:02,060 --> 00:18:04,279 and the size of the whole 485 00:18:04,280 --> 00:18:06,469 database and the square root of N 486 00:18:06,470 --> 00:18:08,689 is much smaller than anif and is of 487 00:18:08,690 --> 00:18:10,159 reasonable size. 488 00:18:10,160 --> 00:18:12,319 OK, so this 489 00:18:12,320 --> 00:18:14,929 was one of the very first peer 490 00:18:14,930 --> 00:18:17,119 protocols proposed by Tor and others 491 00:18:17,120 --> 00:18:19,189 in nineteen ninety five, almost 492 00:18:19,190 --> 00:18:20,190 twenty years ago now. 493 00:18:21,800 --> 00:18:24,229 But it has some shortcomings 494 00:18:24,230 --> 00:18:26,569 that many of which have been addressed 495 00:18:26,570 --> 00:18:28,579 over the subsequent 20 years. 496 00:18:28,580 --> 00:18:30,349 So let's look at a couple of them. 497 00:18:30,350 --> 00:18:32,869 One of them is that 498 00:18:32,870 --> 00:18:35,029 click the the 499 00:18:35,030 --> 00:18:36,649 shape of this database is rather 500 00:18:36,650 --> 00:18:38,029 simplistic, right? 501 00:18:38,030 --> 00:18:40,339 This database consists of some 502 00:18:40,340 --> 00:18:43,009 number of equally sized records. 503 00:18:43,010 --> 00:18:45,139 Not all databases have equally sized 504 00:18:45,140 --> 00:18:47,149 records. So other work has shown how to 505 00:18:47,150 --> 00:18:49,489 extend this very same protocol 506 00:18:49,490 --> 00:18:52,069 or related protocols to handle variable 507 00:18:52,070 --> 00:18:53,089 size records. 508 00:18:53,090 --> 00:18:54,199 And you might think that's a little 509 00:18:54,200 --> 00:18:56,869 tricky because the answer gets 510 00:18:56,870 --> 00:18:59,329 has to not reveal the size 511 00:18:59,330 --> 00:19:01,399 of the record I was looking for. 512 00:19:01,400 --> 00:19:03,949 So it's a little tricky to do this 513 00:19:03,950 --> 00:19:06,109 securely, but that's 514 00:19:06,110 --> 00:19:07,609 been done in previous work. 515 00:19:07,610 --> 00:19:09,949 Other previous work has 516 00:19:09,950 --> 00:19:12,049 looked at the query 517 00:19:12,050 --> 00:19:14,239 write. The query in this protocol is I 518 00:19:14,240 --> 00:19:16,399 want to record three. 519 00:19:16,400 --> 00:19:18,499 Right. Typically a client of a 520 00:19:18,500 --> 00:19:20,509 database does not know which physical 521 00:19:20,510 --> 00:19:22,669 record number they want to look 522 00:19:22,670 --> 00:19:25,159 up. They know some other information. 523 00:19:25,160 --> 00:19:27,439 They have some more expressive 524 00:19:27,440 --> 00:19:29,779 query, for example, keywords 525 00:19:29,780 --> 00:19:31,999 or even ask you well, in previous work 526 00:19:32,000 --> 00:19:34,669 has shown how to put that into picture 527 00:19:34,670 --> 00:19:37,159 so that you can do Enescu query 528 00:19:37,160 --> 00:19:39,649 on a server without telling the server 529 00:19:39,650 --> 00:19:41,030 what your query is. 530 00:19:42,060 --> 00:19:43,399 That's pretty cool. 531 00:19:43,400 --> 00:19:45,259 That's previous work that already exists, 532 00:19:45,260 --> 00:19:46,489 we have code and everything. 533 00:19:47,980 --> 00:19:48,980 So. 534 00:19:51,000 --> 00:19:52,559 These are previous work and one other 535 00:19:52,560 --> 00:19:55,109 thing, one other shortcoming of. 536 00:19:57,360 --> 00:19:59,459 Of this simplistic scheme 537 00:19:59,460 --> 00:20:01,529 is that it's not robust and what we 538 00:20:01,530 --> 00:20:03,809 mean by robust, so if you look 539 00:20:03,810 --> 00:20:05,279 here, what happens? 540 00:20:05,280 --> 00:20:06,280 Click. 541 00:20:09,760 --> 00:20:10,760 OK, over here. 542 00:20:12,130 --> 00:20:13,359 OK, next slide. 543 00:20:16,030 --> 00:20:17,489 OK, there we go. 544 00:20:17,490 --> 00:20:19,390 Lasers working, OK, so. 545 00:20:21,970 --> 00:20:23,619 What do we mean by robust? 546 00:20:23,620 --> 00:20:25,869 Well, imagine one of the servers is 547 00:20:25,870 --> 00:20:28,119 down and doesn't give you a response 548 00:20:28,120 --> 00:20:30,189 or worse, one of the servers is malicious 549 00:20:30,190 --> 00:20:32,289 and gives you the wrong answer. 550 00:20:32,290 --> 00:20:34,779 When Alice adds up the answers, 551 00:20:34,780 --> 00:20:36,580 she'll just get some garbage. 552 00:20:38,020 --> 00:20:41,139 And worse, she can't tell which server 553 00:20:41,140 --> 00:20:44,319 gave her the wrong answer. 554 00:20:44,320 --> 00:20:46,659 OK, so a robust protocol 555 00:20:46,660 --> 00:20:49,359 would allow Alice to retrieve 556 00:20:49,360 --> 00:20:51,369 her correct block even if some of the 557 00:20:51,370 --> 00:20:53,589 servers were down or malicious. 558 00:20:58,390 --> 00:21:00,279 And at the same time, she'll be able to 559 00:21:00,280 --> 00:21:02,439 identify which servers were malicious 560 00:21:02,440 --> 00:21:03,969 and of course, that's a disincentive for 561 00:21:03,970 --> 00:21:05,469 the server to be malicious in the first 562 00:21:05,470 --> 00:21:07,899 place. So let's look at briefly 563 00:21:07,900 --> 00:21:09,789 how these robust protocols work. 564 00:21:11,140 --> 00:21:13,029 So it uses something called Shamir's 565 00:21:13,030 --> 00:21:15,249 secret sharing, which is pretty 566 00:21:15,250 --> 00:21:17,019 fun and cool. So I'm going to talk about 567 00:21:17,020 --> 00:21:17,979 that for a little bit. 568 00:21:17,980 --> 00:21:20,379 Who's heard of Shamir's secret sharing? 569 00:21:20,380 --> 00:21:21,939 Not as many people as I've heard of 570 00:21:21,940 --> 00:21:23,829 matrices. Who's heard of polynomials? 571 00:21:25,460 --> 00:21:26,119 OK, good. 572 00:21:26,120 --> 00:21:28,219 We're going to use polynomials, 573 00:21:28,220 --> 00:21:30,169 OK, so Shamir's secretory. 574 00:21:30,170 --> 00:21:32,119 So what is this? You have some secret in 575 00:21:32,120 --> 00:21:34,609 the case of the PR scheme, the secret is 576 00:21:34,610 --> 00:21:36,589 this Victor II. 577 00:21:36,590 --> 00:21:38,629 Right. Which represents which block 578 00:21:38,630 --> 00:21:39,559 number you're interested in. 579 00:21:39,560 --> 00:21:41,839 So you have some secret and 580 00:21:41,840 --> 00:21:43,969 you want to share pieces of 581 00:21:43,970 --> 00:21:46,069 the secret among a number of 582 00:21:46,070 --> 00:21:48,139 parties such that 583 00:21:48,140 --> 00:21:50,299 there some threshold T 584 00:21:50,300 --> 00:21:52,579 that if it most T of those parties 585 00:21:52,580 --> 00:21:54,949 come together, they have no idea 586 00:21:54,950 --> 00:21:55,849 what the secret is. 587 00:21:55,850 --> 00:21:57,649 It's not that they have some few bits of 588 00:21:57,650 --> 00:22:00,079 the secret. They have none of the secret, 589 00:22:00,080 --> 00:22:02,099 none at all. 590 00:22:02,100 --> 00:22:04,339 OK, but if more than t come together 591 00:22:04,340 --> 00:22:06,199 they get the secret. 592 00:22:06,200 --> 00:22:07,999 OK, so here's how that's going to work. 593 00:22:08,000 --> 00:22:09,109 You have your secret 594 00:22:10,130 --> 00:22:12,319 and you have your privacy threshold 595 00:22:12,320 --> 00:22:13,849 level that you care about. 596 00:22:13,850 --> 00:22:16,339 We'll call T and what you do 597 00:22:16,340 --> 00:22:18,709 is you make 598 00:22:18,710 --> 00:22:21,409 you draw your x y axes 599 00:22:21,410 --> 00:22:23,659 and you draw a green dot at 600 00:22:23,660 --> 00:22:25,160 zero comma your secret. 601 00:22:26,660 --> 00:22:28,729 OK, and then you pick a random 602 00:22:28,730 --> 00:22:31,369 polynomial off of the green tea 603 00:22:31,370 --> 00:22:32,990 that goes through that dot. 604 00:22:35,060 --> 00:22:37,099 OK, so you're picking a random polynomial 605 00:22:37,100 --> 00:22:38,239 of degree T. 606 00:22:38,240 --> 00:22:40,549 Who's y intercept is 607 00:22:40,550 --> 00:22:42,619 your secret, OK, that's what 608 00:22:42,620 --> 00:22:43,549 you're doing. 609 00:22:43,550 --> 00:22:45,829 So when T is one, this is a random line 610 00:22:45,830 --> 00:22:46,729 that goes through the door. 611 00:22:46,730 --> 00:22:48,859 20 is two. It's a random 612 00:22:48,860 --> 00:22:50,659 parabola that goes through the door and 613 00:22:50,660 --> 00:22:52,159 is three. It's a random Kubic that goes 614 00:22:52,160 --> 00:22:53,160 through the dot. 615 00:22:53,800 --> 00:22:55,999 OK, so what 616 00:22:56,000 --> 00:22:58,399 do you do next then you just hand 617 00:22:58,400 --> 00:23:00,649 out other points on this polynomial. 618 00:23:00,650 --> 00:23:02,719 So these blue points here, you hand 619 00:23:02,720 --> 00:23:04,339 them out to the parties, 620 00:23:05,390 --> 00:23:08,059 then what happens if someone said, oh, 621 00:23:08,060 --> 00:23:09,349 someone just got it. 622 00:23:10,970 --> 00:23:12,679 OK, so what's about to happen? 623 00:23:12,680 --> 00:23:15,079 So let's just look at the simple linear 624 00:23:15,080 --> 00:23:17,119 case as an example. 625 00:23:17,120 --> 00:23:19,939 If you only have one dot, 626 00:23:19,940 --> 00:23:22,549 you have no idea what the y intercept 627 00:23:22,550 --> 00:23:24,739 of the line going through this dot is, 628 00:23:24,740 --> 00:23:26,599 because it could literally be anything. 629 00:23:30,620 --> 00:23:32,479 And similarly, if you have two dots, you 630 00:23:32,480 --> 00:23:34,429 have no idea what the y intercept of the 631 00:23:34,430 --> 00:23:36,199 problem is because it could literally be 632 00:23:36,200 --> 00:23:37,249 anything and so on. 633 00:23:39,120 --> 00:23:41,189 But if you have more than T let's say you 634 00:23:41,190 --> 00:23:43,319 have two dots, of course, two points 635 00:23:43,320 --> 00:23:45,119 make a line. So you draw the line and 636 00:23:45,120 --> 00:23:47,009 there's your Y intercept and you can just 637 00:23:47,010 --> 00:23:49,409 read off the secret right from there. 638 00:23:49,410 --> 00:23:51,809 So this is Shamir's secret sharing 639 00:23:51,810 --> 00:23:54,119 and this is what we use 640 00:23:54,120 --> 00:23:56,429 instead of this splitting the eEye 641 00:23:56,430 --> 00:23:57,419 into just V.R. 642 00:23:57,420 --> 00:23:59,699 V1 plus V two plus V three and so 643 00:23:59,700 --> 00:24:02,039 on. We split it in this slightly 644 00:24:02,040 --> 00:24:04,199 more complex way. 645 00:24:04,200 --> 00:24:06,419 But this has the nice feature that you 646 00:24:06,420 --> 00:24:08,609 don't need all the servers 647 00:24:08,610 --> 00:24:10,619 to come back and give you the answers. 648 00:24:10,620 --> 00:24:12,409 You only need T plus one of them 649 00:24:13,500 --> 00:24:15,239 and then one of some of the servers give 650 00:24:15,240 --> 00:24:16,829 you wrong answers. 651 00:24:16,830 --> 00:24:18,479 Well, that's where we use something 652 00:24:18,480 --> 00:24:20,519 called error correcting codes. 653 00:24:20,520 --> 00:24:22,109 So with error correcting codes, we can 654 00:24:22,110 --> 00:24:23,280 tell, for example, 655 00:24:24,600 --> 00:24:27,119 which when we have some 656 00:24:27,120 --> 00:24:29,249 click, some wrong 657 00:24:29,250 --> 00:24:31,469 points, which points 658 00:24:31,470 --> 00:24:34,589 are wrong. So here's a little quiz. 659 00:24:34,590 --> 00:24:36,749 T is three. So we're looking for a Kubic 660 00:24:36,750 --> 00:24:38,849 that passes through all but one 661 00:24:38,850 --> 00:24:40,199 of these points. 662 00:24:40,200 --> 00:24:41,879 So there are six points up there. 663 00:24:41,880 --> 00:24:43,859 One of them is wrong. 664 00:24:43,860 --> 00:24:45,389 Which one is wrong? 665 00:24:45,390 --> 00:24:47,549 Who says the one at this 666 00:24:47,550 --> 00:24:49,709 end is wrong? 667 00:24:49,710 --> 00:24:52,139 Who says the second one third 668 00:24:52,140 --> 00:24:54,929 one fourth one 669 00:24:54,930 --> 00:24:58,069 fifth one sixth one. 670 00:24:58,070 --> 00:25:00,179 OK, the answer is in fact, 671 00:25:00,180 --> 00:25:01,499 the first one. 672 00:25:01,500 --> 00:25:02,519 That's the Kubic. 673 00:25:04,860 --> 00:25:07,109 And this kind of error correction 674 00:25:07,110 --> 00:25:09,599 is actually used quite commonly. 675 00:25:09,600 --> 00:25:11,669 It's used in CDs and 676 00:25:11,670 --> 00:25:12,599 DVDs. 677 00:25:12,600 --> 00:25:14,369 It's used in QR codes. 678 00:25:14,370 --> 00:25:15,419 Right. You're probably familiar with 679 00:25:15,420 --> 00:25:17,429 this. Quick, what is this QR code resolve 680 00:25:17,430 --> 00:25:18,430 to know? 681 00:25:20,130 --> 00:25:22,529 But the reason that it's using QR 682 00:25:22,530 --> 00:25:24,689 codes is so you can do this and just 683 00:25:24,690 --> 00:25:26,909 blot some stuff obscuring 684 00:25:26,910 --> 00:25:29,009 part of the QR code and this code will 685 00:25:29,010 --> 00:25:30,479 still scan to the same thing. 686 00:25:30,480 --> 00:25:32,729 The other code scan to which is in fact 687 00:25:32,730 --> 00:25:33,779 the homepage. 688 00:25:36,040 --> 00:25:38,259 OK, so these error correction 689 00:25:38,260 --> 00:25:39,789 codes are 690 00:25:41,680 --> 00:25:43,989 used all over in in ordinary life 691 00:25:43,990 --> 00:25:45,549 because you want to make sure usually 692 00:25:45,550 --> 00:25:47,949 that scratches on your DVD or Tear's 693 00:25:47,950 --> 00:25:50,109 in your QR code, don't mess things up. 694 00:25:50,110 --> 00:25:52,569 And they are also used in PR 695 00:25:52,570 --> 00:25:55,059 to handle malicious servers. 696 00:25:55,060 --> 00:25:57,249 OK, so all this is implemented 697 00:25:57,250 --> 00:25:59,379 in our Pursey plus plus open 698 00:25:59,380 --> 00:26:00,879 source library. 699 00:26:00,880 --> 00:26:03,939 That's a pun on Pyaar in C++, 700 00:26:03,940 --> 00:26:06,009 pure C++ now. 701 00:26:06,010 --> 00:26:07,010 OK, fine. 702 00:26:10,180 --> 00:26:11,739 For those of you who I get, there's a 703 00:26:11,740 --> 00:26:13,359 gift. For those of you who don't like get 704 00:26:13,360 --> 00:26:14,409 there is a sourceforge. 705 00:26:14,410 --> 00:26:15,489 For those of you who don't like 706 00:26:15,490 --> 00:26:17,559 SourceForge, find someone who you 707 00:26:17,560 --> 00:26:18,560 know who likes get. 708 00:26:21,050 --> 00:26:22,969 OK, so now I'm going to turn it over to 709 00:26:22,970 --> 00:26:25,099 George, who's going to talk about 710 00:26:25,100 --> 00:26:27,559 using Pyaar 711 00:26:27,560 --> 00:26:29,899 to make privacy, preserving protocols. 712 00:26:29,900 --> 00:26:30,900 Thank you. 713 00:26:37,320 --> 00:26:38,609 Good afternoon, everybody. 714 00:26:38,610 --> 00:26:40,649 I hope this works, so the cool thing 715 00:26:40,650 --> 00:26:42,419 about crypto is that it's about math and 716 00:26:42,420 --> 00:26:43,409 mass is cool. 717 00:26:43,410 --> 00:26:45,179 But what is even better is that we can 718 00:26:45,180 --> 00:26:46,439 use crypto in order to protect our 719 00:26:46,440 --> 00:26:48,539 privacy against adversaries that we would 720 00:26:48,540 --> 00:26:50,519 never have imagined without crypto to be 721 00:26:50,520 --> 00:26:52,679 able to protect ourselves against. 722 00:26:52,680 --> 00:26:54,629 So the example that I will use to 723 00:26:54,630 --> 00:26:56,969 illustrate why Peer can be useful, that 724 00:26:56,970 --> 00:26:59,339 it relates to achieving 725 00:26:59,340 --> 00:27:02,039 privacy in kind of social interactions 726 00:27:02,040 --> 00:27:03,299 online. 727 00:27:03,300 --> 00:27:05,459 So you may have noticed that in 728 00:27:05,460 --> 00:27:07,499 the last 15 years we started using 729 00:27:07,500 --> 00:27:09,219 computers to talk to each other. 730 00:27:09,220 --> 00:27:11,729 OK, and you have things like Twitter, 731 00:27:11,730 --> 00:27:14,069 you have things like Facebook, 732 00:27:14,070 --> 00:27:15,180 no reaction, OK? 733 00:27:16,410 --> 00:27:18,509 And you have different chat protocols. 734 00:27:18,510 --> 00:27:20,609 Knew this thing works sometimes and 735 00:27:20,610 --> 00:27:21,749 not other times. 736 00:27:21,750 --> 00:27:22,799 All right. Tricky. 737 00:27:22,800 --> 00:27:25,139 OK, so all of these have something 738 00:27:25,140 --> 00:27:26,219 in common. 739 00:27:26,220 --> 00:27:28,649 Namely, they have a sense 740 00:27:28,650 --> 00:27:30,689 that some users are friends with other 741 00:27:30,690 --> 00:27:32,849 users. Again, this is kind of crucial to 742 00:27:32,850 --> 00:27:35,279 all of them, even even Twitter, 743 00:27:35,280 --> 00:27:37,139 which doesn't, you know, handle secrets. 744 00:27:37,140 --> 00:27:39,329 Usually all that much has a sense 745 00:27:39,330 --> 00:27:40,649 that you have people following you and 746 00:27:40,650 --> 00:27:42,269 you follow people and that kind of rules 747 00:27:42,270 --> 00:27:43,409 information around and it's kind of 748 00:27:43,410 --> 00:27:44,759 important. 749 00:27:44,760 --> 00:27:47,099 OK, now one further 750 00:27:47,100 --> 00:27:48,449 thing that is important, particularly 751 00:27:48,450 --> 00:27:49,619 when it comes to chat and we're 752 00:27:49,620 --> 00:27:51,299 particular kind of chat because we would 753 00:27:51,300 --> 00:27:53,249 like to eventually protect the privacy of 754 00:27:53,250 --> 00:27:55,919 people. Chatting is presence. 755 00:27:55,920 --> 00:27:57,809 Now, what is presence? 756 00:27:57,810 --> 00:27:59,639 Presence is just a little green dot that 757 00:27:59,640 --> 00:28:01,589 you see next to someone's name when 758 00:28:01,590 --> 00:28:03,329 they're online. This is really presents. 759 00:28:03,330 --> 00:28:05,459 I mean, it's kind of a simple thing. 760 00:28:05,460 --> 00:28:07,739 However, we kind of grew used to it 761 00:28:07,740 --> 00:28:10,169 in the sense that in the old days 762 00:28:10,170 --> 00:28:12,089 you would just call a number and hope 763 00:28:12,090 --> 00:28:13,379 that someone picks it up, particularly 764 00:28:13,380 --> 00:28:14,339 when it was a home number. 765 00:28:14,340 --> 00:28:16,049 And most most of the time no one would 766 00:28:16,050 --> 00:28:17,969 pick it up. And it was very frustrating. 767 00:28:17,970 --> 00:28:19,499 Now, what was the last time you had this 768 00:28:19,500 --> 00:28:20,399 frustration? Right. 769 00:28:20,400 --> 00:28:22,559 I mean, 10 years ago, something 770 00:28:22,560 --> 00:28:24,029 nowadays you can see when people are 771 00:28:24,030 --> 00:28:26,369 online, you can just call them. 772 00:28:26,370 --> 00:28:28,229 And you know that more often than not, 773 00:28:28,230 --> 00:28:29,849 they will answer unless they actually 774 00:28:29,850 --> 00:28:31,649 don't want to talk to you, at which point 775 00:28:31,650 --> 00:28:33,119 it's a bit awkward. 776 00:28:33,120 --> 00:28:35,219 And in order to 777 00:28:35,220 --> 00:28:37,319 avoid such awkwardness, in 778 00:28:37,320 --> 00:28:39,599 fact, we have we have 779 00:28:39,600 --> 00:28:41,699 improved our presence protocols with 780 00:28:41,700 --> 00:28:43,239 some additional information. 781 00:28:43,240 --> 00:28:44,939 You don't just see green or nothing. 782 00:28:44,940 --> 00:28:46,199 You actually have this kind of 783 00:28:46,200 --> 00:28:48,179 intermediate states of orange, which is 784 00:28:48,180 --> 00:28:50,279 kind of I'm going away or, you 785 00:28:50,280 --> 00:28:52,079 know, red. I'm quite busy. 786 00:28:52,080 --> 00:28:53,729 So we don't just want to know if people 787 00:28:53,730 --> 00:28:55,499 are online or offline, but we also want 788 00:28:55,500 --> 00:28:58,259 to associate some further information 789 00:28:58,260 --> 00:28:59,219 with what they're doing. 790 00:28:59,220 --> 00:29:01,349 You know, what kind of status they have 791 00:29:01,350 --> 00:29:03,059 some little message that says, I'm away, 792 00:29:03,060 --> 00:29:04,589 I'll be back at 5:00 or something like 793 00:29:04,590 --> 00:29:06,719 this. So our presence protocols will 794 00:29:06,720 --> 00:29:09,149 try to replicate this facility, 795 00:29:09,150 --> 00:29:10,679 both of finding out if people are online 796 00:29:10,680 --> 00:29:12,929 and also convey some little 797 00:29:12,930 --> 00:29:14,699 amount of associated information that 798 00:29:14,700 --> 00:29:17,459 will help any further communications. 799 00:29:17,460 --> 00:29:19,829 Now, how is presence 800 00:29:19,830 --> 00:29:22,109 achieved today in 801 00:29:22,110 --> 00:29:24,059 most services, including very big 802 00:29:24,060 --> 00:29:26,219 commercial services or 803 00:29:26,220 --> 00:29:28,469 smaller services run by good people 804 00:29:28,470 --> 00:29:30,149 like, you know, the job of services of 805 00:29:30,150 --> 00:29:32,939 the CCC that many of us are using? 806 00:29:32,940 --> 00:29:35,219 The the way this is done 807 00:29:35,220 --> 00:29:37,289 is actually quite shared in 808 00:29:37,290 --> 00:29:38,309 some sense. 809 00:29:38,310 --> 00:29:40,109 What happens is that you have usually 810 00:29:40,110 --> 00:29:42,089 some kind of server and 811 00:29:43,410 --> 00:29:44,849 there is some kind of a notion of a 812 00:29:44,850 --> 00:29:47,669 social network of users having friends 813 00:29:47,670 --> 00:29:49,919 and contacts, et cetera, et cetera, 814 00:29:49,920 --> 00:29:51,869 they'd like to hear from or they would 815 00:29:51,870 --> 00:29:53,549 like information about it from what they 816 00:29:53,550 --> 00:29:55,379 would like to find out if they're online. 817 00:29:55,380 --> 00:29:57,449 And the service has to 818 00:29:57,450 --> 00:30:00,359 simply know the full social graph, 819 00:30:00,360 --> 00:30:01,709 OK, that's how it's done. 820 00:30:01,710 --> 00:30:04,139 And then what happens is that Bob 821 00:30:04,140 --> 00:30:05,140 comes online, 822 00:30:07,260 --> 00:30:09,719 but then Alice comes online and 823 00:30:09,720 --> 00:30:12,119 Alice authenticates, says, 824 00:30:12,120 --> 00:30:13,049 Hi, I'm Alice. 825 00:30:13,050 --> 00:30:14,699 The service knows that Bob is a friend of 826 00:30:14,700 --> 00:30:15,359 Alice. 827 00:30:15,360 --> 00:30:17,519 And then the service 828 00:30:17,520 --> 00:30:19,859 sends back to Alice, who's online, 829 00:30:19,860 --> 00:30:21,929 who's not online, what their status is. 830 00:30:21,930 --> 00:30:23,670 OK, now. 831 00:30:26,050 --> 00:30:28,389 Maybe I should I'm clicking 832 00:30:28,390 --> 00:30:30,639 furiously here, I will actually 833 00:30:30,640 --> 00:30:32,289 move towards there so that I stop doing 834 00:30:32,290 --> 00:30:32,979 that. 835 00:30:32,980 --> 00:30:34,480 OK, now. 836 00:30:35,970 --> 00:30:38,099 And then some present information is 837 00:30:38,100 --> 00:30:40,409 routed back, so 838 00:30:40,410 --> 00:30:42,539 there is a fundamental privacy 839 00:30:42,540 --> 00:30:44,969 problem with relying on services 840 00:30:44,970 --> 00:30:47,039 that have these social graph as a 841 00:30:47,040 --> 00:30:48,779 necessary information to provide 842 00:30:48,780 --> 00:30:49,709 presence. 843 00:30:49,710 --> 00:30:51,839 OK, now what is 844 00:30:51,840 --> 00:30:53,819 the problem associated with that? 845 00:30:53,820 --> 00:30:56,009 The problem is that who your friends 846 00:30:56,010 --> 00:30:58,379 are basically 847 00:30:58,380 --> 00:31:00,359 leaks a lot of information about who you 848 00:31:00,360 --> 00:31:02,729 are. OK, if all my friends 849 00:31:02,730 --> 00:31:05,129 are hackers, the probabilities are 850 00:31:05,130 --> 00:31:06,059 that I'm a hacker. 851 00:31:06,060 --> 00:31:07,499 If all my friends are journalists, the 852 00:31:07,500 --> 00:31:09,629 probabilities are that I'm a journalist. 853 00:31:09,630 --> 00:31:11,849 If all my friends are from Sudan, 854 00:31:11,850 --> 00:31:13,499 I have some association from Sudan. 855 00:31:13,500 --> 00:31:15,929 So suddenly who, you know, actually 856 00:31:15,930 --> 00:31:18,419 has gives away a lot of information about 857 00:31:18,420 --> 00:31:20,849 you in particular, 858 00:31:20,850 --> 00:31:22,979 who you contact or who you 859 00:31:22,980 --> 00:31:25,139 know, who you include as 860 00:31:25,140 --> 00:31:26,579 a friend, as a new friend, et cetera. 861 00:31:26,580 --> 00:31:28,139 If suddenly I start including a lot of 862 00:31:28,140 --> 00:31:30,329 doctors or a lot of lawyers 863 00:31:30,330 --> 00:31:31,679 in my circle of friends, well, that 864 00:31:31,680 --> 00:31:34,349 actually leaks information about me. 865 00:31:34,350 --> 00:31:36,509 OK, and you may say, well, you 866 00:31:36,510 --> 00:31:38,669 know, what's the big deal about 867 00:31:38,670 --> 00:31:40,559 this? This is not a big deal. 868 00:31:40,560 --> 00:31:42,779 However, what we have learned from 869 00:31:42,780 --> 00:31:45,449 the Snowden leaks is that 870 00:31:45,450 --> 00:31:47,369 if we have services that hold this 871 00:31:47,370 --> 00:31:49,589 information, what may happen, 872 00:31:49,590 --> 00:31:52,019 such as, for example, a friendly ISP 873 00:31:52,020 --> 00:31:54,389 like Lavabit, what may happen is 874 00:31:54,390 --> 00:31:56,819 that the government who wants to discover 875 00:31:56,820 --> 00:31:58,439 this information about you will go to the 876 00:31:58,440 --> 00:32:00,449 service provider who never intended to 877 00:32:00,450 --> 00:32:01,949 betray you and will say thank you very 878 00:32:01,950 --> 00:32:02,249 much. 879 00:32:02,250 --> 00:32:04,229 Can we have all this database of who is 880 00:32:04,230 --> 00:32:05,189 friends with whom? 881 00:32:05,190 --> 00:32:07,169 OK, and we know that there are specific 882 00:32:07,170 --> 00:32:09,569 programs that do target those databases 883 00:32:09,570 --> 00:32:11,519 for collection, either by coercing 884 00:32:11,520 --> 00:32:14,189 providers or by 885 00:32:14,190 --> 00:32:16,259 actually just stealing the data off 886 00:32:16,260 --> 00:32:19,409 the wire or from their databases. 887 00:32:19,410 --> 00:32:21,509 Now, what's the big deal 888 00:32:21,510 --> 00:32:23,669 with that? Well, we actually had a very 889 00:32:23,670 --> 00:32:26,219 interesting confession 890 00:32:26,220 --> 00:32:28,559 last year by General Michael 891 00:32:28,560 --> 00:32:28,919 Hayden. 892 00:32:28,920 --> 00:32:31,559 He said we kill people based on metadata. 893 00:32:31,560 --> 00:32:33,929 So you being in the social 894 00:32:33,930 --> 00:32:35,849 graph of particular, other people may, in 895 00:32:35,850 --> 00:32:38,039 fact go as far as putting on a kill list. 896 00:32:38,040 --> 00:32:40,109 And even when that doesn't happen, 897 00:32:40,110 --> 00:32:42,659 it go we might go so far as 898 00:32:42,660 --> 00:32:45,029 putting you on a particular targeted 899 00:32:45,030 --> 00:32:47,099 surveillance list or make you 900 00:32:47,100 --> 00:32:48,989 a target for harassment, et cetera, et 901 00:32:48,990 --> 00:32:50,669 cetera, et cetera. So we would like to 902 00:32:50,670 --> 00:32:51,869 hide this metadata. 903 00:32:51,870 --> 00:32:54,059 We do not want to rely on third party 904 00:32:54,060 --> 00:32:56,159 services holding that graph 905 00:32:56,160 --> 00:32:58,889 in order to provide presence or 906 00:32:58,890 --> 00:33:00,659 any other associated data that comes with 907 00:33:00,660 --> 00:33:01,469 presence. 908 00:33:01,470 --> 00:33:02,470 OK. 909 00:33:09,550 --> 00:33:11,679 Now, what do we expect from 910 00:33:11,680 --> 00:33:13,339 a privacy friendly present system? 911 00:33:14,500 --> 00:33:15,849 First of all, there are some functional 912 00:33:15,850 --> 00:33:17,799 features that we would not want to lose. 913 00:33:17,800 --> 00:33:19,899 We want users to be able to 914 00:33:19,900 --> 00:33:21,969 somehow associate friends with 915 00:33:21,970 --> 00:33:24,129 each other and register that they're 916 00:33:24,130 --> 00:33:26,919 online and extract people status 917 00:33:26,920 --> 00:33:29,079 and then suspend friends if they 918 00:33:29,080 --> 00:33:30,879 do not wish to share any more information 919 00:33:30,880 --> 00:33:32,139 with them. 920 00:33:32,140 --> 00:33:34,269 Now, we would like our privacy 921 00:33:34,270 --> 00:33:35,979 friendly system to be resistant against 922 00:33:35,980 --> 00:33:38,109 some pretty serious adversaries out there 923 00:33:38,110 --> 00:33:39,639 because we know they exist and they're 924 00:33:39,640 --> 00:33:41,439 interested in this information. 925 00:33:41,440 --> 00:33:43,229 We assume our adversaries are. 926 00:33:46,520 --> 00:33:49,279 OK, we assume our adversaries, 927 00:33:49,280 --> 00:33:50,809 for example, can observe most 928 00:33:50,810 --> 00:33:52,219 communications on the network, all 929 00:33:52,220 --> 00:33:54,319 communications, we assume our adversary, 930 00:33:54,320 --> 00:33:56,539 sometimes our our friends, we would like 931 00:33:56,540 --> 00:33:58,609 to hide information even 932 00:33:58,610 --> 00:34:00,829 from other uses that we have tagged 933 00:34:00,830 --> 00:34:03,019 as friends. However, we will assume 934 00:34:03,020 --> 00:34:05,119 that we have some aces up our sleeve. 935 00:34:05,120 --> 00:34:07,909 In particular, the computers we're using 936 00:34:07,910 --> 00:34:09,979 are secure. And if you know that is 937 00:34:09,980 --> 00:34:12,049 not the case for your computer, I'll go 938 00:34:12,050 --> 00:34:14,269 and talk to the people who maintain tales 939 00:34:14,270 --> 00:34:15,678 or any such distribution. 940 00:34:15,679 --> 00:34:17,809 They may be able to help you and we will 941 00:34:17,810 --> 00:34:20,269 assume that both are cryptography, 942 00:34:20,270 --> 00:34:22,759 is secure, cannot be broken 943 00:34:22,760 --> 00:34:25,309 by the adversary, and also that 944 00:34:25,310 --> 00:34:27,049 we have some infrastructure servers that 945 00:34:27,050 --> 00:34:29,149 will not all collude with each other to 946 00:34:29,150 --> 00:34:30,259 violate our privacy. 947 00:34:30,260 --> 00:34:32,029 This is very much in line with the 948 00:34:32,030 --> 00:34:33,709 assumption that Ian mentioned earlier 949 00:34:33,710 --> 00:34:34,789 today. 950 00:34:34,790 --> 00:34:36,979 And with those tools, what 951 00:34:36,980 --> 00:34:38,959 we will try to do is, first of all, 952 00:34:38,960 --> 00:34:40,399 protect the privacy of our social 953 00:34:40,400 --> 00:34:42,349 network. We do not want any third party 954 00:34:42,350 --> 00:34:44,599 to be able to see the full social 955 00:34:44,600 --> 00:34:46,459 network. We will try to protect the 956 00:34:46,460 --> 00:34:48,709 privacy and integrity of the associated 957 00:34:48,710 --> 00:34:50,988 status information and also provide 958 00:34:50,989 --> 00:34:53,479 some additional properties, most notably 959 00:34:53,480 --> 00:34:54,709 for the purpose of this talk and 960 00:34:54,710 --> 00:34:56,928 likability, namely the inability 961 00:34:56,929 --> 00:34:59,179 from one time period to learn information 962 00:34:59,180 --> 00:35:01,429 that will be used in another time period 963 00:35:01,430 --> 00:35:03,499 to violate any privacy properties of the 964 00:35:03,500 --> 00:35:05,659 network, as well as forward and backward 965 00:35:05,660 --> 00:35:07,849 secrecy, et cetera, that are 966 00:35:07,850 --> 00:35:10,069 very interesting to resist, very 967 00:35:10,070 --> 00:35:11,029 powerful adversaries. 968 00:35:11,030 --> 00:35:13,159 Now, some of you may already 969 00:35:13,160 --> 00:35:15,259 be thinking, ha, I can 970 00:35:15,260 --> 00:35:17,269 think of a trivial way of doing this 971 00:35:17,270 --> 00:35:17,569 right. 972 00:35:17,570 --> 00:35:19,789 And this is not like using a lot 973 00:35:19,790 --> 00:35:22,429 of very advanced technologies. 974 00:35:22,430 --> 00:35:24,979 What we can do is we simply have Alice 975 00:35:24,980 --> 00:35:26,839 and she basically contacts through an 976 00:35:26,840 --> 00:35:28,969 anonymity channel like Tor, for 977 00:35:28,970 --> 00:35:31,159 example, to a chat server that 978 00:35:31,160 --> 00:35:33,229 is either a hidden service or on 979 00:35:33,230 --> 00:35:34,849 the other side of the anonymous channel 980 00:35:34,850 --> 00:35:36,859 and registers using a pseudonym. 981 00:35:36,860 --> 00:35:38,959 And then we will have Bob down the line 982 00:35:38,960 --> 00:35:41,149 that also registered to the same server 983 00:35:41,150 --> 00:35:43,249 and also says, hey, 984 00:35:43,250 --> 00:35:45,409 by the way, is Alice or the pseudonym 985 00:35:45,410 --> 00:35:47,449 of Alice online, OK? 986 00:35:47,450 --> 00:35:49,579 And that, you may think 987 00:35:49,580 --> 00:35:51,169 solves the problem. 988 00:35:51,170 --> 00:35:52,819 However, this is not quite the case 989 00:35:52,820 --> 00:35:54,469 because what happens on the servers is 990 00:35:54,470 --> 00:35:56,119 that the pseudonym of Alice in the 991 00:35:56,120 --> 00:35:58,789 pseudonym of Bob are somehow associated 992 00:35:58,790 --> 00:36:00,769 with each other and so is the pseudonym 993 00:36:00,770 --> 00:36:02,629 of Alice. Will all the pseudonyms of her 994 00:36:02,630 --> 00:36:04,159 other friends and the pseudonym of Bob 995 00:36:04,160 --> 00:36:06,229 with none of his other 996 00:36:06,230 --> 00:36:08,719 friends. And what happens in effect 997 00:36:08,720 --> 00:36:11,769 is that a kind of isomorphic 998 00:36:11,770 --> 00:36:13,939 a to the real social graph starts being 999 00:36:13,940 --> 00:36:15,379 constructed in the service? 1000 00:36:15,380 --> 00:36:17,059 OK, we have pseudonyms being friends with 1001 00:36:17,060 --> 00:36:18,889 pseudonyms. However, the shape of that 1002 00:36:18,890 --> 00:36:21,139 graph, the links are one to one 1003 00:36:21,140 --> 00:36:23,089 mapping with the real graph. 1004 00:36:23,090 --> 00:36:25,009 And therefore, despite the fact that 1005 00:36:25,010 --> 00:36:27,139 maybe these are just pseudonyms instead 1006 00:36:27,140 --> 00:36:29,059 of Alice, we have a instead of Bob, we 1007 00:36:29,060 --> 00:36:30,229 have B. 1008 00:36:30,230 --> 00:36:32,029 If the adversary has any side 1009 00:36:32,030 --> 00:36:34,939 information, such as, for example, 1010 00:36:34,940 --> 00:36:37,309 you know, contributions of people 1011 00:36:37,310 --> 00:36:39,379 and their friends on, you 1012 00:36:39,380 --> 00:36:41,989 know, kind of online 1013 00:36:41,990 --> 00:36:44,449 video review site or anything like that, 1014 00:36:44,450 --> 00:36:46,519 they may be able to use that information 1015 00:36:46,520 --> 00:36:48,349 to reconstruct the graph and the 1016 00:36:48,350 --> 00:36:49,159 anonymize it. 1017 00:36:49,160 --> 00:36:50,839 And we have seen particular attacks 1018 00:36:50,840 --> 00:36:52,549 against Netflix that do that. 1019 00:36:52,550 --> 00:36:54,589 Therefore, it is not actually a safe way 1020 00:36:54,590 --> 00:36:56,539 to just do this, OK, because the 1021 00:36:56,540 --> 00:36:58,369 adversary would be able to just go to the 1022 00:36:58,370 --> 00:37:00,499 server and or operate 1023 00:37:00,500 --> 00:37:02,899 even such a server and recover 1024 00:37:02,900 --> 00:37:04,999 a graph that is pretty damn 1025 00:37:05,000 --> 00:37:07,459 close to the graph we are trying to hide. 1026 00:37:07,460 --> 00:37:08,479 We don't want to do that. 1027 00:37:08,480 --> 00:37:10,789 We want to leak no information, 1028 00:37:10,790 --> 00:37:12,559 not just hide a little bit of 1029 00:37:12,560 --> 00:37:14,059 information. 1030 00:37:14,060 --> 00:37:16,339 OK, so here is a high level 1031 00:37:16,340 --> 00:37:18,469 overview of how do we actually 1032 00:37:18,470 --> 00:37:20,569 achieve this? And you 1033 00:37:20,570 --> 00:37:23,029 will recognize a few of the ideas that 1034 00:37:23,030 --> 00:37:24,259 you mentioned. 1035 00:37:24,260 --> 00:37:26,389 So the basic problem 1036 00:37:26,390 --> 00:37:28,009 is that we have Alisson, we have Bob and 1037 00:37:28,010 --> 00:37:29,359 their friends and they would like to use 1038 00:37:29,360 --> 00:37:30,409 a service. 1039 00:37:30,410 --> 00:37:32,299 And this service runs our specific 1040 00:37:32,300 --> 00:37:34,010 protocol called DP five, 1041 00:37:35,630 --> 00:37:37,969 and that stands for the National Privacy 1042 00:37:37,970 --> 00:37:40,249 Preserving Present Protocol 1043 00:37:40,250 --> 00:37:42,320 and the extra PS for extra privacy. 1044 00:37:44,150 --> 00:37:45,889 So they would like to use a service that 1045 00:37:45,890 --> 00:37:48,019 runs the Deep Five protocol to 1046 00:37:48,020 --> 00:37:50,209 gain some present information. 1047 00:37:50,210 --> 00:37:51,919 However, we would like all the servers 1048 00:37:51,920 --> 00:37:53,299 that run deep inside not to learn 1049 00:37:53,300 --> 00:37:55,069 anything. So let's see how we could 1050 00:37:55,070 --> 00:37:57,439 achieve this, first of all, because 1051 00:37:57,440 --> 00:37:59,509 the servers should not actually 1052 00:37:59,510 --> 00:38:01,369 be able to extract any information about 1053 00:38:01,370 --> 00:38:03,259 what's going on. Clearly, Alice and Bob 1054 00:38:03,260 --> 00:38:05,269 need to share some secret that the 1055 00:38:05,270 --> 00:38:06,859 servers don't know. So we assume that 1056 00:38:06,860 --> 00:38:08,779 Alice and Bob share a key that they can 1057 00:38:08,780 --> 00:38:10,759 either share when they meet each other or 1058 00:38:10,760 --> 00:38:12,049 they can derive using public key 1059 00:38:12,050 --> 00:38:13,050 cryptography. 1060 00:38:13,940 --> 00:38:16,339 Then Bob somehow has to send 1061 00:38:16,340 --> 00:38:18,409 some information about his 1062 00:38:18,410 --> 00:38:20,779 presence and his status to 1063 00:38:20,780 --> 00:38:22,729 the infrastructure to DP five server or 1064 00:38:22,730 --> 00:38:25,279 servers. OK, and then naively, 1065 00:38:25,280 --> 00:38:27,859 you may think, well, you know, 1066 00:38:27,860 --> 00:38:29,899 Alice, we'll just have to go and ask, you 1067 00:38:29,900 --> 00:38:30,709 know, is Bob there? 1068 00:38:30,710 --> 00:38:33,109 Is Charlie there and recover that 1069 00:38:33,110 --> 00:38:34,009 information? 1070 00:38:34,010 --> 00:38:36,139 However, this would be insecure, of 1071 00:38:36,140 --> 00:38:38,509 course, because that would leak to 1072 00:38:38,510 --> 00:38:40,789 the infrastructure that 1073 00:38:40,790 --> 00:38:43,279 Alice and Bob and Charlie are associated 1074 00:38:43,280 --> 00:38:44,099 with each other. 1075 00:38:44,100 --> 00:38:46,809 OK, so wouldn't it be. 1076 00:38:46,810 --> 00:38:49,119 If at this stage we had 1077 00:38:49,120 --> 00:38:51,789 some kind of mechanism for Alice 1078 00:38:51,790 --> 00:38:53,949 to ask the server 1079 00:38:53,950 --> 00:38:56,109 for a particular record associated with 1080 00:38:56,110 --> 00:38:59,169 Bob without however 1081 00:38:59,170 --> 00:39:01,479 leaking which record that is because 1082 00:39:01,480 --> 00:39:04,119 that, in fact, would allow us to then 1083 00:39:04,120 --> 00:39:05,739 have private presence. 1084 00:39:05,740 --> 00:39:08,439 And in fact, this is exactly 1085 00:39:08,440 --> 00:39:10,539 the protocol that Ian 1086 00:39:10,540 --> 00:39:11,649 talked about before. 1087 00:39:11,650 --> 00:39:13,869 And the key inside, behind the DP five 1088 00:39:13,870 --> 00:39:16,089 protocols is that we use 1089 00:39:16,090 --> 00:39:18,399 private information retrieval 1090 00:39:18,400 --> 00:39:20,649 to recover, 1091 00:39:20,650 --> 00:39:23,109 to request, to query 1092 00:39:23,110 --> 00:39:25,209 on Alice's side a record that corresponds 1093 00:39:25,210 --> 00:39:27,129 to all her friends without letting the 1094 00:39:27,130 --> 00:39:29,559 infrastructure find out which 1095 00:39:29,560 --> 00:39:30,560 are those friends. 1096 00:39:31,700 --> 00:39:33,799 OK, so here is how the 1097 00:39:33,800 --> 00:39:35,600 five works cryptographically, 1098 00:39:36,770 --> 00:39:39,349 we divide first of all time into epochs. 1099 00:39:39,350 --> 00:39:41,599 This could be longer, short, and 1100 00:39:41,600 --> 00:39:43,669 I will discuss this in a second. 1101 00:39:43,670 --> 00:39:45,979 And the idea is that at every epoch, 1102 00:39:45,980 --> 00:39:48,499 users register their presence 1103 00:39:48,500 --> 00:39:50,929 with the service and 1104 00:39:50,930 --> 00:39:53,209 at each epoch, other users 1105 00:39:53,210 --> 00:39:55,429 or the same users can actually recover 1106 00:39:55,430 --> 00:39:57,500 who is online in the previous epochs. 1107 00:39:59,430 --> 00:40:00,430 So. 1108 00:40:01,930 --> 00:40:04,179 Alice, when she needs to register, first 1109 00:40:04,180 --> 00:40:06,549 of all, takes a key she shares with Bob 1110 00:40:06,550 --> 00:40:08,769 Key of Alice and Bob and using 1111 00:40:08,770 --> 00:40:10,479 a pseudo random function, which you can 1112 00:40:10,480 --> 00:40:12,609 think of as a hash 1113 00:40:12,610 --> 00:40:14,650 function that is keyed, 1114 00:40:16,090 --> 00:40:18,339 basically applies that to the 1115 00:40:18,340 --> 00:40:19,929 time epoch 1116 00:40:20,980 --> 00:40:23,169 and gets to things. 1117 00:40:23,170 --> 00:40:25,509 First of all, she gets an ID 1118 00:40:25,510 --> 00:40:26,939 for. 1119 00:40:26,940 --> 00:40:29,159 Alice's presence at this time 1120 00:40:29,160 --> 00:40:31,649 period, and she also gets a symmetric 1121 00:40:31,650 --> 00:40:33,749 key. OK, now, 1122 00:40:33,750 --> 00:40:35,099 Alice, first of all, can use this 1123 00:40:35,100 --> 00:40:37,949 symmetric and effectively encrypt 1124 00:40:37,950 --> 00:40:40,739 her status using 1125 00:40:40,740 --> 00:40:42,509 a strong cipher and using a particular 1126 00:40:42,510 --> 00:40:44,880 mode of operation called 1127 00:40:47,070 --> 00:40:49,499 a D authenticated 1128 00:40:49,500 --> 00:40:52,059 encryption with associated data. 1129 00:40:52,060 --> 00:40:54,299 OK, and that 1130 00:40:54,300 --> 00:40:56,129 basically is just secure encryption. 1131 00:40:56,130 --> 00:40:58,109 You can think about it in this way. 1132 00:40:58,110 --> 00:41:00,899 And then she can make a record 1133 00:41:00,900 --> 00:41:03,119 of just the idea for this period 1134 00:41:03,120 --> 00:41:05,399 and the encrypted status and just 1135 00:41:05,400 --> 00:41:08,419 store it in the database. 1136 00:41:08,420 --> 00:41:10,829 OK, now 1137 00:41:10,830 --> 00:41:12,959 Bob comes along at the 1138 00:41:12,960 --> 00:41:15,209 next period and wants to find 1139 00:41:15,210 --> 00:41:17,399 out if Alice is online. 1140 00:41:17,400 --> 00:41:19,499 OK, so Bob, of 1141 00:41:19,500 --> 00:41:21,869 course, shares a key with Alice the cab. 1142 00:41:21,870 --> 00:41:24,299 So what Bob does is he uses the same 1143 00:41:24,300 --> 00:41:27,089 pseudo random function with the same key 1144 00:41:27,090 --> 00:41:29,159 and applies that to the previous time 1145 00:41:29,160 --> 00:41:31,469 period identifier and extracts 1146 00:41:31,470 --> 00:41:33,659 hopefully the same idea in the same key, 1147 00:41:34,710 --> 00:41:36,659 then using the I.D. 1148 00:41:36,660 --> 00:41:38,729 and a private information retrieval 1149 00:41:38,730 --> 00:41:39,599 protocol. 1150 00:41:39,600 --> 00:41:41,969 Bob can try to retrieve 1151 00:41:41,970 --> 00:41:43,919 the record that Alice has left in the 1152 00:41:43,920 --> 00:41:45,059 database. 1153 00:41:45,060 --> 00:41:47,159 OK, and hopefully he gets back 1154 00:41:47,160 --> 00:41:49,559 the record, see, and then tries 1155 00:41:49,560 --> 00:41:52,319 to decrypt that record with the key. 1156 00:41:52,320 --> 00:41:54,389 And if the decryption is successful, 1157 00:41:54,390 --> 00:41:56,399 it means that Alice is on line in the 1158 00:41:56,400 --> 00:41:57,749 previous epoch. 1159 00:41:57,750 --> 00:41:58,750 And furthermore. 1160 00:41:59,860 --> 00:42:01,539 He can decrypt the status. 1161 00:42:02,920 --> 00:42:03,920 OK. 1162 00:42:04,790 --> 00:42:06,979 Now, I hope that 1163 00:42:06,980 --> 00:42:09,139 everybody is half convinced that this 1164 00:42:09,140 --> 00:42:10,189 is secure. 1165 00:42:10,190 --> 00:42:12,079 This would just work and this would 1166 00:42:12,080 --> 00:42:14,899 defeat subject to all our assumptions, 1167 00:42:14,900 --> 00:42:16,669 very powerful adversaries from finding 1168 00:42:16,670 --> 00:42:18,769 out who's friends with whom and who's 1169 00:42:18,770 --> 00:42:19,940 online and who's 1170 00:42:21,050 --> 00:42:23,119 who's actually caring who else is 1171 00:42:23,120 --> 00:42:24,350 online at any point. 1172 00:42:25,940 --> 00:42:28,069 Now, however, there is a problem with 1173 00:42:28,070 --> 00:42:30,109 all this, which is associated with the 1174 00:42:30,110 --> 00:42:31,969 fact that this database tends to get very 1175 00:42:31,970 --> 00:42:32,959 large. 1176 00:42:32,960 --> 00:42:35,299 As I said, for every relationship 1177 00:42:35,300 --> 00:42:37,459 in the world, we will have to include 1178 00:42:37,460 --> 00:42:39,679 a record in the database. 1179 00:42:39,680 --> 00:42:41,209 And furthermore, we would like to include 1180 00:42:41,210 --> 00:42:43,189 some more records in order to hide how 1181 00:42:43,190 --> 00:42:45,319 many friends each person has so that each 1182 00:42:45,320 --> 00:42:47,749 person always basically submits 100 1183 00:42:47,750 --> 00:42:50,029 relationships and queries for 100 1184 00:42:50,030 --> 00:42:51,169 relationships as well. 1185 00:42:51,170 --> 00:42:53,739 So these databases tend to get quite big. 1186 00:42:53,740 --> 00:42:55,879 OK, and that's a problem because big 1187 00:42:55,880 --> 00:42:57,949 databases are less efficient 1188 00:42:57,950 --> 00:42:59,149 to update and query. 1189 00:42:59,150 --> 00:43:01,219 And we would like these time periods, 1190 00:43:01,220 --> 00:43:03,469 these epochs, to be as short as possible 1191 00:43:03,470 --> 00:43:05,929 because you have to register at one epoch 1192 00:43:05,930 --> 00:43:08,119 and then query at the next 1193 00:43:08,120 --> 00:43:09,889 epoch who was there before. 1194 00:43:09,890 --> 00:43:12,079 So if these e-books are a day, you just 1195 00:43:12,080 --> 00:43:13,459 find out the next day that someone was 1196 00:43:13,460 --> 00:43:14,419 online the previous day. 1197 00:43:14,420 --> 00:43:16,129 And that's not very useful, let's face 1198 00:43:16,130 --> 00:43:17,130 it. 1199 00:43:17,870 --> 00:43:19,849 So we need to basically do something to 1200 00:43:19,850 --> 00:43:21,769 improve efficiency so that these queries 1201 00:43:21,770 --> 00:43:23,479 and these registrations are very fast. 1202 00:43:23,480 --> 00:43:25,999 And as my academic grand grandfather 1203 00:43:26,000 --> 00:43:27,350 said, that David Wheeler, 1204 00:43:28,520 --> 00:43:30,289 any problem in computer science can be 1205 00:43:30,290 --> 00:43:32,269 solved with another layer of indirection. 1206 00:43:32,270 --> 00:43:33,270 He, by the way. 1207 00:43:35,640 --> 00:43:38,069 He is worth a round of applause 1208 00:43:38,070 --> 00:43:40,019 because he invented the subroutine along 1209 00:43:40,020 --> 00:43:41,699 with many other cool things, which is 1210 00:43:41,700 --> 00:43:43,199 indeed a layer of redirection. 1211 00:43:49,190 --> 00:43:51,319 She was also wise enough to 1212 00:43:51,320 --> 00:43:53,509 add that usually this creates another 1213 00:43:53,510 --> 00:43:54,510 problem. 1214 00:43:56,440 --> 00:43:58,539 So what do we do basically 1215 00:43:58,540 --> 00:44:00,699 is we run two versions of the protocol 1216 00:44:00,700 --> 00:44:02,769 that are described to you back 1217 00:44:02,770 --> 00:44:04,989 to back, one feeding into the other, 1218 00:44:04,990 --> 00:44:07,149 we define two different times of time 1219 00:44:07,150 --> 00:44:08,829 period, two different epochs, the long 1220 00:44:08,830 --> 00:44:11,169 epoch and the short epoch. 1221 00:44:11,170 --> 00:44:13,329 And we basically, 1222 00:44:13,330 --> 00:44:15,399 first of all, have Alice 1223 00:44:15,400 --> 00:44:17,559 and Bob store one 1224 00:44:17,560 --> 00:44:19,569 type of recording the long epoch into the 1225 00:44:19,570 --> 00:44:21,819 database. And that record has 1226 00:44:21,820 --> 00:44:23,889 as a status, just a public 1227 00:44:23,890 --> 00:44:25,959 key. So now, Alice, 1228 00:44:25,960 --> 00:44:28,239 basically in a long book that we envisage 1229 00:44:28,240 --> 00:44:30,429 to be about a day, just stores 1230 00:44:30,430 --> 00:44:32,859 a public key for Bob 1231 00:44:32,860 --> 00:44:35,169 into this database. 1232 00:44:35,170 --> 00:44:37,719 And then in the short ebook, 1233 00:44:37,720 --> 00:44:39,999 Bob can both retrieve the 1234 00:44:40,000 --> 00:44:42,339 public key associated with Alice 1235 00:44:42,340 --> 00:44:44,439 in the long period and then use that 1236 00:44:44,440 --> 00:44:47,079 key to query for Alice 1237 00:44:47,080 --> 00:44:48,249 in the short epoch. 1238 00:44:48,250 --> 00:44:50,139 Now, the trick here is that this public 1239 00:44:50,140 --> 00:44:52,479 key is shared by old friends 1240 00:44:52,480 --> 00:44:53,369 of Alice. 1241 00:44:53,370 --> 00:44:55,659 OK, so we now go from a situation 1242 00:44:55,660 --> 00:44:57,129 where we have one record per 1243 00:44:57,130 --> 00:44:58,689 relationship, which is still the case in 1244 00:44:58,690 --> 00:45:00,879 the long term database to just 1245 00:45:00,880 --> 00:45:03,189 having one record for active users, 1246 00:45:03,190 --> 00:45:05,649 which makes for a much shorter database. 1247 00:45:05,650 --> 00:45:07,869 And now that becomes tractable enough 1248 00:45:07,870 --> 00:45:09,819 of these periods to be as short as a 1249 00:45:09,820 --> 00:45:11,799 minute or even a few seconds, depending 1250 00:45:11,800 --> 00:45:13,659 on how many machines you throw at the 1251 00:45:13,660 --> 00:45:15,789 problem. So Alice can then 1252 00:45:15,790 --> 00:45:17,859 store using this public key in the short 1253 00:45:17,860 --> 00:45:20,199 term database, her actual 1254 00:45:20,200 --> 00:45:23,229 status. And Bob will retrieve every 1255 00:45:23,230 --> 00:45:25,569 minute, let's say, the status of Alice 1256 00:45:25,570 --> 00:45:27,069 back and make sure that she's both in 1257 00:45:27,070 --> 00:45:29,319 line and that he 1258 00:45:29,320 --> 00:45:32,049 has an up to date status for her. 1259 00:45:32,050 --> 00:45:33,999 By the way, the status is very important 1260 00:45:34,000 --> 00:45:35,889 to us because we don't just think of it 1261 00:45:35,890 --> 00:45:38,149 as being busy, not there or, you know, 1262 00:45:38,150 --> 00:45:39,489 go away for five minutes. 1263 00:45:39,490 --> 00:45:41,559 But we actually think of this protocol as 1264 00:45:41,560 --> 00:45:43,989 being able to support other 1265 00:45:43,990 --> 00:45:45,889 cryptographic and anonymity protocol. 1266 00:45:45,890 --> 00:45:47,679 So you can think of this status 1267 00:45:47,680 --> 00:45:49,929 information as being by the way, this 1268 00:45:49,930 --> 00:45:52,089 is my anonymous pseudonym for you to 1269 00:45:52,090 --> 00:45:53,679 contact me on this service. 1270 00:45:53,680 --> 00:45:55,539 Or by the way, this is actually the 1271 00:45:55,540 --> 00:45:57,340 address of a Tor 1272 00:45:58,450 --> 00:46:00,579 hidden service on which you can talk to 1273 00:46:00,580 --> 00:46:01,179 me. 1274 00:46:01,180 --> 00:46:02,799 So we were extremely keen to have this 1275 00:46:02,800 --> 00:46:04,929 associated information so that we can 1276 00:46:04,930 --> 00:46:07,479 build more secure chat protocols 1277 00:46:07,480 --> 00:46:09,669 on top of this presence protocol 1278 00:46:09,670 --> 00:46:11,469 and on the back of its properties. 1279 00:46:11,470 --> 00:46:12,470 Now, 1280 00:46:13,780 --> 00:46:15,609 cypherpunks write code, I believe. 1281 00:46:15,610 --> 00:46:16,899 Is that how it goes? 1282 00:46:16,900 --> 00:46:18,009 That's how it used to go. 1283 00:46:18,010 --> 00:46:19,419 And I hope that this is how it's going to 1284 00:46:19,420 --> 00:46:20,799 go from now on as well. 1285 00:46:20,800 --> 00:46:22,869 So all of this has been implemented. 1286 00:46:24,220 --> 00:46:26,799 We use the Pursey plus plus code 1287 00:46:26,800 --> 00:46:29,049 as the core for our peer protocol 1288 00:46:29,050 --> 00:46:31,209 and the rest of the DP five protocol 1289 00:46:31,210 --> 00:46:33,399 at a low level is implemented in C++ 1290 00:46:33,400 --> 00:46:35,409 and we have python bindings that we use 1291 00:46:35,410 --> 00:46:37,629 as part of a cherry pie framework 1292 00:46:37,630 --> 00:46:39,699 and Twisted 1293 00:46:39,700 --> 00:46:42,009 Core to implement 1294 00:46:42,010 --> 00:46:44,229 all of the networking so that 1295 00:46:44,230 --> 00:46:46,389 we can time it and make sure 1296 00:46:46,390 --> 00:46:47,439 that it all works. 1297 00:46:47,440 --> 00:46:49,209 However, this is still a work in progress 1298 00:46:49,210 --> 00:46:50,859 because it has not been integrated with 1299 00:46:50,860 --> 00:46:51,759 any client. 1300 00:46:51,760 --> 00:46:53,439 So the protocol is there. 1301 00:46:53,440 --> 00:46:54,669 We can do all our timings. 1302 00:46:54,670 --> 00:46:56,139 Sadly, though, we can't actually find 1303 00:46:56,140 --> 00:46:58,419 who's online, who's not offline 1304 00:46:58,420 --> 00:47:00,519 among real users, just our 1305 00:47:00,520 --> 00:47:02,409 robots that do our tests for the moment. 1306 00:47:02,410 --> 00:47:04,569 So this is a missing part that I hope 1307 00:47:04,570 --> 00:47:06,760 we will be working on the next year. 1308 00:47:07,780 --> 00:47:10,179 And the cost of running this 1309 00:47:10,180 --> 00:47:12,249 is surprisingly low 1310 00:47:12,250 --> 00:47:14,019 for the kind of very strong properties it 1311 00:47:14,020 --> 00:47:15,020 offers. 1312 00:47:15,940 --> 00:47:18,069 Sadly, the cost per user 1313 00:47:18,070 --> 00:47:20,139 rise as the more users you have, 1314 00:47:20,140 --> 00:47:22,899 because that's how Pyaar is 1315 00:47:22,900 --> 00:47:25,089 OK. Now, if you have a service with, 1316 00:47:25,090 --> 00:47:27,189 let's say, 10000 users, it 1317 00:47:27,190 --> 00:47:30,129 will cost you a fraction of of a penny 1318 00:47:30,130 --> 00:47:32,589 per user to actually run this 1319 00:47:32,590 --> 00:47:34,689 protocol for a month. 1320 00:47:34,690 --> 00:47:36,399 If, however, you start having millions 1321 00:47:36,400 --> 00:47:38,289 and millions of users, it will cost you 1322 00:47:38,290 --> 00:47:40,239 in the order of magnitude of a dollar or 1323 00:47:40,240 --> 00:47:42,939 more per user to actually serve 1324 00:47:42,940 --> 00:47:45,219 users given rational loads. 1325 00:47:46,330 --> 00:47:48,519 So the takeaways here are 1326 00:47:48,520 --> 00:47:51,039 that, first of all, metadata 1327 00:47:51,040 --> 00:47:53,769 in chat protocols and social protocols 1328 00:47:53,770 --> 00:47:55,869 is an active target for national 1329 00:47:55,870 --> 00:47:57,949 security agencies and everybody else. 1330 00:47:57,950 --> 00:47:59,769 So we need to protect it if we're serious 1331 00:47:59,770 --> 00:48:01,839 about protecting communications, 1332 00:48:01,840 --> 00:48:03,909 secrecy, because we know how to 1333 00:48:03,910 --> 00:48:04,839 protect content. 1334 00:48:04,840 --> 00:48:06,909 But metadata is something we're not very 1335 00:48:06,910 --> 00:48:08,349 good yet at protecting. 1336 00:48:08,350 --> 00:48:10,809 OK, now private information retrieval 1337 00:48:10,810 --> 00:48:13,509 as a general primitive is pretty cool. 1338 00:48:13,510 --> 00:48:15,709 OK, you can do things that many of you 1339 00:48:15,710 --> 00:48:17,169 at the beginning of this talk were not 1340 00:48:17,170 --> 00:48:18,909 convinced were even possible. 1341 00:48:18,910 --> 00:48:21,129 And Deep five leverages private 1342 00:48:21,130 --> 00:48:22,899 information retrieval in order to 1343 00:48:22,900 --> 00:48:24,759 implement a specific protocol that does 1344 00:48:24,760 --> 00:48:25,839 private presence. 1345 00:48:25,840 --> 00:48:28,389 And given the characteristics 1346 00:48:28,390 --> 00:48:30,039 of this protocol, it is actually quite 1347 00:48:30,040 --> 00:48:32,319 practical and I hope that many 1348 00:48:32,320 --> 00:48:34,149 services will start considering using 1349 00:48:34,150 --> 00:48:36,609 this kind of technology prediction. 1350 00:48:36,610 --> 00:48:37,869 Thank you very much. We're open for 1351 00:48:37,870 --> 00:48:38,870 questions. 1352 00:48:47,020 --> 00:48:48,279 OK. 1353 00:48:48,280 --> 00:48:50,439 Oh, the git repository. 1354 00:48:50,440 --> 00:48:53,589 OK, could you line up at the microphones 1355 00:48:53,590 --> 00:48:55,389 for the questions? 1356 00:48:55,390 --> 00:48:57,519 And we also have one 1357 00:48:57,520 --> 00:48:58,849 question from the Internet. 1358 00:48:58,850 --> 00:49:01,329 Please go ahead. Our signal angel. 1359 00:49:01,330 --> 00:49:02,049 Hi. 1360 00:49:02,050 --> 00:49:03,489 So the first question or the only 1361 00:49:03,490 --> 00:49:05,589 question currently is how does 1362 00:49:05,590 --> 00:49:07,779 DP five program that Eve gets 1363 00:49:07,780 --> 00:49:10,119 information about Ellis or BOP, which 1364 00:49:10,120 --> 00:49:11,440 they don't want to share with her? 1365 00:49:13,550 --> 00:49:15,229 Right. So is the sun. 1366 00:49:15,230 --> 00:49:15,799 Yes. 1367 00:49:15,800 --> 00:49:18,259 OK, so if you remember 1368 00:49:18,260 --> 00:49:19,819 at the beginning, George showed that 1369 00:49:19,820 --> 00:49:21,919 Alice and Bob shared a 1370 00:49:21,920 --> 00:49:23,149 key. 1371 00:49:23,150 --> 00:49:25,519 Right. And Alice 1372 00:49:25,520 --> 00:49:27,379 shares a separate key with each of her 1373 00:49:27,380 --> 00:49:29,420 friends. The key is what enables 1374 00:49:30,680 --> 00:49:33,319 Bob to look up information about Alice. 1375 00:49:33,320 --> 00:49:35,569 But no, none 1376 00:49:35,570 --> 00:49:37,429 of Alice is non friends can look up 1377 00:49:37,430 --> 00:49:39,349 information. So Eve won't have a shared 1378 00:49:39,350 --> 00:49:41,599 key with Alice, and so he won't be able 1379 00:49:41,600 --> 00:49:43,909 to look up the information in the online 1380 00:49:43,910 --> 00:49:45,349 database. 1381 00:49:45,350 --> 00:49:48,079 OK, microphone number four there, please. 1382 00:49:48,080 --> 00:49:49,269 Hello. Thank you. 1383 00:49:49,270 --> 00:49:51,349 And I wanted 1384 00:49:51,350 --> 00:49:53,899 to ask if you had looked at the 1385 00:49:53,900 --> 00:49:55,849 the price graph looks pretty terrifying 1386 00:49:55,850 --> 00:49:57,439 because if you have one million users and 1387 00:49:57,440 --> 00:49:59,569 if one dollar per user, that's one 1388 00:49:59,570 --> 00:50:01,249 million dollars for months, that's quite 1389 00:50:01,250 --> 00:50:02,749 a lot of money. Have you looked at what 1390 00:50:02,750 --> 00:50:03,979 is actually causing this? 1391 00:50:03,980 --> 00:50:06,499 Is it the Pyaar requests? 1392 00:50:06,500 --> 00:50:07,699 Yeah, it's exactly right. 1393 00:50:07,700 --> 00:50:09,799 So it's I mean, it's a lot 1394 00:50:09,800 --> 00:50:11,839 of money, but it's not a ridiculous lot 1395 00:50:11,840 --> 00:50:14,119 of money. If you really have a million 1396 00:50:14,120 --> 00:50:16,489 users running a privacy 1397 00:50:16,490 --> 00:50:19,219 service for a subscription 1398 00:50:19,220 --> 00:50:21,889 rate of you charge them a buck a month 1399 00:50:21,890 --> 00:50:24,439 is not a ridiculous, totally ridiculous 1400 00:50:24,440 --> 00:50:26,119 thing to do. But it is unfortunate that 1401 00:50:26,120 --> 00:50:27,679 the price does go up per user. 1402 00:50:27,680 --> 00:50:29,869 And the answer is the reason is exactly 1403 00:50:29,870 --> 00:50:31,969 because of PR, because the 1404 00:50:31,970 --> 00:50:34,579 size of the database scales with 1405 00:50:34,580 --> 00:50:36,829 the number of of 1406 00:50:36,830 --> 00:50:37,849 users. 1407 00:50:37,850 --> 00:50:40,369 Right. And so every query 1408 00:50:40,370 --> 00:50:42,649 does a PR look 1409 00:50:42,650 --> 00:50:44,749 up on an increasing 1410 00:50:44,750 --> 00:50:46,609 size database, increasing with the number 1411 00:50:46,610 --> 00:50:48,709 of users and the cost of a PR query 1412 00:50:48,710 --> 00:50:50,059 is proportional to the size of the 1413 00:50:50,060 --> 00:50:51,709 database. Why is that? 1414 00:50:51,710 --> 00:50:54,169 Well, you can easily reason 1415 00:50:54,170 --> 00:50:56,269 that if the server has to 1416 00:50:56,270 --> 00:50:58,789 learn nothing about what record 1417 00:50:58,790 --> 00:51:00,949 you were interested in, then it clearly 1418 00:51:00,950 --> 00:51:03,019 has to process every record in 1419 00:51:03,020 --> 00:51:05,089 the database somehow, because if 1420 00:51:05,090 --> 00:51:07,099 it doesn't touch this record on disk, 1421 00:51:07,100 --> 00:51:08,779 then clearly you didn't ask for that 1422 00:51:08,780 --> 00:51:10,129 record. Right? 1423 00:51:10,130 --> 00:51:13,099 So the server has to process 1424 00:51:13,100 --> 00:51:15,409 every record in the database in 1425 00:51:15,410 --> 00:51:17,959 some fashion. And so it's computational 1426 00:51:17,960 --> 00:51:20,269 cost is proportional to the size 1427 00:51:20,270 --> 00:51:22,339 of the database, but the communication 1428 00:51:22,340 --> 00:51:23,540 cost is much smaller. 1429 00:51:24,920 --> 00:51:27,079 OK, microphone number one up here, 1430 00:51:27,080 --> 00:51:28,249 please. 1431 00:51:28,250 --> 00:51:29,569 Hi, thanks for the talk, was really 1432 00:51:29,570 --> 00:51:31,639 interesting. I have a question about 1433 00:51:31,640 --> 00:51:33,739 the, um, the non 1434 00:51:33,740 --> 00:51:35,179 collusion assumption. 1435 00:51:35,180 --> 00:51:37,309 Um, so in the scenario where 1436 00:51:37,310 --> 00:51:39,529 there's a patent server, 1437 00:51:39,530 --> 00:51:41,839 Alice doesn't trust the one server 1438 00:51:41,840 --> 00:51:44,269 to to not use the 1439 00:51:44,270 --> 00:51:46,849 the information requests for their own 1440 00:51:46,850 --> 00:51:48,839 competitive advantage. 1441 00:51:48,840 --> 00:51:51,049 Seems like in that instance 1442 00:51:51,050 --> 00:51:52,639 where you've got several different servers, 1443 00:51:52,640 --> 00:51:54,319 she still has to trust at least one of 1444 00:51:54,320 --> 00:51:55,429 them not to collude. 1445 00:51:55,430 --> 00:51:57,949 And why is the first assumption 1446 00:51:57,950 --> 00:51:58,969 not reasonable? 1447 00:51:58,970 --> 00:52:01,309 But the second one is if you trust 1448 00:52:01,310 --> 00:52:03,409 a server to to to 1449 00:52:03,410 --> 00:52:05,479 not to not collude, then why 1450 00:52:05,480 --> 00:52:07,609 wouldn't you also trust them not to to 1451 00:52:07,610 --> 00:52:10,069 use your in your question. 1452 00:52:10,070 --> 00:52:12,169 Right. So there are some I 1453 00:52:12,170 --> 00:52:14,239 mean, it is unsettling to some 1454 00:52:14,240 --> 00:52:16,909 extent that for many protocols 1455 00:52:16,910 --> 00:52:19,369 you cannot achieve them on your own 1456 00:52:19,370 --> 00:52:21,049 and you cannot achieve them just with 1457 00:52:21,050 --> 00:52:22,519 your communication partner. 1458 00:52:22,520 --> 00:52:24,679 One classic example of that is anonymity 1459 00:52:24,680 --> 00:52:26,359 protocols. Right? I mean, we usually have 1460 00:52:26,360 --> 00:52:27,739 to use relays. 1461 00:52:27,740 --> 00:52:29,989 And the traditional wisdom is that using 1462 00:52:29,990 --> 00:52:32,179 one relays is actually very fragile 1463 00:52:32,180 --> 00:52:34,249 because at any time this one person, if 1464 00:52:34,250 --> 00:52:36,319 they are corrupt to some extent or 1465 00:52:36,320 --> 00:52:37,939 if they're coerced, even if they were not 1466 00:52:37,940 --> 00:52:40,069 corrupt, might actually be able to to 1467 00:52:40,070 --> 00:52:41,359 leak who you're talking to. 1468 00:52:42,590 --> 00:52:44,659 You know, however, if you have more than 1469 00:52:44,660 --> 00:52:46,579 one, they would all have to be either 1470 00:52:46,580 --> 00:52:49,099 corrupted or collude or collude 1471 00:52:49,100 --> 00:52:50,269 to to do that. 1472 00:52:50,270 --> 00:52:52,579 So all the logic that goes 1473 00:52:52,580 --> 00:52:54,499 into why we trust things like mixed 1474 00:52:54,500 --> 00:52:56,569 networks or onion routing 1475 00:52:56,570 --> 00:52:58,789 to some extent or 1476 00:52:58,790 --> 00:53:00,799 things like that really applies here. 1477 00:53:00,800 --> 00:53:02,839 Why would you trust more than one in 1478 00:53:02,840 --> 00:53:04,189 preference to just one? 1479 00:53:04,190 --> 00:53:05,269 Because they might be in different 1480 00:53:05,270 --> 00:53:06,949 jurisdictions, because they might 1481 00:53:06,950 --> 00:53:08,569 actually have different operators that 1482 00:53:08,570 --> 00:53:10,759 will do different things to 1483 00:53:10,760 --> 00:53:12,439 protect the data, because it's actually 1484 00:53:12,440 --> 00:53:14,149 logistically quite difficult to 1485 00:53:14,150 --> 00:53:16,519 simultaneously go to people 1486 00:53:16,520 --> 00:53:18,439 and simultaneously ask for the secret 1487 00:53:18,440 --> 00:53:20,269 information. And remember, something I 1488 00:53:20,270 --> 00:53:22,159 don't mention here is that it is 1489 00:53:22,160 --> 00:53:23,629 perfectly forward, secure. 1490 00:53:23,630 --> 00:53:25,549 So going after some amount of time 1491 00:53:25,550 --> 00:53:27,739 doesn't work. You have to simultaneously 1492 00:53:27,740 --> 00:53:28,819 go there. Right. 1493 00:53:28,820 --> 00:53:30,949 But it is a social assumption and social 1494 00:53:30,950 --> 00:53:33,529 assumptions are fragile 1495 00:53:33,530 --> 00:53:35,719 because they rely on people like us and 1496 00:53:35,720 --> 00:53:37,429 our community is actually providing those 1497 00:53:37,430 --> 00:53:38,359 infrastructures. 1498 00:53:38,360 --> 00:53:40,729 And as the people from other 1499 00:53:40,730 --> 00:53:42,229 free software projects that rely on 1500 00:53:42,230 --> 00:53:44,269 those, no, this is not automatic. 1501 00:53:44,270 --> 00:53:45,799 If people like us do not run these 1502 00:53:45,800 --> 00:53:47,329 things, it's very unlikely that we'll 1503 00:53:47,330 --> 00:53:48,410 ever be run by anyone. 1504 00:53:49,830 --> 00:53:51,959 OK, microphone number six back 1505 00:53:51,960 --> 00:53:53,309 there, please. 1506 00:53:53,310 --> 00:53:55,319 How we're charting the user database 1507 00:53:55,320 --> 00:53:57,179 effect performance and the privacy 1508 00:53:57,180 --> 00:54:00,059 correct characteristics of the system. 1509 00:54:00,060 --> 00:54:02,129 So it would so if you charged 1510 00:54:02,130 --> 00:54:04,679 the user database into copses, 1511 00:54:04,680 --> 00:54:06,839 the performance gets better by a factor 1512 00:54:06,840 --> 00:54:09,209 of K, but then 1513 00:54:09,210 --> 00:54:11,219 only users in the same Shahd can be 1514 00:54:11,220 --> 00:54:12,220 friends with each other. 1515 00:54:13,470 --> 00:54:15,869 Right, so if your 1516 00:54:15,870 --> 00:54:18,209 user population naturally 1517 00:54:18,210 --> 00:54:20,639 falls into these shards, OK, 1518 00:54:20,640 --> 00:54:22,859 but in some sense, that's exactly 1519 00:54:22,860 --> 00:54:24,569 if that's true, that's exactly the 1520 00:54:24,570 --> 00:54:26,729 information you're trying to protect, 1521 00:54:26,730 --> 00:54:26,999 right? 1522 00:54:27,000 --> 00:54:29,189 You don't want someone 1523 00:54:29,190 --> 00:54:31,379 to observe which Shajarian which would 1524 00:54:31,380 --> 00:54:32,889 be visible. 1525 00:54:32,890 --> 00:54:35,139 Right. So that's why we 1526 00:54:35,140 --> 00:54:37,329 don't we try not to do that, because 1527 00:54:37,330 --> 00:54:39,399 if you would guard the database, 1528 00:54:39,400 --> 00:54:40,929 although your performance goes up, your 1529 00:54:40,930 --> 00:54:43,210 privacy goes quite a bit down. 1530 00:54:44,590 --> 00:54:46,149 OK, then we have a question from 1531 00:54:46,150 --> 00:54:48,339 microphone number two and two more from 1532 00:54:48,340 --> 00:54:49,340 the Internet then. 1533 00:54:50,410 --> 00:54:51,849 Hey, quick question. 1534 00:54:51,850 --> 00:54:54,039 Doesn't the public key that's 1535 00:54:54,040 --> 00:54:56,319 used to query the short 1536 00:54:56,320 --> 00:54:58,479 apoc database, doesn't 1537 00:54:58,480 --> 00:55:01,269 that allow a third party to reconstruct, 1538 00:55:01,270 --> 00:55:03,339 again, a graph which represents 1539 00:55:03,340 --> 00:55:05,799 the real one? Or is the public also 1540 00:55:05,800 --> 00:55:08,049 behind a picture that doesn't really make 1541 00:55:08,050 --> 00:55:10,599 it public but is just shared between 1542 00:55:10,600 --> 00:55:12,819 the users who not only Alice's 1543 00:55:12,820 --> 00:55:15,459 friends learn that key? 1544 00:55:15,460 --> 00:55:17,379 Right, because you have to go through the 1545 00:55:17,380 --> 00:55:19,539 first instance of the DP five 1546 00:55:19,540 --> 00:55:21,999 protocol to get that key 1547 00:55:22,000 --> 00:55:24,189 and then so only your friends have 1548 00:55:24,190 --> 00:55:24,459 it. 1549 00:55:24,460 --> 00:55:26,079 So it's a public key. 1550 00:55:26,080 --> 00:55:27,489 And in a sense that 1551 00:55:28,510 --> 00:55:30,489 Alice has the private half and other 1552 00:55:30,490 --> 00:55:32,529 people have the public, but not everybody 1553 00:55:32,530 --> 00:55:34,509 has the public if the closest friends of 1554 00:55:34,510 --> 00:55:35,079 the public. 1555 00:55:35,080 --> 00:55:37,449 So the public is not really the query 1556 00:55:37,450 --> 00:55:38,859 that goes to the. 1557 00:55:38,860 --> 00:55:40,059 It's never revealed. 1558 00:55:40,060 --> 00:55:41,979 Right. It's never revealed to anyone 1559 00:55:41,980 --> 00:55:42,879 outside that circle. 1560 00:55:42,880 --> 00:55:45,129 And the second round of protocol 1561 00:55:45,130 --> 00:55:46,549 derives keys from that key. 1562 00:55:46,550 --> 00:55:48,399 So it's never actually revealed in such a 1563 00:55:48,400 --> 00:55:49,869 way that it can link different queries 1564 00:55:49,870 --> 00:55:50,959 from different people. 1565 00:55:50,960 --> 00:55:52,179 Thank you, ma'am. 1566 00:55:52,180 --> 00:55:54,279 OK, our signal answer a question 1567 00:55:54,280 --> 00:55:55,269 from the Internet. 1568 00:55:55,270 --> 00:55:57,459 So there are some 1569 00:55:57,460 --> 00:55:59,559 similar questions 1570 00:55:59,560 --> 00:56:00,819 going along the line. 1571 00:56:00,820 --> 00:56:02,559 So the first one, what do I have to do to 1572 00:56:02,560 --> 00:56:04,419 use this on Jaba? 1573 00:56:04,420 --> 00:56:06,549 The second one, can 1574 00:56:06,550 --> 00:56:08,589 I use this to build a distributed DNS 1575 00:56:08,590 --> 00:56:10,389 system, which is I think. 1576 00:56:10,390 --> 00:56:13,209 Yeah. Can I use this for X. 1577 00:56:13,210 --> 00:56:14,739 Well the first question is more easy, so 1578 00:56:14,740 --> 00:56:16,119 I'll take it and then I'll leave the hard 1579 00:56:16,120 --> 00:56:17,889 question for you. 1580 00:56:17,890 --> 00:56:20,049 So what you need to do 1581 00:56:20,050 --> 00:56:21,729 to use that on Jaberi, understand 1582 00:56:21,730 --> 00:56:23,229 correctly is the question is that you 1583 00:56:23,230 --> 00:56:24,879 will have to spend some time integrating 1584 00:56:24,880 --> 00:56:26,409 this protocol to the job of presence 1585 00:56:26,410 --> 00:56:27,999 mechanism, which is not something we have 1586 00:56:28,000 --> 00:56:29,079 done yet. 1587 00:56:29,080 --> 00:56:30,549 We have actually spent quite some time 1588 00:56:30,550 --> 00:56:32,829 thinking how this could could be done. 1589 00:56:32,830 --> 00:56:34,959 And we foresee a 1590 00:56:34,960 --> 00:56:36,879 solution based on implementing a kind of 1591 00:56:36,880 --> 00:56:38,739 JABA protocol proxy or something like 1592 00:56:38,740 --> 00:56:40,869 that, working where your client 1593 00:56:40,870 --> 00:56:43,029 talks to some local proxy 1594 00:56:43,030 --> 00:56:45,549 and the local proxy actually translated 1595 00:56:45,550 --> 00:56:47,919 the president related event into DP five 1596 00:56:47,920 --> 00:56:49,929 and then translates the responses back 1597 00:56:49,930 --> 00:56:52,299 into Jabor events so that we can reuse 1598 00:56:52,300 --> 00:56:54,159 a lot of the code. However, this work is 1599 00:56:54,160 --> 00:56:55,929 still to be done. This integration work 1600 00:56:55,930 --> 00:56:57,429 is actually one of the trickiest parts of 1601 00:56:57,430 --> 00:56:59,169 computer security to make sure that it's 1602 00:56:59,170 --> 00:57:01,119 actually usable and we haven't actually 1603 00:57:01,120 --> 00:57:01,959 done that yet. 1604 00:57:01,960 --> 00:57:03,459 The question of the second question is 1605 00:57:03,460 --> 00:57:05,679 how can we use that to do DNS? 1606 00:57:05,680 --> 00:57:08,079 So it's not a very good match for 1607 00:57:08,080 --> 00:57:10,419 DNS because in DNS, the 1608 00:57:10,420 --> 00:57:12,489 whole point is that you want everybody 1609 00:57:12,490 --> 00:57:15,099 to know the DNS 1610 00:57:15,100 --> 00:57:17,169 information, right? So it's probably a 1611 00:57:17,170 --> 00:57:19,359 better fit, for example, for 1612 00:57:19,360 --> 00:57:21,099 a short messaging service. 1613 00:57:21,100 --> 00:57:23,259 Right. You want Alice wants to tell 1614 00:57:23,260 --> 00:57:26,139 Bob in particular some small 1615 00:57:26,140 --> 00:57:28,059 amount of information, which would be the 1616 00:57:28,060 --> 00:57:30,129 auxiliary data in here. 1617 00:57:30,130 --> 00:57:32,259 So you can imagine DP five or 1618 00:57:32,260 --> 00:57:34,449 very similar protocol being used 1619 00:57:34,450 --> 00:57:37,149 for some kind of short messaging service 1620 00:57:37,150 --> 00:57:39,399 where Alice is sending 1621 00:57:39,400 --> 00:57:41,679 a particular message to 1622 00:57:41,680 --> 00:57:43,839 one or a small subset of 1623 00:57:43,840 --> 00:57:45,999 people, her friends in this example. 1624 00:57:46,000 --> 00:57:47,889 But DNS, you want to send it to 1625 00:57:47,890 --> 00:57:48,849 everybody. 1626 00:57:48,850 --> 00:57:51,159 And so I don't think that's a good fit 1627 00:57:51,160 --> 00:57:52,160 for this protocol. 1628 00:57:53,140 --> 00:57:55,779 OK, two minutes left, two questions. 1629 00:57:55,780 --> 00:57:57,759 Microphone number one, please. 1630 00:57:57,760 --> 00:57:59,979 In the protocol, A-list 1631 00:57:59,980 --> 00:58:02,859 stars are encrypted information with an 1632 00:58:02,860 --> 00:58:05,329 X, and then later on, Bob 1633 00:58:05,330 --> 00:58:08,019 queries the database for that same X.. 1634 00:58:08,020 --> 00:58:09,999 So what prevents the server from knowing 1635 00:58:10,000 --> 00:58:11,949 the relationship between Alice and Bob? 1636 00:58:11,950 --> 00:58:14,259 Because the lookup is done using private 1637 00:58:14,260 --> 00:58:15,729 information retrieval. 1638 00:58:15,730 --> 00:58:17,859 So Bob looks up 1639 00:58:17,860 --> 00:58:20,019 with X, but in a way 1640 00:58:20,020 --> 00:58:22,239 that doesn't reveal to the server what X 1641 00:58:22,240 --> 00:58:23,589 is. 1642 00:58:23,590 --> 00:58:24,999 All right. Right. 1643 00:58:25,000 --> 00:58:26,859 OK, so you're using the disputed model. 1644 00:58:26,860 --> 00:58:28,359 That's right. That's the magic. 1645 00:58:28,360 --> 00:58:30,639 OK, OK, microphone number 1646 00:58:30,640 --> 00:58:31,640 one again. 1647 00:58:32,990 --> 00:58:35,239 What happens if the database 1648 00:58:35,240 --> 00:58:36,199 are not synchronized? 1649 00:58:36,200 --> 00:58:38,029 For example, if they run out of sync for 1650 00:58:38,030 --> 00:58:40,729 one time and have some different 1651 00:58:40,730 --> 00:58:42,649 information about the same user? 1652 00:58:42,650 --> 00:58:44,179 Right. So that would be bad. 1653 00:58:45,620 --> 00:58:47,869 But it's not so bad 1654 00:58:47,870 --> 00:58:50,029 because as I said in the first 1655 00:58:50,030 --> 00:58:52,099 half, right at the end of the first half, 1656 00:58:52,100 --> 00:58:55,069 these pure protocols support robustness. 1657 00:58:55,070 --> 00:58:56,869 So if some of the servers are out of 1658 00:58:56,870 --> 00:58:58,849 sync, as long as not too many are out of 1659 00:58:58,850 --> 00:59:01,129 sync, no problem, because the robustness 1660 00:59:01,130 --> 00:59:03,379 properties of the peer protocol will 1661 00:59:03,380 --> 00:59:04,999 just think, oh, that server is giving me 1662 00:59:05,000 --> 00:59:06,379 the wrong data. 1663 00:59:06,380 --> 00:59:08,479 So as long as enough of the 1664 00:59:08,480 --> 00:59:11,299 servers agree, then the 1665 00:59:11,300 --> 00:59:13,369 the answer that the most 1666 00:59:13,370 --> 00:59:15,319 of the servers agree on will be the 1667 00:59:15,320 --> 00:59:16,349 answer returned. 1668 00:59:16,350 --> 00:59:18,529 OK, so it's the most it's 1669 00:59:18,530 --> 00:59:19,459 no value in between. 1670 00:59:19,460 --> 00:59:20,659 It's the most agreeing. 1671 00:59:20,660 --> 00:59:22,579 No, it's the most agreeing value. 1672 00:59:22,580 --> 00:59:23,580 Thank you. 1673 00:59:24,550 --> 00:59:26,859 OK, we have been asked to finish a second 1674 00:59:26,860 --> 00:59:29,079 time, so unfortunately, you have to close 1675 00:59:29,080 --> 00:59:30,689 the Q&A now. 1676 00:59:30,690 --> 00:59:32,289 Again, thank you very much for coming 1677 00:59:32,290 --> 00:59:34,119 here. Thank you very much. 1678 00:59:34,120 --> 00:59:35,120 And.