|
1 \documentclass[dvipsnames,14pt,t]{beamer} |
|
2 \usepackage{../slides} |
|
3 \usepackage{../graphics} |
|
4 |
|
5 \setmonofont[Scale=.88]{Consolas} |
|
6 \newfontfamily{\consolas}{Consolas} |
|
7 |
|
8 \hfuzz=220pt |
|
9 |
|
10 % beamer stuff |
|
11 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
|
12 \renewcommand{\slidecaption}{SEN 06, King's College London} |
|
13 |
|
14 \begin{document} |
|
15 |
|
16 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
17 \begin{frame}[t] |
|
18 \frametitle{% |
|
19 \begin{tabular}{@ {}c@ {}} |
|
20 \\ |
|
21 \LARGE Security Engineering (6)\\[-3mm] |
|
22 \end{tabular}}\bigskip\bigskip\bigskip |
|
23 |
|
24 \normalsize |
|
25 \begin{center} |
|
26 \begin{tabular}{ll} |
|
27 Email: & christian.urban at kcl.ac.uk\\ |
|
28 Office: & S1.27 (1st floor Strand Building)\\ |
|
29 Slides: & KEATS (also homework is there)\\ |
|
30 \end{tabular} |
|
31 \end{center} |
|
32 |
|
33 \end{frame} |
|
34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
35 |
|
36 |
|
37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
38 \begin{frame}[c] |
|
39 \frametitle{Hashes for History} |
|
40 |
|
41 Q: What is the hash for? |
|
42 |
|
43 \begin{center} |
|
44 \includegraphics[scale=0.4]{../pics/Dismantling_Megamos_Crypto.png} |
|
45 \end{center} |
|
46 |
|
47 \end{frame} |
|
48 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
49 |
|
50 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
51 \begin{frame}[t] |
|
52 \frametitle{Checking Solutions} |
|
53 |
|
54 How can you check somebody's solution without revealing the solution?\pause\bigskip |
|
55 |
|
56 Alice and Bob solve crosswords. Alice knows the answer for 21D (folio) but doesn't |
|
57 want to tell Bob.\medskip |
|
58 |
|
59 You use an English dictionary: |
|
60 |
|
61 \begin{itemize} |
|
62 \item folio \onslide<4->{$\stackrel{1}{\rightarrow}$ individual } |
|
63 \onslide<5->{$\stackrel{2}{\rightarrow}$ human} |
|
64 \onslide<6->{$\stackrel{3}{\rightarrow}$ or \ldots} |
|
65 \only<3>{ |
|
66 \begin{quote} |
|
67 ``an \alert{individual} leaf of paper or parchment, either loose as one of a series or |
|
68 forming part of a bound volume, which is numbered on the recto or front side only.'' |
|
69 \end{quote}} |
|
70 \only<4>{ |
|
71 \begin{quote} |
|
72 ``a single \alert{human} being as distinct from a group'' |
|
73 \end{quote}} |
|
74 \only<5>{ |
|
75 \begin{quote} |
|
76 ``relating to \alert{or} characteristic of humankind'' |
|
77 \end{quote}} |
|
78 \end{itemize}\bigskip\bigskip |
|
79 |
|
80 \only<7->{ |
|
81 this is essentially a hash function...but Bob can only check once he has also found the solution |
|
82 } |
|
83 |
|
84 \end{frame} |
|
85 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
86 |
|
87 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
88 \begin{frame}[c] |
|
89 \frametitle{Zero-Knowledge Proofs} |
|
90 |
|
91 Two remarkable properties of \alert{Zero-Knowledge |
|
92 Proofs}:\bigskip |
|
93 |
|
94 \begin{itemize} |
|
95 |
|
96 \item Alice only reveals the fact that she knows a secret, not |
|
97 the secret itself (meaning she can convince Bob that she |
|
98 knows the secret, but does not give it to him).\bigskip |
|
99 \item Having been convinced, Bob cannot use the evidence in |
|
100 order to convince Carol that Alice knows the secret. |
|
101 |
|
102 \end{itemize} |
|
103 |
|
104 \end{frame} |
|
105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
106 |
|
107 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
108 \begin{frame}[c] |
|
109 \frametitle{Interactive Protocols} |
|
110 |
|
111 Q: How to cut a cake into two equal slices? |
|
112 |
|
113 \begin{center} |
|
114 \includegraphics[scale=0.15]{../pics/cake.jpg} |
|
115 \end{center}\pause\bigskip |
|
116 |
|
117 \small |
|
118 Solves the problem of communication when both parties |
|
119 distrust each other. |
|
120 |
|
121 \end{frame} |
|
122 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
123 |
|
124 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
125 \begin{frame}[t] |
|
126 \frametitle{The Idea} |
|
127 |
|
128 \begin{center} |
|
129 \begin{tabular}{l@{\hspace{10mm}}r} |
|
130 \\[-10mm] |
|
131 \raisebox{10mm}{\large 1.} & \includegraphics[scale=0.1]{../pics/alibaba1.png}\\ |
|
132 \raisebox{10mm}{\large 2.} & \includegraphics[scale=0.1]{../pics/alibaba2.png}\\ |
|
133 \raisebox{10mm}{\large 3.} & \includegraphics[scale=0.1]{../pics/alibaba3.png} |
|
134 \end{tabular} |
|
135 \end{center} |
|
136 |
|
137 \begin{textblock}{7}(1,2) |
|
138 The Alibaba cave protocol: |
|
139 \end{textblock} |
|
140 |
|
141 \small |
|
142 \only<2>{ |
|
143 \begin{textblock}{12}(2,13.3) |
|
144 Even if Bob has a hidden camera, a recording will not be |
|
145 convincing to anyone else (Alice and Bob could have made it |
|
146 all up). |
|
147 \end{textblock}} |
|
148 \only<3>{ |
|
149 \begin{textblock}{12}(2,13.3) |
|
150 Even worse, an observer present at the experiment would not be |
|
151 convinced. |
|
152 \end{textblock}} |
|
153 |
|
154 \end{frame} |
|
155 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
156 |
|
157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
158 \begin{frame}[c] |
|
159 \frametitle{Applications of ZKPs} |
|
160 |
|
161 \begin{itemize} |
|
162 \item authentication, where one party wants to prove its |
|
163 identity to a second party via some secret information, |
|
164 but doesn't want the second party to learn anything |
|
165 about this secret\bigskip |
|
166 \item to enforce honest behaviour while maintaining privacy: |
|
167 the idea is to force users to prove, using a |
|
168 zero-knowledge proof, that their behaviour is correct |
|
169 according to the protocol |
|
170 \end{itemize}\bigskip |
|
171 |
|
172 \small |
|
173 digital currencies, smart cards, id cards |
|
174 \end{frame} |
|
175 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
176 |
|
177 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
178 \mode<presentation>{ |
|
179 \begin{frame}[c] |
|
180 \frametitle{Central Properties} |
|
181 |
|
182 Zero-knowledge proof protocols should satisfy:\bigskip |
|
183 |
|
184 \begin{itemize} |
|
185 \item \alert{\bf Completeness} If Alice knows the secret, Bob |
|
186 accepts Alice's ``proof'' for sure.\bigskip |
|
187 \item \alert{\bf Soundness} If Alice does not know the secret, |
|
188 Bob accepts her ``proof'' with a very small probability. |
|
189 |
|
190 \item \alert{\bf Zero-Knowledge} Even if Bob accepts |
|
191 the proof by Alice, he cannot convince anybody else. |
|
192 |
|
193 \end{itemize} |
|
194 \end{frame}} |
|
195 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
196 |
|
197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
198 \begin{frame}[c] |
|
199 \frametitle{Graph Isomorphism} |
|
200 \mbox{}\\[-20mm]\mbox{} |
|
201 |
|
202 \begin{center} |
|
203 \begin{tabular}{@{}ccc} |
|
204 \raisebox{-18mm}{\includegraphics[scale=0.4]{../pics/simple.png}} & |
|
205 \raisebox{-18mm}{\includegraphics[scale=0.4]{../pics/simple-b.png}}& |
|
206 |
|
207 \footnotesize |
|
208 \begin{tabular}{rl} |
|
209 Graph A & Graph B\\ |
|
210 Graph $G_1$ & Graph $G_2$\\ |
|
211 a & 1\\ |
|
212 b & 6\\ |
|
213 c & 8\\ |
|
214 d & 3\\ |
|
215 g & 5\\ |
|
216 h & 2\\ |
|
217 i & 4\\ |
|
218 j & 7\\ |
|
219 \end{tabular} |
|
220 \end{tabular} |
|
221 \end{center} |
|
222 |
|
223 Finding an isomorphism between two graphs is an NP problem. |
|
224 |
|
225 \end{frame} |
|
226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
227 |
|
228 |
|
229 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
230 \begin{frame}[c] |
|
231 \begin{center} |
|
232 \includegraphics[scale=0.8]{../pics/graphs.png} |
|
233 \end{center} |
|
234 |
|
235 Creating a new isomorphic graph is easy; finding an |
|
236 isomorphism is hard; checking an isomorphism is easy again |
|
237 |
|
238 \end{frame} |
|
239 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
240 |
|
241 |
|
242 |
|
243 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
244 \begin{frame}[c] |
|
245 \frametitle{\Large Graph Isomorphism Protocol} |
|
246 |
|
247 Alice starts with knowing an isomorphism \bl{$\sigma$} between graphs \bl{$G_1$} and \bl{$G_2$}\medskip |
|
248 |
|
249 \begin{enumerate} |
|
250 \item Alice generates an isomorphic graph \bl{$H$} which she sends to Bob |
|
251 \item Bob asks either for an isomorphism between \bl{$G_1$} and \bl{$H$}, or |
|
252 \bl{$G_2$} and \bl{$H$} |
|
253 \item Alice and Bob repeat this procedure \bl{$n$} times |
|
254 \end{enumerate}\pause |
|
255 |
|
256 these are called commitment algorithms |
|
257 |
|
258 \end{frame} |
|
259 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
260 |
|
261 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
262 \begin{frame}[c] |
|
263 \frametitle{\Large Graph Isomorphism Protocol (2)} |
|
264 |
|
265 If Alice knows the isomorphism, she can always calculate |
|
266 \bl{$\sigma$}.\bigskip |
|
267 |
|
268 If she doesn't, she can only correctly respond if Bob's choice |
|
269 of index is the same as the one she used to form \bl{$H$}. The |
|
270 probability of this happening is \bl{$\frac{1}{2}$}, so after |
|
271 \bl{$n$} rounds the probability of her always responding |
|
272 correctly is only \bl{$\frac{1}{2}^n$}. |
|
273 |
|
274 \end{frame} |
|
275 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
276 |
|
277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
278 \begin{frame}[t] |
|
279 \frametitle{Plot of $\frac{1}{2}^n$} |
|
280 |
|
281 \begin{center} |
|
282 \begin{tikzpicture} |
|
283 \begin{axis}[ |
|
284 enlargelimits=true, |
|
285 xtick={0,1,...,10}, |
|
286 xmax=11, |
|
287 ymax=1.1, |
|
288 ytick={0,0.1,...,1.1}, |
|
289 scaled ticks=false, |
|
290 axis lines=left, |
|
291 width=11cm, |
|
292 height=7cm] |
|
293 \addplot[blue,mark=*, mark options={fill=white}] |
|
294 coordinates { |
|
295 (0, 1) (1, 0.5) (2, 0.25) (3, 0.125) |
|
296 (4, 0.0625) (5, 0.03125) (6, 0.015625) |
|
297 (7, 0.0078125) (8, 0.00390625) |
|
298 (9, 0.001953125) (10, 0.0009765625) |
|
299 }; |
|
300 \end{axis} |
|
301 \end{tikzpicture} |
|
302 \end{center} |
|
303 |
|
304 \end{frame} |
|
305 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
306 |
|
307 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
308 \begin{frame}[c] |
|
309 \frametitle{\Large Graph Isomorphism Protocol (3)} |
|
310 |
|
311 Why is the GI-protocol zero-knowledge?\bigskip\pause |
|
312 |
|
313 A: We can generate a fake transcript of a conversation, which |
|
314 cannot be distinguished from a ``real'' conversation.\bigskip |
|
315 |
|
316 Anything Bob can compute using the information obtained from |
|
317 the transcript can be computed using only a forged transcript |
|
318 and therefore participation in such a communication does not |
|
319 increase Bob's capability to perform any computation. |
|
320 |
|
321 \end{frame} |
|
322 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
323 |
|
324 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
325 \begin{frame}[c] |
|
326 \frametitle{Non-Interactive ZKPs} |
|
327 |
|
328 This is amazing: This can all be done ``offline'': |
|
329 \bigskip |
|
330 |
|
331 Alice can publish some data that contains no data about her |
|
332 secret, but this data can be used to convince anyone of the |
|
333 secret's existence (whether Alice knows it, must be |
|
334 established my other means). |
|
335 |
|
336 \end{frame} |
|
337 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
338 |
|
339 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
340 \begin{frame}[c] |
|
341 \frametitle{Non-Interactive ZKPs (2)} |
|
342 |
|
343 Alice starts with knowing an isomorphism \bl{$\sigma$} between |
|
344 graphs \bl{$G_1$} and \bl{$G_2$}\medskip |
|
345 |
|
346 \begin{enumerate} |
|
347 \item Alice generates \bl{$n$} isomorphic graphs |
|
348 \bl{$H_{1..n}$} which she makes public |
|
349 \item she feeds the \bl{$H_{1..n}$} into a hashing function |
|
350 (she has no control over what the output will be) |
|
351 \item Alice takes the first \bl{$n$} bits of the output: |
|
352 whenever output is \bl{$0$}, she shows an isomorphism |
|
353 with \bl{$G_1$} ; for \bl{$1$} she shows an isomorphism |
|
354 with \bl{$G_2$} |
|
355 \end{enumerate} |
|
356 |
|
357 \end{frame} |
|
358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
359 |
|
360 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
361 \begin{frame}[c] |
|
362 \frametitle{Problems of ZKPs} |
|
363 |
|
364 \begin{itemize} |
|
365 \item ``grand chess master problem''\\ (person in the |
|
366 middle again)\bigskip |
|
367 |
|
368 \item Alice can have multiple identities; once she committed a |
|
369 fraud with one, she stops using one |
|
370 \end{itemize} |
|
371 |
|
372 \end{frame} |
|
373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
374 |
|
375 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
376 \mode<presentation>{ |
|
377 \begin{frame}[c] |
|
378 \frametitle{Other Methods for ZKPs} |
|
379 |
|
380 Essentially every NP-problem can be used for ZKPs |
|
381 |
|
382 \begin{itemize} |
|
383 \item modular logarithms: Alice chooses public \bl{$A$}, \bl{$B$}, \bl{$p$}; and private \bl{$x$} |
|
384 |
|
385 \begin{center} |
|
386 \bl{$A^x \equiv B\; mod\; p$} |
|
387 \end{center} |
|
388 \end{itemize} |
|
389 |
|
390 \end{frame}} |
|
391 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
392 |
|
393 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
394 \mode<presentation>{ |
|
395 \begin{frame}[c] |
|
396 \frametitle{Commitment Stage} |
|
397 |
|
398 \begin{enumerate} |
|
399 \item Alice generates \bl{$z$} random numbers \bl{$r_1$}, ..., \bl{$r_z$}, all less than \bl{$p - 1$}. |
|
400 \item Alice sends Bob for all \bl{$1..z$} |
|
401 \begin{center} |
|
402 \bl{$h_i = A^{r_i} \;mod\; p$} |
|
403 \end{center} |
|
404 \item Bob generates random bits \bl{$b_1$}, ..., \bl{$b_z$} by flipping a coin |
|
405 \item For each bit \bl{$b_i$}, Alice sends Bob an \bl{$s_i$} where |
|
406 |
|
407 \begin{center} |
|
408 \begin{tabular}{ll} |
|
409 \bl{$b_i = 0$}: & \bl{$s_i = r_i$}\\ |
|
410 \bl{$b_i = 1$}: & \bl{$s_i = (r_i - r_j) \;mod\; (p -1)$}\\ |
|
411 \end{tabular} |
|
412 \end{center} |
|
413 where \bl{$r_j$} is the lowest \bl{$j$} where \bl{$b_j = 1$} |
|
414 |
|
415 \end{enumerate} |
|
416 |
|
417 \end{frame}} |
|
418 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
419 |
|
420 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
421 \mode<presentation>{ |
|
422 \begin{frame}[c] |
|
423 \frametitle{Confirmation Stage} |
|
424 |
|
425 \begin{enumerate} |
|
426 \item For each \bl{$b_i$} Bob checks whether \bl{$s_i$} conforms to the protocol |
|
427 |
|
428 \begin{center} |
|
429 \begin{tabular}{ll} |
|
430 \bl{$b_i = 0$}: & \bl{$A^{s_i} \equiv h_i\;mod\;p$}\\ |
|
431 \bl{$b_i = 1$}: & \bl{$A^{s_i} \equiv h_i * h_j^{-1} \;mod\; p$}\\ |
|
432 \end{tabular} |
|
433 \end{center}\bigskip |
|
434 |
|
435 Bob was sent |
|
436 |
|
437 \begin{center} |
|
438 \bl{$r_j - r_j$}, \bl{$r_m - r_j$}, \ldots, \bl{$r_p - r_j \;mod \;p - 1$} |
|
439 \end{center} |
|
440 |
|
441 where the corresponding bits were |
|
442 \bl{$1$}; Bob does not know \bl{$r_j$}, he does not know any \bl{$r_i$} where the bit was \bl{$1$} |
|
443 \end{enumerate} |
|
444 |
|
445 \end{frame}} |
|
446 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
447 |
|
448 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
449 \begin{frame}[c] |
|
450 \frametitle{Proving Stage} |
|
451 |
|
452 \begin{enumerate} |
|
453 \item Alice proves she knows \bl{$x$}, the discrete log of \bl{$B$}\\ |
|
454 she sends |
|
455 |
|
456 \begin{center} |
|
457 \bl{$s_{z+1} = (x - r_j)$} |
|
458 \end{center} |
|
459 |
|
460 \item Bob confirms |
|
461 |
|
462 \begin{center} |
|
463 \bl{$A^{s_{z+1}} \equiv B * h_j^{-1} \;mod \; p$} |
|
464 \end{center} |
|
465 \end{enumerate}\bigskip\pause |
|
466 |
|
467 In order to cheat, Alice has to guess all bits in advance. She |
|
468 has only \bl{$\frac{1}{2}^z$} chance of doing so.\bigskip\\ |
|
469 |
|
470 \small\hspace{7mm} |
|
471 \textcolor{gray}{(explanation $\rightarrow$ \url{http://goo.gl/irL9GK})} |
|
472 |
|
473 \end{frame} |
|
474 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
475 |
|
476 |
|
477 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
478 \begin{frame}[c] |
|
479 \frametitle{Take Home Points} |
|
480 |
|
481 \begin{itemize} |
|
482 \item this is pretty old work (in theory); seems |
|
483 little used in practice (surprising)\bigskip |
|
484 |
|
485 \item for use in privacy, the incentives are |
|
486 not yet right\bigskip |
|
487 |
|
488 \item most likely applied with digital cash |
|
489 (Bitcoins are not yet good enough, Zerocoins) |
|
490 |
|
491 \end{itemize} |
|
492 |
|
493 \end{frame} |
|
494 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
495 |
|
496 |
|
497 |
|
498 |
|
499 \end{document} |
|
500 |
|
501 %%% Local Variables: |
|
502 %%% mode: latex |
|
503 %%% TeX-master: t |
|
504 %%% End: |
|
505 |