65 \end{center} |
65 \end{center} |
66 |
66 |
67 \end{frame}} |
67 \end{frame}} |
68 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
68 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
69 |
69 |
|
70 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
71 \mode<presentation>{ |
|
72 \begin{frame}[c] |
|
73 \frametitle{Review: Proofs} |
|
74 |
|
75 Modify the formula |
|
76 \begin{center} |
|
77 \begin{tabular}{l} |
|
78 \bl{$P\;\textit{controls}\;\textit{Permitted}(O, \textit{write})$}\\ |
|
79 \end{tabular} |
|
80 \end{center} |
|
81 using security levels so that it satisfies the {\it write rule} from the {\it |
|
82 Bell-LaPadula} access policy.\bigskip |
|
83 |
|
84 Do the same again, but satisfy the {\it write rule} |
|
85 from the {\it Biba} access policy. |
|
86 |
|
87 \end{frame}} |
|
88 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
89 |
|
90 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
91 \mode<presentation>{ |
|
92 \begin{frame}[c] |
|
93 \frametitle{Review: Proofs} |
|
94 |
|
95 Assume two security levels \bl{$\textit{S}$} and \bl{$\textit{TS}$}, |
|
96 which are ordered so that \bl{$slev(\textit{S}) < slev(\textit{TS})$}. |
|
97 Assume further the substitution rules |
|
98 \begin{center} |
|
99 \bl{\begin{tabular}{@{}c@{}} |
|
100 $\Gamma \vdash slev(P) = l_1$ \hspace{2mm} $\Gamma \vdash slev(Q) = l_2$ |
|
101 \hspace{2mm} $\Gamma \vdash l_1 < l_2$\\\hline |
|
102 $\Gamma \vdash slev(P) < slev(Q)$ |
|
103 \end{tabular}} |
|
104 \end{center} |
|
105 |
|
106 \begin{center} |
|
107 \bl{\begin{tabular}{c} |
|
108 $\Gamma \vdash slev(P) = l$ \hspace{4mm} $\Gamma \vdash slev(Q) = l$\\\hline |
|
109 $\Gamma \vdash slev(P) = slev(Q)$ |
|
110 \end{tabular}} |
|
111 \end{center} |
|
112 |
|
113 |
|
114 \end{frame}} |
|
115 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
116 |
|
117 |
|
118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
119 \mode<presentation>{ |
|
120 \begin{frame}[c] |
|
121 \frametitle{Review: Proofs}\small |
|
122 |
|
123 Let \bl{$\Gamma$} be the set containing the following six formulas |
|
124 \begin{center} |
|
125 \bl{\begin{tabular}{@{}l@{}} |
|
126 $slev(\textit{S}) < slev(\textit{TS})$\smallskip\\ |
|
127 $slev(\textit{Agent}) = slev(\textit{TS})$\smallskip\\ |
|
128 $slev(\textit{File}_1) = slev(\textit{S})$\smallskip\\ |
|
129 $slev(\textit{File}_2) = slev(\textit{TS})$\smallskip\\ |
|
130 $\forall O.\;slev(O) < slev(\textit{Agent}) \Rightarrow$\\ |
|
131 \hspace{30mm}$(\textit{Agent}\;\textit{controls}\;\textit{Permitted}(O, \textit{read}))$\smallskip\\ |
|
132 $\forall O.\;slev(O) = slev(\textit{Agent}) \Rightarrow$\\ |
|
133 \hspace{30mm}$(\textit{Agent}\;\textit{controls}\;\textit{Permitted}(O, \textit{read}))$\\ |
|
134 \end{tabular}} |
|
135 \end{center} |
|
136 Using the inference rules of access-control logic and the substitution rules shown above, |
|
137 give proofs for the two judgements |
|
138 \begin{center} |
|
139 \bl{\begin{tabular}{@{}l@{}} |
|
140 $\Gamma \vdash |
|
141 (\textit{Agent}\;\textit{says}\;\textit{Permitted}(\textit{File}_1, |
|
142 \textit{read})) \Rightarrow$\\ |
|
143 \hspace{50mm}$\textit{Permitted}(\textit{File}_1, \textit{read})$\\ |
|
144 \end{tabular}} |
|
145 \end{center} |
|
146 |
|
147 |
|
148 \end{frame}} |
|
149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
150 |
70 |
151 |
71 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
152 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
72 \mode<presentation>{ |
153 \mode<presentation>{ |
73 \begin{frame}[t] |
154 \begin{frame}[t] |
74 \frametitle{Checking Solutions} |
155 \frametitle{Checking Solutions} |
150 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
231 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
151 |
232 |
152 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
233 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
153 \mode<presentation>{ |
234 \mode<presentation>{ |
154 \begin{frame}[c] |
235 \begin{frame}[c] |
|
236 \frametitle{Applications of ZKPs} |
|
237 |
|
238 \begin{itemize} |
|
239 \item authentication, where one party wants to prove its identity to a |
|
240 second party via some secret information, but doesn't want the second |
|
241 party to learn anything about this secret\bigskip |
|
242 \item to enforce honest behaviour while maintaining privacy: the idea is to |
|
243 force a user to prove, using a zero-knowledge proof, that its behaviour is |
|
244 correct according to the protocol |
|
245 \end{itemize} |
|
246 \end{frame}} |
|
247 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
248 |
|
249 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
250 \mode<presentation>{ |
|
251 \begin{frame}[c] |
|
252 \frametitle{Central Properties} |
|
253 |
|
254 Zero-knowledge proof protocols should satisfy:\bigskip |
|
255 |
|
256 \begin{itemize} |
|
257 \item \alert{\bf Completeness} If Alice knows the secret, Bob accepts Alice ``proof'' for sure.\bigskip |
|
258 \item \alert{\bf Soundness} If Alice does not know the secret, Bob accepts her ``proof'' with a very |
|
259 small probability. |
|
260 \end{itemize} |
|
261 \end{frame}} |
|
262 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
263 |
|
264 |
|
265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
266 \mode<presentation>{ |
|
267 \begin{frame}[c] |
155 \frametitle{Graph Isomorphism} |
268 \frametitle{Graph Isomorphism} |
156 |
269 |
157 \begin{center} |
270 \begin{center} |
158 \begin{tabular}{l@{\hspace{10mm}}r} |
271 \begin{tabular}{l@{\hspace{10mm}}r} |
159 \includegraphics[scale=0.8]{pics/graphs.png}\\ |
272 \includegraphics[scale=0.8]{pics/graphs.png}\\ |
167 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
280 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
168 \mode<presentation>{ |
281 \mode<presentation>{ |
169 \begin{frame}[c] |
282 \begin{frame}[c] |
170 \frametitle{Graph Isomorphism Protocol} |
283 \frametitle{Graph Isomorphism Protocol} |
171 |
284 |
172 Alice starts with knowing an isomorphism between graphs \bl{$G_1$} and \bl{$G_2$}\medskip |
285 Alice starts with knowing an isomorphism \bl{$\sigma$} between graphs \bl{$G_1$} and \bl{$G_2$}\medskip |
173 |
286 |
174 \begin{enumerate} |
287 \begin{enumerate} |
175 \item Alice generates an isomorphic graph \bl{$H$} which she sends to Bob |
288 \item Alice generates an isomorphic graph \bl{$H$} which she sends to Bob |
176 \item Bob asks either for an isomorphism between \bl{$G_1$} and \bl{$H$}, or |
289 \item Bob asks either for an isomorphism between \bl{$G_1$} and \bl{$H$}, or |
177 \bl{$G_2$} and \bl{$H$} |
290 \bl{$G_2$} and \bl{$H$} |
178 \item Alice and Bob repeat this procedure \bl{$n$} times |
291 \item Alice and Bob repeat this procedure \bl{$n$} times |
179 \end{enumerate}\pause |
292 \end{enumerate}\pause |
180 |
293 |
181 these are called commitment algorithms |
294 these are called commitment algorithms |
|
295 |
|
296 \end{frame}} |
|
297 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
298 |
|
299 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
300 \mode<presentation>{ |
|
301 \begin{frame}[c] |
|
302 \frametitle{Graph Isomorphism Protocol (2)} |
|
303 |
|
304 If Alice knows the isomorphism, she can always calculate \bl{$\sigma$}.\bigskip |
|
305 |
|
306 If she doesn't, she can only correctly respond if Bob's |
|
307 choice of index is the same as the one she used to form \bl{$H$}. The probability |
|
308 of this happening is \bl{$\frac{1}{2}$}, so after \bl{$n$} rounds the probability of her |
|
309 always responding correctly is only \bl{$\frac{1}{2}^n$}. |
|
310 |
|
311 \end{frame}} |
|
312 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
313 |
|
314 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
315 \mode<presentation>{ |
|
316 \begin{frame}[c] |
|
317 \frametitle{Graph Isomorphism Protocol (3)} |
|
318 |
|
319 Why is the GI-protocol zero-knowledge?\bigskip\pause |
|
320 |
|
321 A: We can generate a fake transcript of a conversation, which |
|
322 cannot be distinguished from a ``real'' conversation.\bigskip |
|
323 |
|
324 Anything Bob can compute using the information obtained from |
|
325 the transcript can be computed using only a forged transcript and |
|
326 therefore participation in such a communication does not increase |
|
327 Bob's capability to perform any computation. |
|
328 |
182 \end{frame}} |
329 \end{frame}} |
183 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
330 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
184 |
331 |
185 |
332 |
|
333 |
186 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
334 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
187 \mode<presentation>{ |
335 \mode<presentation>{ |
188 \begin{frame}[c] |
336 \begin{frame}[c] |
189 \frametitle{Non-Interactive ZKPs} |
337 \frametitle{Non-Interactive ZKPs} |
190 |
338 |
191 |
339 |
192 \bigskip |
340 \bigskip |
193 This is amazing: Alison can publish some data that contains no data about her secret, |
341 This is amazing: Alison can publish some data that contains no data about her secret, |
194 but can be used to convince anyone of the secret's existence. |
342 but this data can be used to convince anyone of the secret's existence. |
|
343 \end{frame}} |
|
344 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
345 |
|
346 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
347 \mode<presentation>{ |
|
348 \begin{frame}[c] |
|
349 \frametitle{Non-Interactive ZKPs (2)} |
|
350 |
|
351 Alice starts with knowing an isomorphism \bl{$\sigma$} between graphs \bl{$G_1$} and \bl{$G_2$}\medskip |
|
352 |
|
353 \begin{enumerate} |
|
354 \item Alice generates \bl{$n$} isomorphic graphs \bl{$H_{1..n}$} which she makes public |
|
355 \item she feeds the \bl{$H_{1..n}$} into a hashing function (she has no control over what |
|
356 the output will be) |
|
357 \item Alice takes the first \bl{$n$} bits of the output: whenever output is \bl{$0$}, she shows |
|
358 an isomorphism with \bl{$G_1$} ; for \bl{$1$} she shows an isomorphism with \bl{$G_2$} |
|
359 \end{enumerate} |
|
360 |
195 \end{frame}} |
361 \end{frame}} |
196 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
362 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
197 |
363 |
198 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
364 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
199 \mode<presentation>{ |
365 \mode<presentation>{ |
200 \begin{frame}[c] |
366 \begin{frame}[c] |
201 \frametitle{Problems of ZKPs} |
367 \frametitle{Problems of ZKPs} |
202 |
368 |
203 |
369 \begin{itemize} |
204 \bigskip |
370 \item ``grand chess master problem'' (person in the middle) |
205 This is amazing: Alison can publish some data that contains no data about her secret, |
371 \item |
206 but can be used to convince anyone of the secret's existence. |
372 \end{itemize} |
|
373 |
|
374 \end{frame}} |
|
375 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
376 |
|
377 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
378 \mode<presentation>{ |
|
379 \begin{frame}[c] |
|
380 \frametitle{Other Methods for ZKPs} |
|
381 |
|
382 \begin{itemize} |
|
383 \item modular logarithms (you can |
|
384 \end{itemize} |
|
385 |
207 \end{frame}} |
386 \end{frame}} |
208 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
387 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
209 |
388 |
210 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
389 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
211 \mode<presentation>{ |
390 \mode<presentation>{ |