33 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
32 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
34 |
33 |
35 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
36 \begin{frame}[c] |
35 \begin{frame}[c] |
37 |
36 |
38 \begin{itemize} |
37 \begin{bubble}[10cm] |
39 \item Imagine you have an completely innocent email message, |
38 Imagine you have a completely innocent email message, like |
40 like birthday wishes to your grandmother? Why should you |
39 birthday wishes to your grandmother? Why should you still |
41 still encrypt this message and your grandmother take the |
40 encrypt this message and your grandmother take the effort to |
42 effort to decrypt it?\bigskip |
41 decrypt it? |
43 |
42 \end{bubble} |
44 \small |
43 |
|
44 \begin{itemize} |
|
45 \item \small |
45 (Hint: The answer has nothing to do with preserving the |
46 (Hint: The answer has nothing to do with preserving the |
46 privacy of your grandmother and nothing to do with |
47 privacy of your grandmother and nothing to do with |
47 keeping her birthday wishes super-secret. Also nothing to |
48 keeping her birthday wishes super-secret. Also nothing to |
48 do with you and grandmother testing the latest |
49 do with you and grandmother testing the latest |
49 encryption technology, nor just for the sake of it.) |
50 encryption technology, nor just for the sake of it.) |
54 |
55 |
55 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
56 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
56 \begin{frame}[c] |
57 \begin{frame}[c] |
57 |
58 |
58 \begin{center} |
59 \begin{center} |
59 \includegraphics[scale=0.6]{../pics/escher.jpg} |
60 \includegraphics[scale=0.6]{../pics/escher.jpg}\\ |
|
61 \footnotesize\mbox{M.C.Escher, Amazing World (from Gödel, Escher, Bach by D.Hofstadter)} |
60 \end{center} |
62 \end{center} |
61 |
63 |
62 \end{frame} |
64 \end{frame} |
63 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
65 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
64 |
66 |
65 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
67 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
66 \begin{frame}[c] |
68 \begin{frame}[c] |
67 \frametitle{Interlock Protocol} |
69 \frametitle{Interlock Protocol} |
68 |
70 |
69 Protocol between a car \bl{$C$} and a key transponder \bl{$T$}:\bigskip |
71 \mbox{A Protocol between a car \bl{$C$} and a key transponder \bl{$T$}:}\bigskip |
70 |
72 |
71 \begin{enumerate} |
73 \begin{enumerate} |
72 \item \bl{$C$} generates a random number \bl{$N$} |
74 \item \bl{$C$} generates a random number \bl{$N$} |
73 \item \bl{$C$} calculates \bl{$(F,G) = \{N\}_K$} |
75 \item \bl{$C$} calculates \bl{$(F,G) = \{N\}_K$} |
74 \item \bl{$C \to T$}: \bl{$N, F$}\bigskip |
76 \item \bl{$C \to T$}: \bl{$N, F$}\bigskip |
83 |
85 |
84 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
86 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
85 \begin{frame}[c] |
87 \begin{frame}[c] |
86 \frametitle{Zero-Knowledge Proofs} |
88 \frametitle{Zero-Knowledge Proofs} |
87 |
89 |
88 Essentially every NP-problem can be used for ZKPs\bigskip |
90 \begin{itemize} |
89 |
91 \item Essentially every NP-problem can be used for ZKPs\bigskip |
90 \begin{itemize} |
92 |
91 \item modular logarithms: Alice chooses public \bl{$A$}, \bl{$B$}, \bl{$p$}; and private \bl{$x$} |
93 \item modular logarithms: Alice chooses public \bl{$A$}, \bl{$B$}, \bl{$p$}; and private \bl{$x$} |
92 |
94 |
93 \begin{center} |
95 \begin{center} |
94 \large\bl{$A^x \equiv B\; mod\; p$} |
96 \large\bl{$A^x \equiv B\; mod\; p$} |
95 \end{center} |
97 \end{center} |
115 |
117 |
116 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
117 \begin{frame}[c] |
119 \begin{frame}[c] |
118 \frametitle{Modular Logarithm} |
120 \frametitle{Modular Logarithm} |
119 |
121 |
120 Ordinary, non-modular logarithms: |
122 Ordinary, \emph{non}-modular logarithms: |
121 |
123 |
122 \begin{center}\large |
124 \begin{center}\large |
123 \begin{tabular}{ll} |
125 \begin{tabular}{ll} |
124 & \bl{$10^? = 17$}\bigskip\\\pause |
126 & \bl{$10^? = 17$}\bigskip\\\pause |
125 $\Rightarrow$ & \bl{$log_{10} 17 = 1.2304489\ldots$}\\\pause |
127 $\Rightarrow$ & \bl{$log_{10} 17 = 1.2304489\ldots$}\\\pause |
126 $\Rightarrow$ & \bl{$10^{1.2304489} = 16.999999$}\\\pause |
128 $\Rightarrow$ & \bl{$10^{1.2304489} = 16.999999$}\\\pause |
127 \end{tabular} |
129 \end{tabular} |
128 \end{center} |
130 \end{center} |
129 |
131 |
130 Conclusion: \bl{$1.2304489$} is very close to the \emph{true} |
132 Conclusion: \bl{$1.2304489$} is very close to the \emph{true} |
131 solution |
133 solution, slightly low |
132 |
134 |
133 \end{frame} |
135 \end{frame} |
134 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
136 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
135 |
137 |
136 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
138 \frametitle{Modular Logarithm} |
140 \frametitle{Modular Logarithm} |
139 |
141 |
140 In contrast, modular logarithms behave much differently: |
142 In contrast, modular logarithms behave much differently: |
141 |
143 |
142 \begin{center}\large |
144 \begin{center}\large |
143 \bl{$2^? \equiv 88319671\;\; mod\;\; 97330327$}\bigskip\\\pause |
145 \bl{$2^? \equiv 88319671\;\; mod\;\; 97330327$}\bigskip |
144 \end{center}\pause |
146 \end{center}\pause |
145 |
147 |
146 Lets say I found \bl{$28305819$}\ldots I try |
148 Lets say I `found' \bl{$28305819$} and I try |
147 |
149 |
148 \begin{center}\large |
150 \begin{center}\large |
149 \bl{$2^{28305819} \equiv 88032151\;\; mod\;\; 97330327$}\bigskip\\\pause |
151 \bl{$2^{28305819} \equiv 88032151\;\; mod\;\; 97330327$}\bigskip |
150 \end{center}\pause |
152 \end{center}\pause |
151 |
153 |
152 I could be tempted to try \bl{$28305820$}\ldots\pause |
154 Slightly lower. I might be tempted to try \bl{$28305820$}\ldots\pause |
153 but the real\\ |
155 but the real answer is \bl{12314}. |
154 \mbox{}\hfill answer is \bl{12314}. |
|
155 |
156 |
156 \end{frame} |
157 \end{frame} |
157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
158 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
158 |
159 |
159 |
160 |
261 In order to cheat, Alice has to guess all bits in advance. She |
262 In order to cheat, Alice has to guess all bits in advance. She |
262 has only \bl{$\frac{1}{2}^z$} chance of doing so.\bigskip\\ |
263 has only \bl{$\frac{1}{2}^z$} chance of doing so.\bigskip\\ |
263 |
264 |
264 \end{frame} |
265 \end{frame} |
265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
266 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
267 |
|
268 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
269 \begin{frame}[c] |
|
270 \frametitle{How can Alice cheat?} |
|
271 |
|
272 \begin{itemize} |
|
273 \item Alice needs to coordinate what she sends as \bl{$h_i$} |
|
274 (in step 2), \bl{$s_i$} (in step 4) and |
|
275 \bl{$s_{z+1}$} (in step 6).\pause\bigskip |
|
276 |
|
277 \item for \bl{$s_{z+1}$} she solves the easy |
|
278 \begin{center} |
|
279 \bl{$A^{s_{z+1}} \equiv B * y \;mod\;p$} |
|
280 \end{center} |
|
281 |
|
282 for \bl{$y$}.\pause |
|
283 \item if she can guess \bl{$j$} (first \bl{$1$}) then |
|
284 she sends \bl{$y$} as \bl{$h_j$} |
|
285 and \bl{$0$} as \bl{$s_j$}.\pause |
|
286 |
|
287 \item however she does not know \bl{$r_j$} because she would |
|
288 need to solve |
|
289 \begin{center} |
|
290 \bl{$A^{r_j} \equiv y \;mod\;p$} |
|
291 \end{center} |
|
292 \end{itemize} |
|
293 |
|
294 \end{frame} |
|
295 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
296 |
|
297 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
298 \begin{frame}[c] |
|
299 \frametitle{How can Alice cheat?} |
|
300 |
|
301 \begin{itemize} |
|
302 \item Alice still needs to decide on the other \bl{$h_i$} and |
|
303 \bl{$s_i$}. They have to satisfy the test: |
|
304 |
|
305 \[\bl{A^{\alert{s_i}} \stackrel{?}{\equiv} \alert{h_i} * h_j^{-1} \;mod\; p}\] |
|
306 \pause |
|
307 |
|
308 \item Lets say she choses the \bl{$s_i$} at random, then she |
|
309 needs to solve |
|
310 |
|
311 \[\bl{A^{s_i} \equiv z * h_j^{-1} \;mod\; p}\] |
|
312 |
|
313 for \bl{$z$}.\pause{} It still does not allow us to find out |
|
314 the \bl{$r_i$}. Let us call an \bl{$h_i$} calculated in this |
|
315 way as \alert{bogus}. |
|
316 |
|
317 \end{itemize} |
|
318 |
|
319 \end{frame} |
|
320 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
321 |
|
322 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
323 \begin{frame}[t] |
|
324 \frametitle{How can Alice cheat?} |
|
325 |
|
326 \begin{itemize} |
|
327 \item Alice has to produce bogus \bl{$h_i$} for all bits that |
|
328 are going to be \bl{$1$} in advance.\bigskip\pause |
|
329 |
|
330 \item Lets say \bl{$b_i = 1$} where Alice guessed \bl{$0$}: |
|
331 She already has sent \bl{$h_i$} and \bl{$h_j$} and now must find a |
|
332 correct \bl{$s_i$} (which she chose at random at first) |
|
333 |
|
334 \[\bl{A^{s_i} \equiv h_i * h_j^{-1} \;mod\; p}\] |
|
335 |
|
336 If she knew \bl{$r_i$} and \bl{$r_j$}, then easy: |
|
337 \bl{$s_i = r_i - r_j$}. But she does not. So she will be found |
|
338 out. |
|
339 \end{itemize} |
|
340 |
|
341 \end{frame} |
|
342 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
343 |
|
344 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
345 \begin{frame}[t] |
|
346 \frametitle{How can Alice cheat?} |
|
347 |
|
348 \begin{itemize} |
|
349 \item Alice has to produce bogus \bl{$h_i$} for all bits that |
|
350 are going to be \bl{$1$} in advance.\bigskip |
|
351 |
|
352 \item Lets say \bl{$b_i = 0$} where Alice guessed \bl{$1$}: |
|
353 She has to send an \bl{$s_i$} so that |
|
354 |
|
355 \[\bl{A^{s_i} \equiv h_i\;mod\;p}\] |
|
356 |
|
357 She does not know \bl{$r_i$}. So this is too hard and |
|
358 she will be found out. |
|
359 \end{itemize} |
|
360 |
|
361 \end{frame} |
|
362 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
363 |
266 |
364 |
267 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
365 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
268 \tikzset{alt/.code args={<#1>#2#3#4}{% |
366 \tikzset{alt/.code args={<#1>#2#3#4}{% |
269 \alt<#1>{\pgfkeysalso{#2}}{\pgfkeysalso{#3}} % \pgfkeysalso doesn't change the path |
367 \alt<#1>{\pgfkeysalso{#2}}{\pgfkeysalso{#3}} % \pgfkeysalso doesn't change the path |
270 }} |
368 }} |
372 \end{frame} |
470 \end{frame} |
373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
471 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
374 |
472 |
375 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
473 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
376 \begin{frame}[c] |
474 \begin{frame}[c] |
377 |
475 \frametitle{Coming Back To\ldots} |
378 \begin{itemize} |
476 |
379 \item Imagine you have an completely innocent email message, |
477 \begin{bubble}[10cm] |
380 like birthday wishes to your grandmother? Why should you |
478 Imagine you have an completely innocent email message, like |
381 still encrypt this message and your grandmother take the |
479 birthday wishes to your grandmother? Why should you still |
382 effort to decrypt it?\bigskip |
480 encrypt this message and your grandmother take the effort to |
383 |
481 decrypt it? |
384 \small |
482 \end{bubble}\pause |
385 (Hint: The answer has nothing to do with preserving the |
483 |
386 privacy of your grandmother and nothing to do with |
484 \begin{itemize} |
387 keeping her birthday wishes super-secret. Also nothing to |
485 \item \small |
388 do with you and grandmother testing the latest |
486 Bruce Schneier\\ |
389 encryption technology, nor just for the sake of it.) |
487 NSA Surveillance and What To Do About It\\ |
|
488 \url{https://www.youtube.com/watch?v=QXtS6UcdOMs} |
390 \end{itemize} |
489 \end{itemize} |
391 |
490 |
392 \end{frame} |
491 \end{frame} |
393 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
492 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
394 |
493 |
|
494 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
495 \begin{frame}[c] |
|
496 \small |
|
497 \begin{bubble}[10cm] |
|
498 Terrorists use encrypted mobile-messaging apps. The spy |
|
499 agencies argue that although they can follow the conversations |
|
500 on Twitter, they ``go dark'' on the encrypted message apps. To |
|
501 counter this ``going-dark problem'', the spy agencies push for |
|
502 the implementation of back-doors in iMessage and Facebook and |
|
503 Skype and everything else UK or US-made, which they can use |
|
504 eavesdrop on conversations without the conversants' knowledge |
|
505 or consent. |
|
506 |
|
507 \end{bubble} |
|
508 |
|
509 \begin{itemize} |
|
510 \item What is the fallacy in the spy agencies going-dark |
|
511 argument? |
|
512 \end{itemize} |
|
513 |
|
514 \end{frame} |
|
515 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
395 |
516 |
396 \end{document} |
517 \end{document} |
397 |
518 |
398 |
519 |
399 %%% Local Variables: |
520 %%% Local Variables: |