1 \xcalways\section{Basics}\x
3 \xcalways\subsection{Introduction and motivation}\x
5 \begin{slide}
6 \topic{joke}
9 An elderly Frenchman rises every morning at 5, goes out to the street in
10 front of his house, and sprinkles a white powder up and down the street.
12 One day, a neighbour, who has watched his routine for many years, confronts
13 him. What is this powder you sprinkle on the street every morning,
14 Pierre?'
16 It is elephant powder, \emph{mon ami},' the gentleman says. It keeps the
17 elephants away.'
19 But Pierre,' says the neighbour. Everybody knows that there are no
20 elephants in France.'
22 Says the older man matter-of-factly, I guess it must be working, then.'
23 \end{slide}
25 The joke has its mandatory corresponding serious message. Cryptography is
26 like elephant powder. If it seems to work, and keeps the attackers -- our
27 elephants -- away, then we trust it. This isn't really very satisfactory.
28 When the elephant powder fails, a 2-ton elephant turns up, with three of its
29 chums in a Mini, and you notice it hiding upside-down in your bowl of
30 custard. Let's face it: elephants aren't good at being surreptitious.
32 But if your cryptography is no good, you may never know.
34 \begin{slide}
35 \topic{serious message}
38 So, what can we do about the situation?
39 \begin{itemize}
40 \item Design simple cryptographic primitives, e.g., block ciphers, hash
41 functions. Develop techniques for analysing them, and attempt to stay
43 \item Build useful constructions from trusted primitives in a modular way.
44 \emph{Prove that the constructions are secure.}
45 \end{itemize}
46 Here we look at this second part of the approach.
47 \end{slide}
49 \xcalways\subsection{Approach}\x
51 \begin{slide}
54 \begin{itemize}
55 \item Define notions of security. Now we know what to aim for, and what to
56 expect of our components.
57 \item Prove how the security of a construction relates to the security of
58 its primitives. If it breaks, we know who to blame.
59 \end{itemize}
60 \end{slide}
62 \begin{slide}
66 We model our adversary as a \emph{probabilistic algorithm}; i.e., the
67 algorithm is allowed to \emph{flip coins} to make decisions. The
68 adversary's output (for some input) follows a probability distribution. We
69 define what it means for an adversary to \emph{break} our construction, and
70 examine the probability with which this happens.
72 We provide the adversary with \emph{oracles}:
73 \begin{itemize}
74 \item Oracles compute using secrets hidden from the adversary.
75 \item We count the number of \emph{queries} made to an oracle.
76 \item We can restrict the types of queries the adversary makes.
77 \end{itemize}
79 Oracles are written as superscripts. For example, an adversary given a
80 chosen-plaintext oracle might be written as $A^{E_K(\cdot)}$.
81 \end{slide}
83 \begin{slide}
84 \topic{the asymptotic approach}
85 \resetseq
88 A function $\nu\colon \N \to \R$ is \emph{negligible} if, for any integer
89 $c$, there exists an $n \in \N$ such that $0 \le \nu(k) < k^{-c}$ for all
90 $k \ge n$. That is, $\nu(k)$ is eventually' less than any polynomial
91 function of $k$.
93 We examine families of constructions, with a \emph{security parameter} $k$.
94 We say that a function is (asymptotically) secure in some sense if, for any
95 polynomial $p(k)$ there is a negligible function $\nu(k)$ such that, for
96 any construction in the family, parameterized by $k$, no adversary which
97 runs for time $p(k)$ has success probability better than $\nu(k)$.
98 \end{slide}
100 \begin{slide}
103 Suppose we build an encryption scheme from a one-way function. We'd like
104 to prove that the encryption is good if the one-way function is secure. We
106 \begin{enumerate}
107 \item Suppose an adversary $A$ breaks the encryption scheme with
108 better-than-negligible probability.
109 \item Show a polynomial-time \emph{reduction}: an algorithm which uses $A$
110 to break the one-way function, in polynomial time, and with
111 better-than-negligible probability,
112 \item Claim that this violates the assumption of a secure one-way function.
113 \end{enumerate}
115 This doesn't work with real constructions. We don't know where the
116 asymptotics set in, and they can conceal large constants. It's still
117 better than nothing.
118 \end{slide}
120 \begin{slide}
121 \topic{the concrete (quantitative) approach}
124 We constrain the resources we allow the adversary:
125 \begin{itemize}
126 \item Running time (including program size).
127 \item Number of oracle queries.
128 \item Maximum size of oracle queries.
129 \end{itemize}
130 Write that something is \emph{$(t, q, \epsilon)$-secure} if no adversary
131 which runs in time $t$ and makes $q$ oracle queries can break it with
132 probability better than $\epsilon$.
134 We make statements like foo is $(t, q, 2 q \epsilon)$-secure if bar is $(t 135 + O(q), 2 q, \epsilon)$-secure'.
137 This is a much more satisfactory approach. However, we still have to
138 \emph{assume} the security of our primitive operations.
139 \end{slide}
141 \xcalways\subsection{Notation}\x
143 \begin{slide}
144 \topic{boolean operators}
145 \resetseq
148 If $P$ and $Q$ are \emph{predicates} -- i.e., either true or false -- then:
149 \begin{itemize}
150 \item $P \land Q$ is true if both $P$ \emph{and} $Q$ is true;
151 \item $P \lor Q$ is true if either $P$ \emph{or} $Q$ (or both) is true;
152 \item $\lnot P$ is true if $P$ is false; and
153 \item $P \implies Q$ is true if $Q$ is true or $P$ is false.
154 \end{itemize}
155 \end{slide}
157 \begin{slide}
158 \topic{sets}
161 For our purposes, we can think of sets as being collections of objects.
163 We use the usual notations for set membership ($x \in X$), intersection ($X 164 \cap Y$), union ($X \cup Y$) and subset containment ($X \subseteq Y$). The
165 \emph{empty set}, which contains no elements, is written $\emptyset$.
167 The notation $\{\, f(x) \mid P(x) \,\}$ describes the set containing those
168 items $f(x)$ for those $x$ for which the predicate $P(x)$ is true.
170 The \emph{cardinality} $|X|$ of a (finite) set $X$ is the number of
171 elements in the set.
173 The power set $\powerset(X)$ of a set $X$ is the set of all subsets of $X$.
175 The \emph{Cartesian product} of two sets $X \times Y$ is the set of all
176 ordered pairs $\{\, (x, y) \mid x \in X \land y \in Y \,\}$. We use
177 exponents to indicate the product of a set with itself: hence, $X^2 = X 178 \times X$.
180 A \emph{relation} $R$ is a subset of a Cartesian product. We write $R(x, 181 y)$ if $(x, y) \in R$. Relations between two sets are often written as
182 infix symbols: e.g., $x \sim y$.
183 \end{slide}
185 \begin{slide}
188 In addition to strings, defined later, we use the following standard sets:
189 \begin{itemize}
190 \item the set $\Z$ of integers;
191 \item the set $\N = \{\, x \in \Z \mid x \ge 0 \,\}$ of natural numbers;
192 \item the set $\R$ of real numbers;
193 \item closed intervals $[a, b] = \{\, x \in \R \mid a \le x \le b \,\}$;
194 \item the finite field $\F_q$ of $q$ elements, and its multiplicative
195 subgroup $\F_q^* = \F_q \setminus \{0\}$; and
196 \item the ring $\Z/n\Z$ of residue classes modulo $n$ (i.e., if $x \in 197 \Z/n\Z$ and $a, b \in x$ then $a \equiv b \pmod{n}$), and its
198 multiplicative subgroup $(\Z/n\Z)^* = \Z/n\Z - \{\, x + n\Z \mid \gcd(x, 199 n) > 1 \,\}$.
200 \end{itemize}
201 \end{slide}
203 \begin{slide}
204 \topic{functions}
207 A \emph{function} $f\colon X \to Y$ is a mapping which assigns every
208 element $x$ in the \emph{domain} $X$ a corresponding element $f(x)$ in the
209 \emph{range} (or sometimes \emph{codomain}) $Y$. The notation $\dom f$
210 describes the domain of an arbitrary function; $\ran f$ describes its
211 range.
213 We sometimes apply the function notation to sets, indicating that the
214 function should be applied pointwise; i.e., $f(Z) = \{ f(z) \mid z \in Z 215 \}$. The \emph{image} of a function $f$ is the set $f(\dom f)$.
217 If $f\colon X \to Y$ preserves equality, i.e., $f(x) = f(x') \implies x = 218 x'$ for all $x, x' \in X$, then we say $f$ is \emph{injective} (or
219 \emph{1-to-1}). If $f(X) = Y$ then we say that it is \emph{surjective} (or
220 \emph{onto}). If $f$ is both injective and surjective then we say that it
221 is \emph{bijective}. In this case, there is a well-defined inverse
222 $f^{-1}\colon Y \to X$ defined by $f(f^{-1}(y)) = y$ for all $y \in Y$.
224 If $f\colon X \to X$ (i.e., its domain and range are the same set) is
225 bijective, then we say that $f$ is a \emph{permutation on $X$}.
226 \end{slide}
228 \begin{slide}
231 We can consider a function $f\colon X \to Y$ to be a particular sort of
232 relation $f \subseteq X \times Y$, subject to the constraint that if $(x, 233 y) \in f$ and $(x, y') \in f$ then $y = y'$.
235 We shall use this view in some of the algorithms we present. In addition,
236 we shall use the \emph{maplet} notation $x \mapsto y$ rather than the
237 ordered pair notation $(x, y)$ to reinforce the notion of a mapping.
239 We might write, for example,
240 \begin{program}
241 $f \gets f \cup \{ x \mapsto y \}$;
242 \end{program}
243 to augment a function by the addition of a new mapping. This is clearly
244 only valid if $x \notin \dom f$ (or $f(x) = y$) initially.
245 \end{slide}
247 \begin{slide}
248 \topic{strings}
251 An \emph{alphabet} is a finite set of \emph{symbols}. The one we'll use
252 most of the time is the set $\Sigma = \{0, 1\}$ of \emph{bits}.
254 Suppose $A$ is an alphabet. The set of sequences of exactly $n$ symbols
255 from $A$ is written $A^n$. Hence, $\{0, 1\}^{64}$ is the set of all 64-bit
256 sequences. The set of (finite) \emph{strings} over an alphabet $A$ is $A^* 257 = \bigcup_{i \in \N} A^i$. The empty string is named $\emptystring$.
259 The \emph{length} of a string $a \in A^*$, written $|a|$, is the natural
260 number $n$ where $a \in A^n$.
262 If $x, y \in A^*$ are strings then their \emph{concatenation}, written $x 263 \cat y$, or sometimes just $x y$, is the result of writing the symbols in
264 $x$ followed by the symbols in $y$, in order. We have $|x y| = |x| + |y|$.
265 \end{slide}
267 \begin{slide}
270 There are natural (injective) mappings between bit strings and natural
271 numbers.
273 If $x = x_0 x_1 \ldots x_{n-1} \in \{0, 1\}^*$ then we can associate with
274 it the natural number
275 $\overrightarrow{x} = \sum_{0 \le i < n} 2^i x_i.$
277 The other natural mapping is
278 $\overleftarrow{x} = \sum_{0 \le i < n} 2^{n-i-1} x_i.$
279 It doesn't matter which you choose, as long as you're consistent.
281 For simplicity's sake, we shall tend to switch between strings and the
282 numbers (and occasionally more exotic objects) they represent implicitly.
283 \end{slide}
285 \begin{slide}
286 \topic{parsing}
289 We'll find it useful to be able to break up strings in the algorithms we
290 present. We use the statement
291 \begin{program}
292 \PARSE $x$ \AS $n_0\colon x_0, n_1\colon x_1, \ldots, n_k\colon x_k$;
293 \end{program}
294 to mean that the string $x$ is broken up into individual strings $x_0$,
295 $x_1$, \ldots, $x_k$, such that
296 \begin{itemize}
297 \item $x = x_0 \cat x_1 \cat \cdots \cat x_k$; and
298 \item $|x_i| = n_i$ for all $0 \le i \le k$.
299 \end{itemize}
300 We may omit one of the $n_i$ length indicators, since it can be deduced
301 from the length of the string $x$ and the other $n_j$.
302 \end{slide}
304 \begin{slide}
305 \topic{vectors}
308 A \emph{vector} $\vect{x}$ is a finite ordered collection of elements from
309 some set $X$. If $\vect{x}$ contains $n$ elements then we write $\vect{x} 310 \in X^n$, and that $|\vect{x}| = n$. We write the individual elements as
311 $\vect{x}, \vect{x}, \ldots, \vect{x}[n - 1]$.
313 We shall abuse set membership notation for vectors; i.e., we write $x \in 314 \vect{x}$ if there is an $i$ ($0 \le i < |\vect{x}|$) such that
315 $\vect{x}[i] = x$.
317 When we apply functions to vectors, we mean that they are applied
318 pointwise, as for sets. Thus, if we write that $\vect{y} = 319 f(\vect{x})$ then $|\vect{y}| = |\vect{x}|$ and $\vect{y}[i] = 320 f(\vect{x}[i])$ for all $0 \le i < |\vect{x}|$.
321 \end{slide}
323 \begin{slide}
324 \topic{distributions and randomness}
325 \head{Notation, \seq: distributions and randomness}
327 A \emph{probability distribution} over a (countable) set $X$ is a
328 function $\mathcal{D}\colon X \to [0, 1]$ such that
329 $\sum_{x \in X} \mathcal{D}(x) = 1.$
331 The \emph{support} of $\mathcal{D}$, written $\supp \mathcal{D}$, is the
332 set $\{ x \in X \mid \mathcal{D}(x) \ne 0 \}$; i.e., those elements of $X$
333 which occur with nonzero probability.
335 We write $x \getsr \mathcal{D}$ in algorithms to indicate that $x$ is to be
336 chosen independently at random, according to the distribution
337 $\mathcal{D}$. The notation $x \inr \mathcal{D}$ indicates that $x$ has
338 been chosen at independently at random according to $\mathcal{D}$.
340 The \emph{uniform distribution} over a (finite) set $X$ is
341 $\mathcal{U}_X\colon X \to [0, 1]$ defined by $\mathcal{U}_X(x) = 1/|X|$
342 for all $x \in X$. We shall write $x \getsr X$ and $x \inr X$ as
343 convenient shorthands, meaning $x \getsr \mathcal{U}_X$ and $x \inr 344 \mathcal{U}_X$ respectively.
345 \end{slide}
347 \xcalways\subsection{Background}\x
349 \begin{slide}
350 \topic{distinguishability}
351 \resetseq
354 Suppose that $\mathcal{X}$ and $\mathcal{Y}$ are two probability
355 distributions.
357 Let $X$ be a random variable distributed according to $\mathcal{X}$, and
358 let $Y$ be a random variable distributed according to $\mathcal{Y}$. We
359 say that $\mathcal{X}$ and $\mathcal{Y}$ are \emph{identically
360 distributed}, and write that $\mathcal{X} \equiv \mathcal{Y}$, if, for
361 all possible values $x$ of $X$, we have
362 $\Pr[X = x] = \Pr[Y = x].$
364 Equivalently, we require that, for all $x \in \supp \mathcal{X}$ we have
365 $x \in \supp \mathcal{Y} \land \mathcal{X}(x) = \mathcal{Y}(y).$
366 \end{slide}
368 \begin{slide}
371 Now we generalize the setting slightly. Consider two \emph{families} of
372 distributions, $\{\mathcal{X}_k\}_{k\in\N}$ and
373 $\{\mathcal{Y}_k\}_{k\in\N}$, parameterized by a security parameter $k$,
374 where $\dom\mathcal{X}_k = \dom\mathcal{Y}_k$. To make the asymptotics
375 work, we require that $|x| \le p(k)$ for some polynomial $p(\cdot)$, for
376 all $x \in \dom\mathcal{X}_k$.
378 Fix a value of $k$. Again, let $X$ be distributed according to
379 $\mathcal{X}_k$, and let $Y$ be distributed according to $\mathcal{Y}_k$.
380 We say that $\{\mathcal{X}_k\}_{k \in \N}$ and $\{\mathcal{Y}_k\}_{k\in\N}$
381 are \emph{statistically close}, and write that $\{\mathcal{X}_k\}_{k\in\N} 382 \statclose \{\mathcal{Y}_k\}_{k\in\N}$, if there is a negligible function
383 $\nu(\cdot)$ such that, for any $k \in \N$,
384 $\sum_{x\in\dom{\mathcal{X}_k}} 385 |{\Pr[X = x]} - \Pr[Y = x]| \le \nu(k).$%
386 (Reminder: Saying that $\nu\colon \N \to \R$ is \emph{negligible} means
387 that, for any $c \in \Z$ there is an $n \in N$ such that $\nu(k) < 388 k^{-c}$.)
389 \end{slide}
391 \begin{slide}
394 We say that two families of distributions are computationally
395 indistinguishable if no efficient' algorithm can tell them apart with
396 better than negligible' probability.
398 So, we say that $\{\mathcal{X}_k\}_{k\in\N}$ and
399 $\{\mathcal{Y}_k\}_{k\in\N}$ are \emph{computationally indistinguishable}
400 and write that $\{\mathcal{X}_k\}_{k\in\N} \compind 401 \{\mathcal{Y}_k\}_{k\in\N}$, if, for any probabilistic polynomial-time
402 algorithm $A$, there is a negligible function $\nu(\cdot)$ such that, for
403 any $k$:
404 $\Pr[x \getsr \mathcal{X}_k; b \gets A(x) : b = 1] - 405 \Pr[y \getsr \mathcal{Y}_k; b \gets A(y) : b = 1] \le \nu(k).$%
406 Statistical closeness implies computational indistinguishability.
407 \end{slide}
409 \begin{proof}
410 Let two statistically close distributions $\{\mathcal{X}_k\}_{k\in\N} 411 \statclose \{\mathcal{Y}_k\}_{y\in\N}$ be given. Fix some $k$, and let $Z 412 = \dom\mathcal{X}_k = \dom\mathcal{Y}_k$. Now note that the adversary's
413 advantage is given by $\sum_{z\in Z} \Pr[b \gets A(z) : b = 1] 414 |\mathcal{X}_k(z) - \mathcal{Y}_k(z)| \le \sum_{z\in Z} |\mathcal{X}_k(z) - 415 \mathcal{Y}_k(z)| \le \nu(k)$. Hence the two distributions are
416 computationally indistinguishable.
417 \end{proof}
419 \begin{slide}
420 \topic{collisions}
421 \head{Collisions -- the Birthday paradox'}
423 Suppose we throw $q$ balls into $n$ bins at random (with $q \le n$). Let
424 $C_{q, n}$ be the event that, at the end of this, we have a bin containing
425 more than one ball -- a \emph{collision}.
427 Let $B_{q, n}$ be the event that the $q$-th ball collides with a
428 previous one. Obviously, the worst case for this is when none of the other
429 balls have collided, so
430 $\Pr[B_{q, n}] \le \frac{q - 1}{n}.$
431 Then
432 \begin{eqnarray*}[rl]
433 \Pr[C_{q, n}]
434 &\le \Pr[B_{2, n}] + \Pr[B_{3, n}] + \cdots + \Pr[B_{q, n}] \\
435 &\le \frac{1}{n} + \frac{2}{n} + \cdots + \frac{q - 1}{n} \\
436 &= \frac{q(q - 1)}{2 n}.
437 \end{eqnarray*}
438 This is an extremely useful result, and we shall need it often.
439 \end{slide}
441 \xcalways\subsection{Primitives}\x
443 \begin{slide}
444 \topic{one-way functions}
445 \resetseq
448 Intuition: a one-way function is easy to compute but hard to invert.
450 Choose a function $f\colon X \to Y$. Let $I$ be a prospective inverter.
451 Now we play a game:
452 \begin{enumerate}
453 \item Choose $x \in X$ at random. Compute $y = f(x)$.
454 \item Let $x'$ be the output of $I$ when run on input $y$.
455 \item We say that $I$ wins' if $f(x') = y$; otherwise it loses.
456 \end{enumerate}
457 Note that we don't care whether $x = x'$.
459 Examples: SHA-1, or $x \mapsto g^x \bmod p$.
460 \end{slide}
462 \begin{slide}
465 The \emph{success probability} of an inverter $I$ against the function $f$
466 is
467 $\Succ{owf}{f}(I) = 468 \Pr[x \getsr X; 469 y \gets f(x); 470 x' \gets I(y) : 471 f(x') = y]$%
472 where the probability is taken over all choices of $x$ and all coin flips
473 made by $I$.
475 We measure the \emph{insecurity} of a one-way function (OWF) by maximizing
476 over possible inverters:
477 $\InSec{owf}(f; t) = \max_I \Succ{owf}{f}(I)$
478 where the maximum is taken over all $I$ running in time $t$.
480 If $\InSec{owf}(f; t) \le \epsilon$ then we say that $f$ is a \emph{$(t, 481 \epsilon)$-secure one-way function}.
482 \end{slide}
484 \begin{slide}
487 Intuition: a \emph{trapdoor} is secret information which makes inverting a
488 one-way function easy. This is most useful when the one-way function is a
489 permutation. A trapdoor one-way function generator $\mathcal{T} = (G, f, 490 T)$ is a triple of algorithms:
492 \begin{itemize}
493 \item The probabilistic algorithm $G$ is given some parameter $k$ and
494 returns a pair $(P, K)$, containing the public parameters $P$ for
495 computing an instance of the one-way function, and the secret trapdoor
496 information $K$ for inverting it. We write $(P, K) \in G(k)$.
498 \item The algorithm $f$ implements the one-way function. That is, if $(P, 499 K) \in G(k)$ then $f(P, \cdot)$ (usually written $f_P(\cdot)$) is a
500 one-way function.
502 \item The algorithm $T$ inverts $f$ using the trapdoor information. That
503 is, if $(P, K) \in G(k)$ and $y = f_P(x)$ for some $x$, then $y = 504 f_P(T(K, y))$. We usually write $T_K(\cdot)$ instead of $T(K, \cdot)$.
505 \end{itemize}
506 \end{slide}
508 \begin{slide}
509 \topic{pseudorandom generators (PRGs)}
512 A pseudorandom generator (PRG) stretches' an input seed into a longer
513 string which looks' random.
515 Let $G\colon \{0, 1\}^k \to \{0, 1\}^L$ be a function from $k$-bit strings
516 to $L$-bit strings. The \emph{advantage} of a distinguisher $D$ against
517 $G$ is:
518 \begin{eqnarray*}[rl]
520 \Pr[x \getsr \{0, 1\}^k; y \gets G(x) : D(y) = 1] - {}\\
521 & \Pr[y \getsr \{0, 1\}^L : D(y) = 1].
522 \end{eqnarray*}
523 The \emph{insecurity} is simply the maximum advantage:
524 $\InSec{prg}(G; t) = \max_D \Adv{prg}{G}(D)$
525 where the maximum is taken over all distinguishers $D$ running in time
526 $t$. If $\InSec{prg}(G; t) \le \epsilon$ then we also say that $G$ is a
527 $(t, \epsilon)$-secure PRG\@.
528 \end{slide}
530 \begin{exercise}
531 We say that a PRG $g\colon \{0, 1\}^k \to \{0, 1\}^L$ is \emph{trivial} if
532 $k \ge L$.
533 \begin{enumerate}
534 \item Show that trivial PRGs exist.
535 \item Show that if $g$ is nontrivial, then $g$ is also a one-way function,
536 with
537 $\InSec{owf}(g; t) \le \InSec{prg}(g; t) + 2^{k-L}.$
538 \end{enumerate}
540 \begin{parenum}
541 \item The identity function $I(x) = x$ is a trivial PRG, with
542 $\InSec{prg}(I, t) = 0$, as is easily seen from the definition.
543 \item Suppose $A$ inverts $g$. Then consider adversary $B(y)$: \{ $x \gets 544 A(y)$; \IF $g(x) = y$ \THEN \RETURN $1$; \ELSE \RETURN $0$;~\}. If $y$
545 is the output of $g$, then $A$ inverts $y$ with probability
546 $\Succ{owf}{g}(A)$; if $y$ is random in $\{0, 1\}^L$ then there is a
547 probability at least $1 - 2^{k-L}$ that $y$ has \emph{no} inverse,
548 proving the result. Note that \cite{Wagner:2000:PSU} provides a better
549 security bound than this simplistic analysis.
550 \end{parenum}
551 \end{exercise}
553 \begin{exercise}
554 \label{ex:dbl-prg}
555 Suppose that we have a \emph{length-doubling} PRG $g\colon \{0, 1\}^k \to 556 \{0, 1\}^{2k}$. Let $g_0(\cdot)$ be the first $k$ bits of $g(x)$ and
557 $g_1(\cdot)$ be the second $k$ bits. Define the sequence of generators
558 $g^{(i)}$ (for $i >= 1$) by
559 $g^{(1)}(x) = g(x); \qquad 560 g^{(i+1)}(x) = g_0(x) \cat g^{(i)}(g_1(x)).$%
561 Relate the security of $g^{(i)}$ to that of $g$.
563 The description of the function $g^{(i)}$ is deliberately terse and
564 unhelpful. It probably helps understanding if you make a diagram.
566 Let $A$ be an adversary running in time $t$ and attacking $g^{(i+1)}$.
567 Firstly, we attack $g$: consider adversary $B(y)$: \{ \PARSE $y$ \AS $y_0, 568 k\colon y_1$; $z \gets g^{(i)}$; $b \gets A(y_0 \cat z)$; \RETURN $b$;~\}.
569 Then $\Adv{prg}{g}(B) \ge \Adv{prg}{g^{(i+1)}}(A) + \delta$, so
570 $\InSec{prg}(g^{(i+1)}; t) \le \InSec{prg}(g; t) + \delta$, where
571 \begin{eqnarray*}[rl]
572 \delta = &\Pr[x_0 \gets \{0, 1\}^k; x_1 \gets \{0, 1\}^k;
573 y \gets g^{(i)}(x) : A(x_0 \cat y) = 1] - \\
574 &\Pr[y \getsr \{0, 1\}^{(i+2)k} : A(y) = 1].
575 \end{eqnarray*}
576 We attack $g^{(i)}$ to bound $\delta$: consider adversary $C(y)$: \{ $x_0 577 \getsr \{0, 1\}^k$; $b \gets A(x_0 \cat y)$; \RETURN $b$;~\}. Now $\delta 578 \le \Adv{prg}{g^{(i)}}(C) \le \InSec{prg}(g^{(i)}; t)$. So by induction,
579 $\InSec{prg}(g^{(i)}; t) \le i \cdot \InSec{prg}(g; t).$
580 \end{exercise}
582 \begin{slide}
586 Advantage is a concept used in many definitions of security notions:
587 \begin{eqnarray*}[rl]
589 \Pr[\text{$A$ returns 1 in setting $a$}] - {} \\
590 & \Pr[\text{$A$ returns 1 in setting $b$}].
591 \end{eqnarray*}
592 \begin{enumerate}
593 \item We have $-1 \le \Adv{}{}(A) \le +1$.
594 \item Zero means that the adversary couldn't distinguish.
595 \item Negative advantage means the adversary got them the wrong way
596 around. There is another adversary which uses the same resources but has
598 \item \label{item:adv-guess} If $A$ is attempting to guess some hidden bit
599 $b^* \inr \{0, 1\}$, we have
600 $\Pr[b \gets A : b = b^*] = \frac{\Adv{}{}(A)}{2} + \frac{1}{2}.$
601 \end{enumerate}
602 \end{slide}
604 \begin{proof}
605 Let $b$ be the bit that $A$ returns, and let $b^*$ be the experiment's
606 hidden bit. Then
607 $\Adv{}{}(A) = \Pr[b = 1 \mid b^* = 1] - \Pr[b = 1 \mid b^* = 0].$
608 Addressing the above claims in order:
609 \begin{enumerate}
610 \item By definition of probability, $0 \le \Pr[b = 1 \mid b^* = 1] \le 1$
611 and $0 \le \Pr[b = 1 \mid b^* = 0]$, so their absolute difference can be
612 at most 1.
613 \item This is a corollary of \ref{item:adv-guess}.
614 \item Consider the adversary $\bar{A}$ which runs $A$ and returns the
615 complement bit $\bar{b} = b \xor 1$. Then
616 \begin{eqnarray*}[rl]
618 &= \Pr[\bar{b} = 1 \mid b^* = 1] - \Pr[\bar{b} = 1 \mid b^* = 0] \\
619 &= \Pr[b = 0 \mid b^* = 1] - \Pr[b = 0 \mid b^* = 0] \\
620 &= (1 - \Pr[b = 1 \mid b^* = 1]) - (1 - \Pr[b = 1 \mid b^* = 0]) \\
621 &= \Pr[b = 1 \mid b^* = 0] - \Pr[b = 1 \mid b^* = 1] \\
623 \end{eqnarray*}
624 \item Note that $\Pr[b^* = 1] = \Pr[b^* = 0] = \frac{1}{2}$. Then
625 \begin{eqnarray*}[rl]
626 \Pr[b = b^*]
627 &= \Pr[b = 1 \land b^* = 1] + \Pr[b = 0 \land b^* = 0] \\
628 &= \frac{1}{2}(\Pr[b = 1 \mid b^* = 1] + \Pr[b = 1 \mid b^* = 0]) \\
629 &= \frac{1}{2}(\Pr[b = 1 \mid b^* = 1] +
630 (1 - \Pr[b = 0 \mid b^* = 0])) \\
631 &= \frac{1}{2}(1 + \Pr[b = 1 \mid b^* = 1] -
632 \Pr[b = 0 \mid b^* = 0]) \\
634 \end{eqnarray*}
635 \end{enumerate}
636 All present and correct.
637 \end{proof}
639 \begin{slide}
640 \topic{pseudorandom functions (PRFs)}
643 A \emph{pseudorandom function family} (PRF) is a collection of functions
644 $F_K\colon \{0, 1\}^l \to \{0, 1\}^L$, where $K$ is some index, typically
645 from a set of fixed-size strings $\{0, 1\}^k$. We shall often consider a
646 PRF to be a single function $F\colon \{0, 1\}^k \times \{0, 1\}^l \to \{0, 647 1\}^L$.
649 We want to say that $F$ is a strong PRF if adversaries find it hard to
650 distinguish an instance $F_K$ from a function chosen completely at random
651 with the same shape'.
653 We provide the adversary with an \emph{oracle}, either for a randomly
654 selected $F_K$, or for completely random function, and ask it to try and
655 say which it is given.
657 We write $\Func{l}{L}$ as the set of \emph{all} functions from $\{0, 1\}^l$
658 to $\{0, 1\}^L$.
659 \end{slide}
661 \begin{slide}
664 We define the advantage of a distinguisher $D$ against the PRF $F$ as
665 follows:
666 \begin{eqnarray*}[rl]
668 \Pr[K \getsr \{0, 1\}^k : D^{F_K(\cdot)} = 1] - {}\\
669 & \Pr[R \getsr \Func{l}{L} : D^{R(\cdot)} = 1].
670 \end{eqnarray*}
671 The insecurity of the PRF is then measured as
672 $\InSec{prf}(F; t, q) = \max_D \Adv{prf}{F}(D)$
673 where the maximum is taken over all distinguishers $D$ which run for time
674 $t$ and make $q$ oracle queries. As is usual, if $\InSec{prf}(F; t, q) 675 \le \epsilon$ then we say that $F$ is a $(t, q, \epsilon)$-secure PRF.
676 \end{slide}
678 \begin{slide}
679 \topic{pseudorandom permutations (PRPs)}
682 We define a \emph{pseudorandom permutation family} (PRP) in a similar way
683 to the PRFs we've already seen. A PRP is a family $F_K\colon \{0, 1\}^L 684 \to \{0, 1\}^L$ is a of permutations, indexed by elements of some finite
685 set, e.g., $\{0, 1\}^k$. We shall often consider a PRP to be a single
686 function $F\colon \{0, 1\}^k \times \{0, 1\}^l \to \{0, 1\}^L$.
688 Let $\Perm{L}$ be the set of \emph{all} permutations over the set of
689 $L$-bit strings $\{0, 1\}^L$.
691 The advantage of a distinguisher $D$ against the PRP $F$ is
692 \begin{eqnarray*}[rl]
694 \Pr[K \getsr \{0, 1\}^k : D^{F_K(\cdot)} = 1] - {}\\
695 & \Pr[R \getsr \Perm{L} : D^{R(\cdot)} = 1].
696 \end{eqnarray*}
698 We define $\InSec{prp}(F; t, q) = \max_D \Adv{prp}{F}(D)$ exactly as for
699 PRFs, and the notion of $(t, q, \epsilon)$-security is the same.
700 \end{slide}
702 \begin{slide}
705 PRPs are bijective. A \emph{super PRP} is a PRP which remains secure when
706 the distinguisher is allowed to make inverse queries:
707 \begin{eqnarray*}[rl]
709 \Pr[K \getsr \{0, 1\}^k : D^{F_K(\cdot), F_K^{-1}(\cdot)} = 1] - {} \\
710 & \Pr[R \getsr \Perm{L} : D^{R(\cdot), R^{-1}(\cdot)} = 1].
711 \end{eqnarray*}
712 Since there are two oracles, we count queries to both when evaluating the
713 insecurity:
714 $\InSec{sprp}(F; t, q, q') = \max_D \Adv{sprp}{F}(D)$
715 where the maximum is taken over all distinguishers $D$ which run for time
716 $t$, make $q$ queries to the standard oracle, and $q'$ queries to the
717 inverse oracle. If $\InSec{sprp}(F; t, q, q') \le \epsilon$ then we say
718 $F$ is a $(t, q, q', \epsilon)$-secure super PRP\@.
719 \end{slide}
721 \begin{exercise}
722 Note that the key length hasn't appeared anywhere in the definition of
723 insecurity for a PRP. Derive lower bounds for the insecurity of a PRP with
724 a $k$-bit key.
726 Let $E\colon \{0, 1\}^k \times \{0, 1\}^L \to \{0, 1\}^L$ be a PRP. Fix
727 $n$ and $c$. Then consider adversary $S^{E(\cdot)}$: \{ \FOR $i = 0$ \TO
728 $c - 1$ \DO $y[i] \gets E(i)$; \FOR $K = 0$ \TO $n - 1$ \DO \{ $i \gets 0$;
729 $\id{good} \gets 1$; \WHILE $i < c \land \id{good} = 1$ \DO \{ \IF $E_K(i) 730 \ne y[i]$ \THEN $\id{good} \gets 0$;~\} \IF $\id{good} = 1$ \THEN \RETURN
731 $1$;~\}~\}. Then $\Adv{prp}{E}(S) \ge n(2^{-k} - 2^{-Lc})$.
732 \end{exercise}
734 \begin{slide}
735 \resetseq
738 We model block ciphers as families of PRPs (not super PRPs). Most of the
739 analysis works best on PRFs, though. We show that a PRP makes a pretty
740 good' PRF, as long as it's not over-used.
742 Let $F$ be any PRP family. Then
743 $\InSec{prf}(F; t, q) \le 744 \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}}.$%
745 This is a useful result. As long as $q^2$ is small compared to $2^L$ --
746 the block size -- then a PRP makes a good PRF.
748 The value $2^{L/2}$ is often called the \emph{Birthday bound}. We shall
749 meet it often when we examine modes of operation. We shall examine the
750 proof, because it illustrates some useful techniques.
751 \end{slide}
753 \begin{slide}
756 This handy lemma states that the difference in the probability of some
757 outcome between the two games is bounded above by the probability that the
758 games differ.
760 \begin{lemma}[Shoup \cite{Shoup:2001:OAEPR}]
761 \label{lem:shoup}
762 If $X$, $Y$ and $F$ are events, and $\Pr[X \land \lnot F] = \Pr[Y \land 763 \lnot F]$ then $|{\Pr[X]} - \Pr[Y]| \le \Pr[F]$.
764 \end{lemma}
765 \begin{proof}
766 We have:
767 \begin{eqnarray*}[rll]
768 \Pr[X] &= \Pr[X \land F] &+ \Pr[X \land \lnot F] \\
769 \Pr[Y] &= \Pr[Y \land F] &+ \Pr[Y \land \lnot F]
770 \end{eqnarray*}
771 Subtracting gives
772 $|{\Pr[X]} - \Pr[Y]| = |{\Pr[X \land F]} - 773 \Pr[Y \land F]| \le \Pr[F]$%
774 as required.
775 \end{proof}
776 \end{slide}
778 \begin{slide}
779 \head{PRPs are PRFs, \seq: proof}
781 Let $F\colon \{0, 1\}^k \times \{0, 1\}^L \to \{0, 1\}^L$ be a pseudorandom
782 permutation. We aim to show that $F$ is also a pseudorandom function.
784 Let $A$ be an adversary which distinguishes~$F$ from a pseudorandom
785 function in time~$t$, after making $q$ oracle queries. We consider a
786 sequence of games $\G{i}$ played with the adversary. In each game $\G{i}$,
787 let $S_i$ be the event that the adversary returns~$1$ at the end of the
788 game.
790 Game~$\G0$ is the random function' game. We given $A$ an oracle
791 containing a random function $R \inr \Func{L}{L}$.
793 Game~$\G1$ is the PRF' game. We give $A$ an oracle which computes
794 $F_K(\cdot)$ for some randomly chosen $K \inr \{0, 1\}^k$.
796 By definition, then,
797 $\Adv{prf}{F}(A) = \Pr[S_1] - \Pr[S_0].$
798 \end{slide}
800 \begin{slide}
801 \head{PRPs are PRFs, \seq: proof (cont.)}
803 Let $x_0, x_1, \ldots, x_{q-1}$ be the oracle queries made by $A$, and let
804 $y_0, y_1, \ldots, y_{q-1}$ be the corresponding responses.
806 Game~$\G2$ works in the same way as $\G0$, except that if there is a
807 \emph{collision} in the query replies (i.e., $y_i = y_j$ but $x_i \ne x_j$
808 for any $0 \le i, j < q$) then we stop the game immediately. Let $F_2$ be
809 the event that this occurs.
811 Because $\G2$ behaves exactly the same as $\G0$ unless $F_2$ occurs, we
812 must have
813 $\Pr[S_2 \land \lnot F_2] = \Pr[S_0 \land \lnot F_2]$
814 so we invoke Lemma~\ref{lem:shoup} and discover that
815 $|{\Pr[S_2]} - \Pr[S_0]| \le \Pr[F_2].$
816 Using the earlier result on collisions, it's easy to see that
817 $\Pr[F_2] \le \frac{q(q - 1)}{2^{L+1}}.$
818 \end{slide}
820 \begin{slide}
821 \head{PRPs are PRFs, \seq: proof (cont.)}
823 Game~$\G3$ works in the same way as $\G2$, except that we use a random
824 permutation $P \inr \Perm{L}$ instead of a random function $R \inr 825 \Func{L}{L}$. Firstly, note that $F_2$ can't occur in $\G3$. But, if
826 $F_2$ doesn't occur in $\G2$ (i.e., there is no collision), then the random
827 function is indistinguishable from a random permutation. So
828 $\Pr[S_3] = \Pr[S_2].$
830 By definition, we have
831 $\Adv{prp}{F}(A) = \Pr[S_1] - \Pr[S_3].$
832 We can now tie all of this together.
833 \end{slide}
835 \begin{slide}
836 \head{PRPs are PRFs, \seq: proof (cont.)}
838 A simple calculation shows that
839 \begin{eqnarray*}[rl]
840 \Adv{prf}{F}(A) &= \Pr[S_1] - \Pr[S_0] \\
841 &\le \Pr[S_1] - \Pr[S_2] + \Pr[F_2] \\
842 &= \Pr[S_1] - \Pr[S_3] + \Pr[F_2] \\
843 &= \Adv{prp}{F}(A) + \Pr[F_2] \\
844 &\le \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}}.
845 \end{eqnarray*}
846 In the second line, we used the bound we computed on the absolute
847 difference between $\Pr[S_2]$ and $\Pr[S_0]$; in the third, we noted that
848 $\Pr[S_2] = \Pr[S_3]$; in the fourth, we used the definition of advantage
849 against a PRP; and in the fifth we used the definition of insecurity for a
850 PRP.
851 \end{slide}
853 \begin{slide}
854 \head{PRPs are PRFs, \seq: proof (cont.)}
856 Finally, we imposed no restrictions on $A$, except that it run in time $t$
857 and make $q$ oracle queries. So our bound
858 $\Adv{prf}{F}(A) \le \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}}$%
859 is true for \emph{any} such adversary $A$, and in particular, it's true for
860 the most successful adversary running with those resource bounds.
862 Hence, we can maximize, showing that
863 $\InSec{prf}(F; t, q) \le 864 \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}}$%
865 as required.
866 \end{slide}
868 \begin{slide}
869 \topic{hash functions}
870 \resetseq
873 Hash functions like MD5 and SHA-1 are extremely useful primitives. What
874 properties do we expect of them? This out to be an extremely difficult
876 \begin{itemize}
877 \item One-wayness. We've seen a definition for this already. But it's not
878 enough.
879 \item Collision-resistance. This is the property usually claimed as the
880 requirement for use in digital signature systems. We'll look at this
881 later.
882 \item Randomness. What does this mean, when the function is completely
883 public? A distinguishability criterion is clearly hopeless.
884 \end{itemize}
885 \end{slide}
887 \begin{slide}
888 \head{Hash functions, \seq: Merkle-Damg\aa{}rd iterated hashing
889 \cite{Damgaard:1990:DPH, Merkle:1991:FSE}}
891 Let $F\colon \{0, 1\}^{k+L} \to \{0, 1\}^k$ be a \emph{compression}
892 function. Now consider the function $H\colon \{0, 1\}^* \to \{0, 1\}^k$
893 which transforms an input string $x$ as follows:
894 \begin{enumerate}
895 \item Pad $x$ to a multiple of $L$ bits in some injective way. Divide the
896 padded message into $L$-bit blocks $x_0$, $x_1$, \ldots, $x_{n-1}$.
897 \item Fix some $k$-bit constant $I$. Let $I_0 = I$. Define $I_{i+1} = 898 F(I_i \cat x_i)$ for $0 \le i < n$.
899 \item The result $H(x) = I_n$.
900 \end{enumerate}
902 Suppose we have two strings $x \ne y$, such that $H(x) = H(y)$; i.e., a
903 \emph{collision}. Then \emph{either} we can find a collision for $F$
904 \emph{or} a string $z$ for which $F(z) = I$. (This is why initialization
905 vectors for hash functions have such obviously regular forms.)
906 \end{slide}
908 \begin{proof}
909 Let $x_0, x_1, \ldots, x_{n-1}$ and $x'_0, x'_1, \ldots, x'_{n'-1}$ be
910 the $l$-bit blocks of two distinct (padded) messages, and without loss
911 of generality suppose that $n \ge n'$. Let $I_0 = I'_0 = I$, let
912 $I_{i+1} = F(I_i \cat x_i)$, and $I'_{i+1} = F(I'_i \cat x'_i)$. We
913 have $I_n = I'_{n'}$.
915 We prove the result by induction on $n$. The case $n = 0$ is trivially
916 true, since there is only one zero-block message. Suppose, then, that the
917 result is true for $n$-block messages. There are three cases to consider.
918 Firstly, if $n' = 0$ then $F(I_n \cat x_n) = I$. Secondly, if $I_n \ne 919 I'_{n'}$ or $x_n \ne x'_{n'}$, then we have a collision, for $F(I_n \cat 920 x_n) = I_n = I'_{n'} = F(I'_{n'} \cat x'_{n'})$. Finally, if $I_n = 921 I'_{n'}$ and $x_n = x'_{n'}$ then we remove the final block from both
922 messages, and because the remaining messages must differ in at least one
923 block, we can apply the inductive hypothesis on these shorter messages to
924 complete the proof.
925 \end{proof}
927 \begin{slide}
928 \head{Hash functions, \seq: Merkle-Damg\aa{}rd iterated hashing (cont.)}
930 \vfil
931 $\begin{graph} 932 []!{0; <2cm, 0cm>: <0cm, 0.9cm>::} 933 *+=(1, 0)+[F]{\mathstrut I_0 = I} :[d] *+[F]{F}="f" 934 [urrr] *+=(3, 0)+[F]{\mathstrut x_0} :d"f" "f" :[d] 935 *+=(1, 0)+[F]{\mathstrut I_1} :[d] *+[F]{F}="f" 936 [urrr] *+=(3, 0)+[F]{\mathstrut x_1} :d"f" "f" :@{-->}[dd] 937 *+=(1, 0)+[F]{\mathstrut I_{n-1}} :[d] *+[F]{F}="f" 938 [urrr] *+=(3, 0)+[F]{\mathstrut x_{n-1}} :d"f" "f" :[d] 939 *+=(1, 0)+[F:thicker]{\mathstrut H(x) = I_n} 940 \end{graph}$
941 \vfil
942 \end{slide}
944 \begin{slide}
945 \head{Hash functions, \seq: any-collision resistance}
947 The statement usually made about a good' hash function $h$ is that it
948 should be difficult' to find a collision: i.e., two preimages $x \ne y$
949 where $H(x) = H(y)$. How do we formalize this? Here's one attempt:
950 \begin{eqlines*}
951 \Succ{acr}{H}(A) = \Pr[(x, y) \gets A : x \ne y \land H(x) = H(y)]; \\
952 \InSec{acr}(H; t) = \max_A \Succ{acr}{H}(A).
953 \end{eqlines*}
954 But this doesn't work. There clearly \emph{exists} an adversary which
955 already knows' the a collision for $H$ and just outputs the right answer.
956 It succeeds very quickly, and with probability 1. So this definition is
957 impossible to satisfy.
958 \end{slide}
960 \begin{slide}
961 \head{Hash functions, \seq: targetted collision resistance}
963 The concept of targetted collision resistance is relatively new, but quite
964 promising. It replaces a single hash function with a \emph{family} of hash
965 functions. They're not really keyed, because the indices aren't kept
966 secret.
968 When making a signature, an index $i$ is chosen at random, and the
969 signature for message $m$ is formed over the pair $(i, H_i(M))$.
971 TCR-hash functions are the subject of ongoing research. No practical
972 designs exist at the moment.
973 \end{slide}
975 \begin{slide}
976 \head{Hash functions, \seq: targetted collision resistance (cont.)}
978 Consider the following experiment:
979 \begin{program}
980 $\Expt{tcr}{H}(A)$: \+ \\
981 $(x, s) \gets A(\cookie{find})$; \\
982 $i \getsr \keys H$; \\
983 $y \gets A(\cookie{collide}, i, s)$; \\
984 \IF $x \ne y \land H_i(x) = H_i(y)$
985 \THEN \RETURN $1$; \\
986 \ELSE \RETURN $0$;
987 \end{program}
988 The security of a TCR-hash function is measured as:
989 $\InSec{tcr}(H; t) = \max_A \Pr[\Expt{tcr}{H}(A) = 1]$
990 where the maximum is taken over all adversaries running in time $t$. We
991 define $(t, \epsilon)$-security as usual.
992 \end{slide}
994 \begin{slide}
995 \head{Hash functions, \seq: random oracles \cite{Bellare:1993:ROP}}
997 In practice, we expect much more than just collision resistance from hash
998 functions: we expect a certain amount of random' behaviour. But this is
999 hard to quantify.
1001 One approach is to model a hash function as a random oracle', i.e., an
1002 oracle containing a function chosen at random, used by the construction
1003 under consideration, and made available to the adversary. The idea is that
1004 reductions can capture' the knowledge of an adversary by examining the
1005 queries it makes to its random oracle.
1007 Hash functions \emph{aren't} random oracles. But a random oracle proof is
1008 better than nothing.
1009 \end{slide}
1011 \xcalways\subsection{Standard assumptions}\x
1013 \begin{slide}
1016 There are a number of standard' assumptions that are made about the
1017 difficulty of various problems:
1018 \begin{itemize}
1019 \item IFP, the Integer Factorization Problem;
1020 \item QRP, the Quadratic Residuosity Problem;
1021 \item DLP, the Discrete Logarithm Problem;
1022 \item RSAP, the RSA Problem; and
1023 \item CDH, the Computational Diffie-Hellman problem and its variants
1024 \end{itemize}
1025 \cite{Menezes:1997:HAC} has excellent material on the above.
1026 \end{slide}
1028 \begin{slide}
1029 \topic{integer factorization}
1030 \resetseq
1031 \head{The Integer Factorization Problem, \seq}
1033 We often assume that large integers of the form $n = p q$, where $p$ and
1034 $q$ are primes of roughly the same size, are hard' to factor.
1035 Specifically, there is no algorithm which will factor such an $n$ in time
1036 bounded by a polynomial function of $\log n$.
1038 The difficulty of various other problems, e.g., Quadratic Residuosity, or
1039 RSA, depend on the difficulty of factoring; however, it is not yet known
1040 whether the ability to solve QRP or RSAP can be used to factor.
1041 \end{slide}
1043 \begin{slide}
1044 \head{The Integer Factorization Problem, \seq: square roots}
1046 The problem of extracting square roots modulo $n = p q$ is provably as hard
1047 as factoring. This is the basis of Rabin's public key encryption and
1048 digital signature schemes. We shall analyse these later.
1050 Suppose $Q(n, y)$ is an algorithm which returns an $x$ such that $x^2 1051 \equiv y \pmod{n}$, provided such an $x$ exists. Then we can find a
1052 nontrivial factor of $n$ as follows:
1053 \begin{program}
1054 Algorithm $\id{find-factor}(n)$: \+ \\
1056 $x \getsr \{1, 2, \ldots, n - 1\}$; \\
1057 $y \gets x^2 \bmod n$; \\
1058 $x' \gets Q(n, y)$; \\
1059 $p \gets \gcd(x + x', n)$; \\
1060 \IF $p \notin \{1, n\}$ \THEN \RETURN $p$; \- \\
1061 \FOREVER;
1062 \end{program}
1063 \end{slide}
1065 \begin{proof}
1066 The program attempts to find two square roots of $y$ mod $n$. It's easy to
1067 see that this might lead to factors of $n$. If $x^2 \equiv x'^2 \pmod{n}$
1068 then $x^2 - x'^2 = k n$ for some constant $k$. Then $(x + x')(x - x')$ is
1069 a factorization of $k n$. It remains to prove the probability bound on $x 1070 + x'$ being a nontrivial factor of $n$.
1072 Let $n$ be an odd composite. Then, if $x \not\equiv \pm y \pmod{n}$ but
1073 $x^2 \equiv y^2 \pmod{n}$, then $\gcd(x + y, n)$ is a nontrivial factor of
1074 $n$.
1076 Firstly, we claim that, if $p$ is an odd prime then the congruence $x^2 1077 \equiv y \pmod{p}$ has precisely two solutions $x$, $x'$ such that $x 1078 \equiv -x' \pmod{p}$. Let $g$ be primitive mod $p$, with $x = g^\alpha$,
1079 $x' = g^\beta$. Then $g^{2 \alpha} \equiv g^{2 \beta} \pmod{p}$, so $2 1080 \alpha \equiv 2 \beta \pmod{p - 1}$. But $p - 1$ is even, by hypothesis,
1081 so $\alpha \equiv \beta \pmod{(p - 1)/2}$. But $g^{(p-1)/2} \equiv -1 1082 \pmod{p}$; hence $x \equiv \pm x' \pmod{p}$, proving the claim.
1084 There must exist odd primes $p$, $q$, such that $p|n$ and $q|n$, and $x 1085 \equiv -y \pmod{p}$ and $x \equiv y \pmod{q}$, for if not, then $x \equiv 1086 \pm y \pmod{n}$ contrary to hypothesis. But then $x + y \equiv 0 1087 \pmod{p}$, so $p|(x + y)$; but $x + y \equiv 2 x \not\equiv 0 \pmod{q}$,
1088 since $q$ is odd. Hence, $p$ divides $x + y$, but $q$ does not, so $\gcd(x 1089 + y, n)$ is a nontrivial factor of $n$, completing the proof.
1090 \end{proof}
1092 \begin{slide}
1096 If there is an $x$ such that $x^2 \equiv y \pmod{n}$ then $y$ is a
1097 \emph{quadratic residue modulo $n$}, and we write $y \in Q_n$; if there is
1098 no such $x$ then $y$ is a \emph{quadratic nonresidue modulo $n$}.
1100 If $p$ is prime, then we can use the \emph{Legendre symbol} to decide
1101 whether $x$ is a quadratic residue mod $p$:
1102 $\jacobi{x}{p} = x^{(p-1)/2} \bmod p = 1103 \begin{cases} 1104 0 & if p divides x \\ 1105 -1 & if x is a quadratic nonresidue mod p \\ 1106 +1 & if x is a quadratic residue mod p 1107 \end{cases}.$%
1108 The \emph{Jacobi symbol} (written the same way) is defined for odd~$n$: if
1109 $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ where the $p_i$ are prime, then
1110 $\jacobi{x}{n} = 1111 \jacobi{x}{p_1}^{a_1} \jacobi{x}{p_2}^{a_2} \cdots 1112 \jacobi{x}{p_k}^{a_k}.$%
1113 This can be efficiently computed without knowledge of the factors of $n$
1114 \cite[Section~2.4.5]{Menezes:1997:HAC}.
1115 \end{slide}
1117 \begin{slide}
1120 If $\jacobi{x}{n} = -1$ then $x$ is certainly \emph{not} a quadratic
1121 residue mod $n$; however, if $\jacobi{x}{n} = 1$ then $x$ might be a
1122 quadratic residue or it might not; if not, then we say that $x$ is a
1123 \emph{pseudosquare}.
1125 If $n = p q$ is a product of two primes and $x \inr (\Z/n\Z)^*$ is chosen
1126 at random, then
1127 $\Pr\Bigl[x \in Q_n \Bigm| \jacobi{x}{n} = 1\Bigr] = \frac{1}{2},$
1128 since we have
1129 $\jacobi{x}{p} = \jacobi{x}{q} = \pm 1$
1130 with each occurring with equal probability.
1132 The problem of distinguishing pseudosquares from quadratic residues is
1133 called the Quadratic Residuosity Problem (QRP). It is not known how to
1134 solve this problem without factoring $n$.
1135 \end{slide}
1137 \begin{slide}
1138 \topic{discrete logarithms}
1141 The (Integer) Discrete Logarithm Problem asks for the solution $x$ given a
1142 congruence of the form $g^x \equiv y \pmod{n}$. This seems to be about as
1143 difficult as factoring. (The ability to solve discrete logs modulo $n$ is
1144 sufficient to factor $n$. The best known algorithms for IFP and DLP have
1145 the same running time.)
1147 The problem generalizes to other cyclic groups, e.g., elliptic curves over
1148 finite fields.
1149 \end{slide}
1151 \begin{slide}
1152 \topic{self-reducibility}
1153 \resetseq
1156 The problems of square-root extraction, deciding quadratic residuosity, the
1157 RSA problem, and finding discrete logarithms share the property of being
1158 \emph{randomly self-reducible}; i.e., an instance of the problem can be
1159 transformed into many different derived instances \emph{without skewing the
1160 probability distribution of problem instances}, such that a solution to
1161 one of the derived instances yields a solution to the original one.
1163 This is a good property to have. It implies that most' problem instances
1164 are as hard as the hardest instances.
1165 \end{slide}
1167 \begin{slide}
1168 \head{Self-reducibility, \seq: the RSA problem \cite{Rivest:1978:MOD}}
1170 The RSA problem is to compute $e$-th roots modulo $n = p q$, where $e$ is
1171 relatively prime to $n$. Suppose that the algorithm $S(n, e, y)$ returns a
1172 value $x$ such that $x^e \equiv y \pmod{n}$ for `many' choices of $y$, or
1173 the special symbol $\bot$ otherwise. The following probabilistic algorithm
1174 then solves the RSA problem for arbitrary $y$:
1175 \begin{program}
1176 Algorithm $\id{solve-rsa}(n, e, y)$: \+ \\
1178 $x' \getsr \{1, 2, \ldots, n - 1\}$; \\
1179 \IF $\gcd(x', n) = 1$ \THEN \\ \quad\=\+\kill
1180 $y' \gets y x'^e \bmod n$; \\
1181 $x \gets S(n, e, y')$; \\
1182 \IF $x \ne \bot$ \THEN \RETURN $x x'^{-1} \bmod n$; \-\- \\
1183 \FOREVER;
1184 \end{program}
1185 \end{slide}
1187 \begin{slide}
1188 \topic{the Diffie-Hellman problem}
1191 Let $G = \langle g \rangle$ be a cyclic group or order $q$. Let $\alpha$
1192 and $\beta$ be indices, $\alpha, \beta \in \Z/q\Z$.
1194 The (computational) \emph{Diffie-Hellman} problem is, given $g^\alpha$ and
1195 $g^\beta$, to find $g^{\alpha\beta}$.
1197 The (computational) Diffie-Hellman \emph{assumption} is that there is no
1198 probabilistic algorithm which solves the computational Diffie-Hellman
1199 problem in time polynomial in $\log q$.
1201 Obviously, being able to compute discrete logs in $G$ efficiently would
1202 yield a solution to the Diffie-Hellman problem. But it may be the case
1203 that the Diffie-Hellman problem is easier than the discrete log problem.
1205 The Diffie-Hellman problem is self-reducible.
1206 \end{slide}
1208 \begin{slide}
1209 \head{The Decisional Diffie-Hellman assumption \cite{Boneh:1998:DDP}}
1211 The computational Diffie-Hellman assumption makes a statement only about
1212 algorithms which compute the \emph{entire} answer $g^{\alpha\beta}$. Since
1213 Diffie-Hellman is frequently used for key-exchange, what can we say about
1214 the ability of an adversary to guess any of the bits?
1216 The Decisional Diffie-Hellman (DDH) assumption asserts that, if you don't
1217 know $\alpha$ or $\beta$, then it's hard to tell $g^{\alpha\beta}$ from a
1218 random element of $G$; that is, that the distributions of the following
1219 experiments are computationally indistinguishable:
1220 \begin{program}
1221 $\alpha \getsr \Z/q\Z;$ \\
1222 $\beta \getsr \Z/q\Z;$ \\
1223 \RETURN $(g^\alpha, g^\beta, g^{\alpha\beta})$;
1224 \next
1225 $\alpha \getsr \Z/q\Z;$ \\
1226 $\beta \getsr \Z/q\Z;$ \\
1227 $\gamma \getsr \Z/q\Z;$ \\
1228 \RETURN $(g^\alpha, g^\beta, g^\gamma)$;
1229 \end{program}
1230 \end{slide}
1232 \begin{slide}
1233 \head{The Decisional Diffie-Hellman assumption (cont.)}
1235 If $A$ is an algorithm attempting to solve DDH in the group $G$, then we
1237 \begin{eqnarray*}[rl]
1239 & \Pr[\alpha \getsr \Z/q\Z; \beta \getsr \Z/q\Z :
1240 A(g^\alpha, g^\beta, g^{\alpha\beta}) = 1] - {} \\
1241 & \Pr[\alpha \getsr \Z/q\Z; \beta \getsr \Z/q\Z;
1242 \gamma \getsr \Z/q\Z :
1243 A(g^\alpha, g^\beta, g^\gamma) = 1]
1244 \end{eqnarray*}
1245 and the insecurity of DDH in $G$ as
1246 $\InSec{ddh}(G; t) = \max_A \Adv{ddh}{G}(A)$
1247 with the maximum over all algorithms $A$ running in time $t$.
1248 \end{slide}
1250 \begin{slide}
1251 \head{The Decisional Diffie-Hellman assumption (cont.)}
1253 If you can solve the computational Diffie-Hellman problem, you can solve
1254 the decisional version. If you can compute discrete logs, you can solve
1255 both.
1257 There \emph{are} groups in which the computation problem is (believed to
1258 be) hard, but the decisional problem is easy. In particular, if the group
1259 order $q$ has small factors then the decisional problem isn't hard.
1260 \end{slide}
1262 \endinput
1264 %%% Local Variables:
1265 %%% mode: latex
1266 %%% TeX-master: "ips"
1267 %%% End: