\topic{serious message}
\head{Cryptography is elephant powder}
- So, what can we do about the situtation?
+ So, what can we do about the situation?
\begin{itemize}
\item Design simple cryptographic primitives, e.g., block ciphers, hash
functions. Develop techniques for analysing them, and attempt to stay
\begin{slide}
\topic{the asymptotic approach}
- \head{The asymptotic approach, 1}
+ \resetseq
+ \head{The asymptotic approach, \seq}
A function $\nu\colon \N \to \R$ is \emph{negligible} if, for any integer
$c$, there exists an $n \in \N$ such that $0 \le \nu(k) < k^{-c}$ for all
\end{slide}
\begin{slide}
- \head{The asymptotic approach, 2}
+ \head{The asymptotic approach, \seq}
Suppose we build an encryption scheme from a one-way function. We'd like
to prove that the encryption is good if the one-way function is secure. We
\begin{slide}
\topic{boolean operators}
- \head{Notation, 1: boolean operators}
+ \resetseq
+ \head{Notation, \seq: boolean operators}
If $P$ and $Q$ are \emph{predicates} -- i.e., either true or false -- then:
\begin{itemize}
\begin{slide}
\topic{sets}
- \head{Notation, 2: sets}
+ \head{Notation, \seq: sets}
For our purposes, we can think of sets as being collections of objects.
\cap Y$), union ($X \cup Y$) and subset containment ($X \subseteq Y$). The
\emph{empty set}, which contains no elements, is written $\emptyset$.
- The notation $\{f(x) \mid P(x)\}$ describes the set containing those items
- $f(x)$ for which the predicate $P(x)$ is true.
+ The notation $\{\, f(x) \mid P(x) \,\}$ describes the set containing those
+ items $f(x)$ for those $x$ for which the predicate $P(x)$ is true.
The \emph{cardinality} $|X|$ of a (finite) set $X$ is the number of
elements in the set.
The power set $\powerset(X)$ of a set $X$ is the set of all subsets of $X$.
+
+ The \emph{Cartesian product} of two sets $X \times Y$ is the set of all
+ ordered pairs $\{\, (x, y) \mid x \in X \land y \in Y \,\}$. We use
+ exponents to indicate the product of a set with itself: hence, $X^2 = X
+ \times X$.
+
+ A \emph{relation} $R$ is a subset of a Cartesian product. We write $R(x,
+ y)$ if $(x, y) \in R$. Relations between two sets are often written as
+ infix symbols: e.g., $x \sim y$.
\end{slide}
\begin{slide}
- \head{Notation, 3: sets (cont.)}
-
- The \emph{cartesian product} of two sets $X \times Y$ is the set of all
- ordered pairs $\{ (x, y) \mid x \in X \land y \in Y \}$. We use exponents
- to indicate the product of a set with itself: hence, $X^2 = X \times X$.
+ \head{Notation, \seq: sets (cont.)}
- A \emph{relation} $R$ is a subset of a cartesian product. We write $R(x,
- y)$ if $(x, y) \in R$. Relations between two sets are often written as
- infix symbols: e.g., $x \sim y$.
+ In addition to strings, defined later, we use the following standard sets:
+ \begin{itemize}
+ \item the set $\Z$ of integers;
+ \item the set $\N = \{\, x \in \Z \mid x \ge 0 \,\}$ of natural numbers;
+ \item the set $\R$ of real numbers;
+ \item closed intervals $[a, b] = \{\, x \in \R \mid a \le x \le b \,\}$;
+ \item the finite field $\F_q$ of $q$ elements, and its multiplicative
+ subgroup $\F_q^* = \F_q \setminus \{0\}$; and
+ \item the ring $\Z/n\Z$ of residue classes modulo $n$ (i.e., if $x \in
+ \Z/n\Z$ and $a, b \in x$ then $a \equiv b \pmod{n}$), and its
+ multiplicative subgroup $(\Z/n\Z)^* = \Z/n\Z - \{\, x + n\Z \mid \gcd(x,
+ n) > 1 \,\}$.
+ \end{itemize}
\end{slide}
\begin{slide}
\topic{functions}
- \head{Notation, 4: functions}
+ \head{Notation, \seq: functions}
A \emph{function} $f\colon X \to Y$ is a mapping which assigns every
element $x$ in the \emph{domain} $X$ a corresponding element $f(x)$ in the
\emph{onto}). If $f$ is both injective and surjective then we say that it
is \emph{bijective}. In this case, there is a well-defined inverse
$f^{-1}\colon Y \to X$ defined by $f(f^{-1}(y)) = y$ for all $y \in Y$.
+
+ If $f\colon X \to X$ (i.e., its domain and range are the same set) is
+ bijective, then we say that $f$ is a \emph{permutation on $X$}.
\end{slide}
\begin{slide}
- \head{Notation, 5: functions (cont.)}
+ \head{Notation, \seq: functions (cont.)}
We can consider a function $f\colon X \to Y$ to be a particular sort of
relation $f \subseteq X \times Y$, subject to the constraint that if $(x,
\begin{slide}
\topic{strings}
- \head{Notation, 6: strings}
+ \head{Notation, \seq: strings}
An \emph{alphabet} is a finite set of \emph{symbols}. The one we'll use
most of the time is the set $\Sigma = \{0, 1\}$ of \emph{bits}.
Suppose $A$ is an alphabet. The set of sequences of exactly $n$ symbols
from $A$ is written $A^n$. Hence, $\{0, 1\}^{64}$ is the set of all 64-bit
sequences. The set of (finite) \emph{strings} over an alphabet $A$ is $A^*
- = \bigcup_{i \in \N} A^n$. The empty string is named $\emptystring$.
+ = \bigcup_{i \in \N} A^i$. The empty string is named $\emptystring$.
The \emph{length} of a string $a \in A^*$, written $|a|$, is the natural
number $n$ where $a \in A^n$.
\end{slide}
\begin{slide}
- \head{Notation, 7: strings (cont.)}
+ \head{Notation, \seq: strings (cont.)}
- There are natural (bijective) mappings between bit strings and natual
+ There are natural (injective) mappings between bit strings and natural
numbers.
If $x = x_0 x_1 \ldots x_{n-1} \in \{0, 1\}^*$ then we can associate with
It doesn't matter which you choose, as long as you're consistent.
For simplicity's sake, we shall tend to switch between strings and the
- numbers (and occasionally more exotic objects) they represent implictly.
+ numbers (and occasionally more exotic objects) they represent implicitly.
\end{slide}
\begin{slide}
\topic{parsing}
- \head{Notation, 8: parsing}
+ \head{Notation, \seq: parsing}
We'll find it useful to be able to break up strings in the algorithms we
present. We use the statement
\begin{slide}
\topic{vectors}
- \head{Notation, 9: vectors}
+ \head{Notation, \seq: vectors}
A \emph{vector} $\vect{x}$ is a finite ordered collection of elements from
some set $X$. If $\vect{x}$ contains $n$ elements then we write $\vect{x}
\in X^n$, and that $|\vect{x}| = n$. We write the individual elements as
$\vect{x}[0], \vect{x}[1], \ldots, \vect{x}[n - 1]$.
- We shall use set membership notation for vectors; i.e., we write $x \in
+ We shall abuse set membership notation for vectors; i.e., we write $x \in
\vect{x}$ if there is an $i$ ($0 \le i < |\vect{x}|$) such that
$\vect{x}[i] = x$.
\begin{slide}
\topic{distributions and randomness}
- \head{Notation, 10: distributions and randomness}
+ \head{Notation, \seq: distributions and randomness}
A \emph{probability distribution} over a (countable) set $X$ is a
function $\mathcal{D}\colon X \to [0, 1]$ such that
\begin{slide}
\topic{distinguishability}
- \head{Distinguishability, 1}
+ \resetseq
+ \head{Distinguishability, \seq}
Suppose that $\mathcal{X}$ and $\mathcal{Y}$ are two probability
distributions.
-
+
Let $X$ be a random variable distributed according to $\mathcal{X}$, and
let $Y$ be a random variable distributed according to $\mathcal{Y}$. We
- say that $\mathcal{A}$ and $\mathcal{B}$ are \emph{identically
- distributed} if, for all possible values $x$ of $X$, we have
+ say that $\mathcal{X}$ and $\mathcal{Y}$ are \emph{identically
+ distributed}, and write that $\mathcal{X} \equiv \mathcal{Y}$, if, for
+ all possible values $x$ of $X$, we have
\[ \Pr[X = x] = \Pr[Y = x]. \]
Equivalently, we require that, for all $x \in \supp \mathcal{X}$ we have
\end{slide}
\begin{slide}
- \head{Distinguishability, 2: statistical closeness}
+ \head{Distinguishability, \seq: statistical closeness}
Now we generalize the setting slightly. Consider two \emph{families} of
- distributions, $\{\mathcal{X}_k\}_{k \in \N}$ and $\{\mathcal{Y}_k\}_{k \in
- \N}$, parameterized by a security parameter $k$.
+ distributions, $\{\mathcal{X}_k\}_{k\in\N}$ and
+ $\{\mathcal{Y}_k\}_{k\in\N}$, parameterized by a security parameter $k$,
+ where $\dom\mathcal{X}_k = \dom\mathcal{Y}_k$. To make the asymptotics
+ work, we require that $|x| \le p(k)$ for some polynomial $p(\cdot)$, for
+ all $x \in \dom\mathcal{X}_k$.
Fix a value of $k$. Again, let $X$ be distributed according to
$\mathcal{X}_k$, and let $Y$ be distributed according to $\mathcal{Y}_k$.
- We say that $\{\mathcal{X}_k\}_{k \in \N}$ and $\{\mathcal{Y}_k\}_{k \in
- \N}$ are \emph{statistically close} if there is a negligible function
- $\nu(\cdot)$ such that for any $k \in \N$, and for all $x \in
- \supp \mathcal{X}_k$,
- \[ |{\Pr[X = x]} - \Pr[Y = x]| \le \nu(k). \]
-
+ We say that $\{\mathcal{X}_k\}_{k \in \N}$ and $\{\mathcal{Y}_k\}_{k\in\N}$
+ are \emph{statistically close}, and write that $\{\mathcal{X}_k\}_{k\in\N}
+ \statclose \{\mathcal{Y}_k\}_{k\in\N}$, if there is a negligible function
+ $\nu(\cdot)$ such that, for any $k \in \N$,
+ \[ \sum_{x\in\dom{\mathcal{X}_k}}
+ |{\Pr[X = x]} - \Pr[Y = x]| \le \nu(k). \]%
(Reminder: Saying that $\nu\colon \N \to \R$ is \emph{negligible} means
that, for any $c \in \Z$ there is an $n \in N$ such that $\nu(k) <
k^{-c}$.)
\end{slide}
\begin{slide}
- \head{Distinguishability, 3: computational indistinguishability}
+ \head{Distinguishability, \seq: computational indistinguishability}
We say that two families of distributions are computationally
indistinguishable if no `efficient' algorithm can tell them apart with
better than `negligible' probability.
- So, we say that $\{\mathcal{X}_k\}_{k \in \N}$ and $\{\mathcal{Y}_k\}_{k
- \in \N}$ are \emph{computationally indistinguishable} if, for any
- probabilistic polynomial-time algorithm $A$, there is a negligible function
- $\nu(\cdot)$ such that, for any $k$:
+ So, we say that $\{\mathcal{X}_k\}_{k\in\N}$ and
+ $\{\mathcal{Y}_k\}_{k\in\N}$ are \emph{computationally indistinguishable}
+ and write that $\{\mathcal{X}_k\}_{k\in\N} \compind
+ \{\mathcal{Y}_k\}_{k\in\N}$, if, for any probabilistic polynomial-time
+ algorithm $A$, there is a negligible function $\nu(\cdot)$ such that, for
+ any $k$:
\[ \Pr[x \getsr \mathcal{X}_k; b \gets A(x) : b = 1] -
- \Pr[x \getsr \mathcal{Y}_k; b \gets A(x) : b = 1] \le \nu(k). \]%
+ \Pr[y \getsr \mathcal{Y}_k; b \gets A(y) : b = 1] \le \nu(k). \]%
+ Statistical closeness implies computational indistinguishability.
\end{slide}
+\begin{proof}
+ Let two statistically close distributions $\{\mathcal{X}_k\}_{k\in\N}
+ \statclose \{\mathcal{Y}_k\}_{y\in\N}$ be given. Fix some $k$, and let $Z
+ = \dom\mathcal{X}_k = \dom\mathcal{Y}_k$. Now note that the adversary's
+ advantage is given by $\sum_{z\in Z} \Pr[b \gets A(z) : b = 1]
+ |\mathcal{X}_k(z) - \mathcal{Y}_k(z)| \le \sum_{z\in Z} |\mathcal{X}_k(z) -
+ \mathcal{Y}_k(z)| \le \nu(k)$. Hence the two distributions are
+ computationally indistinguishable.
+\end{proof}
+
\begin{slide}
\topic{collisions}
- \head{Collisions}
+ \head{Collisions -- the Birthday `paradox'}
Suppose we throw $q$ balls into $n$ bins at random (with $q \le n$). Let
$C_{q, n}$ be the event that, at the end of this, we have a bin containing
\begin{eqnarray*}[rl]
\Pr[C_{q, n}]
&\le \Pr[B_{2, n}] + \Pr[B_{3, n}] + \cdots + \Pr[B_{q, n}] \\
- &= \frac{1}{n} + \frac{2}{n} + \cdots + \frac{q - 1}{n} \\
- &= \frac{q(q - 1)}{2 n}.
+ &\le \frac{1}{n} + \frac{2}{n} + \cdots + \frac{q - 1}{n} \\
+ &= \frac{q(q - 1)}{2 n}.
\end{eqnarray*}
This is an extremely useful result, and we shall need it often.
\end{slide}
\begin{slide}
\topic{one-way functions}
- \head{One-way functions, 1: introduction}
+ \resetseq
+ \head{One-way functions, \seq: introduction}
Intuition: a one-way function is easy to compute but hard to invert.
\end{slide}
\begin{slide}
- \head{One-way functions, 2: formalism}
+ \head{One-way functions, \seq: formalism}
The \emph{success probability} of an inverter $I$ against the function $f$
is
\end{slide}
\begin{slide}
- \head{One-way functions, 3: trapdoors}
+ \head{One-way functions, \seq: trapdoors}
Intuition: a \emph{trapdoor} is secret information which makes inverting a
- one-way function easy. A trapdoor one-way function generator $\mathcal{T}
- = (G, f, T)$ is a triple of algorithms:
+ one-way function easy. This is most useful when the one-way function is a
+ permutation. A trapdoor one-way function generator $\mathcal{T} = (G, f,
+ T)$ is a triple of algorithms:
\begin{itemize}
\item The probabilistic algorithm $G$ is given some parameter $k$ and
one-way function.
\item The algorithm $T$ inverts $f$ using the trapdoor information. That
- is, if $(P, K) \in G(k)$ and $y = f_P(x)$ for some $x$, then $x =
- T(K, y)$. We usually write $T_K(\cdot)$ instead of $T(K, \cdot)$.
+ is, if $(P, K) \in G(k)$ and $y = f_P(x)$ for some $x$, then $y =
+ f_P(T(K, y))$. We usually write $T_K(\cdot)$ instead of $T(K, \cdot)$.
\end{itemize}
\end{slide}
A \emph{pseudorandom function family} (PRF) is a collection of functions
$F_K\colon \{0, 1\}^l \to \{0, 1\}^L$, where $K$ is some index, typically
- from a set of fixed-size strings $\{0, 1\}^k$.
+ from a set of fixed-size strings $\{0, 1\}^k$. We shall often consider a
+ PRF to be a single function $F\colon \{0, 1\}^k \times \{0, 1\}^l \to \{0,
+ 1\}^L$.
We want to say that $F$ is a strong PRF if adversaries find it hard to
distinguish an instance $F_K$ from a function chosen completely at random
\end{slide}
\begin{slide}
- \head{Pseudorandomness, 3: PRFs (cont.)}
+ \head{Pseudorandom functions (cont.)}
We define the advantage of a distinguisher $D$ against the PRF $F$ as
follows:
\begin{slide}
\topic{pseudorandom permutations (PRPs)}
\head{Pseudorandom permutations (PRPs)}
-
+
We define a \emph{pseudorandom permutation family} (PRP) in a similar way
- to the PRFs we've already seen. Suppose $F_K\colon \{0, 1\}^L \to \{0,
- 1\}^L$ is a family of permutations, indexed by elements of some finite set,
- e.g., $\{0, 1\}^k$. Let $\Perm{L}$ be the set of \emph{all} permutations
- over the set of $L$-bit strings $\{0, 1\}^L$.
+ to the PRFs we've already seen. A PRP is a family $F_K\colon \{0, 1\}^L
+ \to \{0, 1\}^L$ is a of permutations, indexed by elements of some finite
+ set, e.g., $\{0, 1\}^k$. We shall often consider a PRP to be a single
+ function $F\colon \{0, 1\}^k \times \{0, 1\}^l \to \{0, 1\}^L$.
+
+ Let $\Perm{L}$ be the set of \emph{all} permutations over the set of
+ $L$-bit strings $\{0, 1\}^L$.
The advantage of a distinguisher $D$ against the PRP $F$ is
\begin{eqnarray*}[rl]
\end{slide}
\begin{slide}
- \head{Pseudorandomness, 5: super PRPs}
+ \head{Super pseudorandom permutations}
PRPs are bijective. A \emph{super PRP} is a PRP which remains secure when
the distinguisher is allowed to make inverse queries:
\begin{eqnarray*}[rl]
\Adv{sprp}{F}(D) = &
- \Pr[D^{F_K(\cdot), F_K^{-1}(\cdot)} = 1 \mid
- K \getsr \{0, 1\}^k] - {} \\
+ \Pr[K \getsr \{0, 1\}^k : D^{F_K(\cdot), F_K^{-1}(\cdot)} = 1] - {} \\
& \Pr[R \getsr \Perm{L} : D^{R(\cdot), R^{-1}(\cdot)} = 1].
\end{eqnarray*}
Since there are two oracles, we count queries to both when evaluating the
\end{exercise}
\begin{slide}
- \head{Block ciphers: PRPs are PRFs}
+ \resetseq
+ \head{PRPs are PRFs, \seq}
We model block ciphers as families of PRPs (not super PRPs). Most of the
analysis works best on PRFs, though. We show that a PRP makes a `pretty
This is a useful result. As long as $q^2$ is small compared to $2^L$ --
the block size -- then a PRP makes a good PRF.
- The value $2^{L/2}$ is often called the \emph{Birthday bound} (after the
- birthday `paradox'). We shall meet it often when we examine modes of
- operation.
+ The value $2^{L/2}$ is often called the \emph{Birthday bound}. We shall
+ meet it often when we examine modes of operation. We shall examine the
+ proof, because it illustrates some useful techniques.
\end{slide}
-\begin{proof}
- Let $F$ be a PRP family, and $K$ a randomly chosen key from the keyspace of
- $F$; let $R \inr \Func{L}{L}$ be a random function, and let $P \inr
- \Perm{L}$ be a random permutation.
+\begin{slide}
+ \head{Shoup's lemma}
+
+ This handy lemma states that the difference in the probability of some
+ outcome between the two games is bounded above by the probability that the
+ games differ.
+
+ \begin{lemma}[Shoup \cite{Shoup:2001:OAEPR}]
+ \label{lem:shoup}
+ If $X$, $Y$ and $F$ are events, and $\Pr[X \land \lnot F] = \Pr[Y \land
+ \lnot F]$ then $|{\Pr[X]} - \Pr[Y]| \le \Pr[F]$.
+ \end{lemma}
+ \begin{proof}
+ We have:
+ \begin{eqnarray*}[rll]
+ \Pr[X] &= \Pr[X \land F] &+ \Pr[X \land \lnot F] \\
+ \Pr[Y] &= \Pr[Y \land F] &+ \Pr[Y \land \lnot F]
+ \end{eqnarray*}
+ Subtracting gives
+ \[ |{\Pr[X]} - \Pr[Y]| = |{\Pr[X \land F]} -
+ \Pr[Y \land F]| \le \Pr[F] \]%
+ as required.
+ \end{proof}
+\end{slide}
+
+\begin{slide}
+ \head{PRPs are PRFs, \seq: proof}
+
+ Let $F\colon \{0, 1\}^k \times \{0, 1\}^L \to \{0, 1\}^L$ be a pseudorandom
+ permutation. We aim to show that $F$ is also a pseudorandom function.
- Let $A$ be any distinguisher running in time $t$, and making $q$ oracle
- queries. Then:
- \begin{eqnarray*}[rl]
- \Adv{prf}{F}(A)
- & = \Pr[A^{F_K(\cdot)} = 1] - \Pr[A^{R(\cdot)} = 1] \\
- & = \Pr[A^{F_K(\cdot)} = 1] - \Pr[A^{P(\cdot)} = 1] +
- \Pr[A^{P(\cdot)} = 1] - \Pr[A^{R(\cdot)} = 1] \\
- & = \Adv{prp}{F}(A) + \Pr[A^{P(\cdot)} = 1] - \Pr[A^{R(\cdot)} = 1] \\
- & = \Adv{prp}{F}(A) + \Pr[A^{R(\cdot)} = 0] - \Pr[A^{P(\cdot)} = 0].
- \end{eqnarray*}
- Now we need to bound the quantity $\Pr[A^{R(\cdot)} = 0] - \Pr[A^{P(\cdot)}
- = 0]$. Let $D$ be the event that all of the \emph{distinct} oracle queries
- to $R$ yield distinct results. Then
+ Let $A$ be an adversary which distinguishes~$F$ from a pseudorandom
+ function in time~$t$, after making $q$ oracle queries. We consider a
+ sequence of games $\G{i}$ played with the adversary. In each game $\G{i}$,
+ let $S_i$ be the event that the adversary returns~$1$ at the end of the
+ game.
+
+ Game~$\G0$ is the `random function' game. We given $A$ an oracle
+ containing a random function $R \inr \Func{L}{L}$.
+
+ Game~$\G1$ is the `PRF' game. We give $A$ an oracle which computes
+ $F_K(\cdot)$ for some randomly chosen $K \inr \{0, 1\}^k$.
+
+ By definition, then,
+ \[ \Adv{prf}{F}(A) = \Pr[S_1] - \Pr[S_0]. \]
+\end{slide}
+
+\begin{slide}
+ \head{PRPs are PRFs, \seq: proof (cont.)}
+
+ Let $x_0, x_1, \ldots, x_{q-1}$ be the oracle queries made by $A$, and let
+ $y_0, y_1, \ldots, y_{q-1}$ be the corresponding responses.
+
+ Game~$\G2$ works in the same way as $\G0$, except that if there is a
+ \emph{collision} in the query replies (i.e., $y_i = y_j$ but $x_i \ne x_j$
+ for any $0 \le i, j < q$) then we stop the game immediately. Let $F_2$ be
+ the event that this occurs.
+
+ Because $\G2$ behaves exactly the same as $\G0$ unless $F_2$ occurs, we
+ must have
+ \[ \Pr[S_2 \land \lnot F_2] = \Pr[S_0 \land \lnot F_2] \]
+ so we invoke Lemma~\ref{lem:shoup} and discover that
+ \[ |{\Pr[S_2]} - \Pr[S_0]| \le \Pr[F_2]. \]
+ Using the earlier result on collisions, it's easy to see that
+ \[ \Pr[F_2] \le \frac{q(q - 1)}{2^{L+1}}. \]
+\end{slide}
+
+\begin{slide}
+ \head{PRPs are PRFs, \seq: proof (cont.)}
+
+ Game~$\G3$ works in the same way as $\G2$, except that we use a random
+ permutation $P \inr \Perm{L}$ instead of a random function $R \inr
+ \Func{L}{L}$. Firstly, note that $F_2$ can't occur in $\G3$. But, if
+ $F_2$ doesn't occur in $\G2$ (i.e., there is no collision), then the random
+ function is indistinguishable from a random permutation. So
+ \[ \Pr[S_3] = \Pr[S_2]. \]
+
+ By definition, we have
+ \[ \Adv{prp}{F}(A) = \Pr[S_1] - \Pr[S_3]. \]
+ We can now tie all of this together.
+\end{slide}
+
+\begin{slide}
+ \head{PRPs are PRFs, \seq: proof (cont.)}
+
+ A simple calculation shows that
\begin{eqnarray*}[rl]
- \Pr[A^{R(\cdot)} = 0]
- & = \Pr[A^{R(\cdot)} = 0 \mid D] \Pr[D] +
- \Pr[A^{R(\cdot)} = 0 \mid \lnot D] \Pr[\lnot D] \\
- & = \Pr[A^{P(\cdot)} = 0] \Pr[D] +
- \Pr[A^{R(\cdot)} = 0 \mid \lnot D] \Pr[\lnot D] \\
- & \le \Pr[A^{P(\cdot)} = 0] + \Pr[\lnot D] \\
- & \le \Pr[A^{P(\cdot)} = 0] + \frac{q(q - 1)}{2^{L+1}}.
+ \Adv{prf}{F}(A) &= \Pr[S_1] - \Pr[S_0] \\
+ &\le \Pr[S_1] - \Pr[S_2] + \Pr[F_2] \\
+ &= \Pr[S_1] - \Pr[S_3] + \Pr[F_2] \\
+ &= \Adv{prp}{F}(A) + \Pr[F_2] \\
+ &\le \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}}.
\end{eqnarray*}
- Substituting this into the above equation yields
- \[ \Adv{prf}{F}(A) \le \Adv{prp}{F}(A) + \frac{q(q - 1)}{2^{L+1}}. \]
- Select $A$ such that $\Adv{prf}{F}(A) = \InSec{prf}(F; t, q)$. We know
- $\Adv{prp}{F}(A) \le \InSec{prp}(F; t, q)$ by definition. The result
- follows.
-\end{proof}
+ In the second line, we used the bound we computed on the absolute
+ difference between $\Pr[S_2]$ and $\Pr[S_0]$; in the third, we noted that
+ $\Pr[S_2] = \Pr[S_3]$; in the fourth, we used the definition of advantage
+ against a PRP; and in the fifth we used the definition of insecurity for a
+ PRP.
+\end{slide}
+
+\begin{slide}
+ \head{PRPs are PRFs, \seq: proof (cont.)}
+
+ Finally, we imposed no restrictions on $A$, except that it run in time $t$
+ and make $q$ oracle queries. So our bound
+ \[ \Adv{prf}{F}(A) \le \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}} \]%
+ is true for \emph{any} such adversary $A$, and in particular, it's true for
+ the most successful adversary running with those resource bounds.
+
+ Hence, we can maximize, showing that
+ \[ \InSec{prf}(F; t, q) \le
+ \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}} \]%
+ as required.
+\end{slide}
\begin{slide}
\topic{hash functions}
- \head{Hash functions, 1: properties}
+ \resetseq
+ \head{Hash functions, \seq: properties}
Hash functions like MD5 and SHA-1 are extremely useful primitives. What
properties do we expect of them? This out to be an extremely difficult
\end{slide}
\begin{slide}
- \head{Hash functions, 2: Merkle-Damg\aa{}rd iterated hashing
+ \head{Hash functions, \seq: Merkle-Damg\aa{}rd iterated hashing
\cite{Damgaard:1990:DPH, Merkle:1991:FSE}}
Let $F\colon \{0, 1\}^{k+L} \to \{0, 1\}^k$ be a \emph{compression}
\begin{enumerate}
\item Pad $x$ to a multiple of $L$ bits in some injective way. Divide the
padded message into $L$-bit blocks $x_0$, $x_1$, \ldots, $x_{n-1}$.
- \item Fix some $L$-bit constant $I$. Let $I_0 = I$. Define $I_{i+1} =
+ \item Fix some $k$-bit constant $I$. Let $I_0 = I$. Define $I_{i+1} =
F(I_i \cat x_i)$ for $0 \le i < n$.
\item The result $H(x) = I_n$.
\end{enumerate}
\end{proof}
\begin{slide}
- \head{Hash functions, 2: any-collision resistance}
+ \head{Hash functions, \seq: any-collision resistance}
The statement usually made about a `good' hash function $h$ is that it
should be `difficult' to find a collision: i.e., two preimages $x \ne y$
\end{slide}
\begin{slide}
- \head{Hash functions, 3: targetted collision resistance}
+ \head{Hash functions, \seq: targetted collision resistance}
The concept of targetted collision resistance is relatively new, but quite
promising. It replaces a single hash function with a \emph{family} of hash
\end{slide}
\begin{slide}
- \head{Hash functions, 4: targetted collision resistance (cont.)}
+ \head{Hash functions, \seq: targetted collision resistance (cont.)}
Consider the following experiment:
\begin{program}
\end{slide}
\begin{slide}
- \head{Hash functions, 5: random oracles \cite{Bellare:1993:ROP}}
+ \head{Hash functions, \seq: random oracles \cite{Bellare:1993:ROP}}
In practice, we expect much more than just collision resistance from hash
functions: we expect a certain amount of `random' behaviour. But this is
\begin{slide}
\topic{integer factorization}
- \head{The Integer Factorization Problem, 1}
+ \resetseq
+ \head{The Integer Factorization Problem, \seq}
We often assume that large integers of the form $n = p q$, where $p$ and
$q$ are primes of roughly the same size, are `hard' to factor.
\end{slide}
\begin{slide}
- \head{The Integer Factorization Problem, 2: square roots}
+ \head{The Integer Factorization Problem, \seq: square roots}
The problem of extracting square roots modulo $n = p q$ is provably as hard
as factoring. This is the basis of Rabin's public key encryption and
If $n = p q$ is a product of two primes and $x \inr (\Z/n\Z)^*$ is chosen
at random, then
- \[ \Pr\Bigl[x \in Q_n \Bigm| \jacobi{x}{n} = 1\Bigr] = \frac{1}{2}. \]
+ \[ \Pr\Bigl[x \in Q_n \Bigm| \jacobi{x}{n} = 1\Bigr] = \frac{1}{2}, \]
+ since we have
+ \[ \jacobi{x}{p} = \jacobi{x}{q} = \pm 1 \]
+ with each occurring with equal probability.
The problem of distinguishing pseudosquares from quadratic residues is
called the Quadratic Residuosity Problem (QRP). It is not known how to
\begin{slide}
\topic{self-reducibility}
- \head{Self-reducibility, 1}
+ \resetseq
+ \head{Self-reducibility, \seq}
The problems of square-root extraction, deciding quadratic residuosity, the
RSA problem, and finding discrete logarithms share the property of being
\end{slide}
\begin{slide}
- \head{Self-reducibility, 2: the RSA problem \cite{Rivest:1978:MOD}}
+ \head{Self-reducibility, \seq: the RSA problem \cite{Rivest:1978:MOD}}
The RSA problem is to compute $e$-th roots modulo $n = p q$, where $e$ is
relatively prime to $n$. Suppose that the algorithm $S(n, e, y)$ returns a
value $x$ such that $x^e \equiv y \pmod{n}$ for `many' choices of $y$, or
the special symbol $\bot$ otherwise. The following probabilistic algorithm
- then solves the RSA problem for arbitary $y$:
+ then solves the RSA problem for arbitrary $y$:
\begin{program}
Algorithm $\id{solve-rsa}(n, e, y)$: \+ \\
\REPEAT \\ \quad\=\+\kill
The (computational) Diffie-Hellman \emph{assumption} is that there is no
probabilistic algorithm which solves the computational Diffie-Hellman
- problem in time polynomial in $q$.
+ problem in time polynomial in $\log q$.
Obviously, being able to compute discrete logs in $G$ efficiently would
yield a solution to the Diffie-Hellman problem. But it may be the case
~mdw / doc / ips / blobdiff