\begin{slide}
\topic{informal security notion}
- \head{Strong MACs, 1: informal security notion}
+ \resetseq
+ \head{Strong MACs, \seq: informal security notion}
Our standard notion of security for MACs is \emph{strong unforgeability
against chosen message attack}, or SUF-CMA, for short
\begin{slide}
\topic{strong MACs}
- \head{Strong MACs, 2: the experiment}
+ \head{Strong MACs, \seq: the experiment}
We perform the following experiment with the adversary.
\begin{program}
\end{slide}
\begin{slide}
- \head{Strong MACs, 3: wrapping up the notation}
+ \head{Strong MACs, \seq: wrapping up the notation}
The \emph{success probability} of an adversary $A$ against the MAC
$\mathcal{M}$ in the sense of SUF-CMA is
\begin{slide}
\topic{PRFs are MACs}
- \head{PRFs are MACs, 1}
+ \resetseq
+ \head{PRFs are MACs, \seq}
If $F_K\colon \{0, 1\}^* \to \{0, 1\}^L$ is a $(t, q, \epsilon)$-secure
PRF, then it's also a $(t', q_T, q_V, \epsilon')$-secure MAC, with $q = q_T
\end{slide}
\begin{slide}
- \head{PRFs are MACs, 2: the distinguisher}
+ \head{PRFs are MACs, \seq: the distinguisher}
\begin{program}
Distinguisher $D^{F(\cdot)}$: \+ \\
\end{slide}
\begin{slide}
- \head{PRFs are MACs, 3: wrapping up}
+ \head{PRFs are MACs, \seq: wrapping up}
The distinguisher simulates the tagging and verification oracles for the
MAC forger, using its supplied oracle. If the forger succeeds, then the
\InSec{prf}(F; t + O(q), q) + (q_V + 1)2^{-L}. \]%
\end{slide}
+\begin{slide}
+ \head{PRFs are MACs, \seq: MACs aren't PRFs}
+
+ The converse of our result is not true. Suppose $\mathcal{M} = (T, V)$ is
+ a deterministic MAC. Choose some integer $n$. Then define $\mathcal{M}' =
+ (T', V')$, as follows:
+ \[ T'_K(x) = 0^n \cat T_K(x); \qquad
+ V'_K(x, \tau) = \begin{cases}
+ 1 & if $T'_K(x) = \tau$ \\
+ 0 & otherwise
+ \end{cases}.
+ \]
+ $T'$ is obviously not a PRF: an adversary checking for the string of $n$
+ zero bits on the output will succeed with advantage $1 - 2^{-qn}$.
+
+ However, $\mathcal{M}'$ is a secure MAC. Suppose $A'$ attacks
+ $\mathcal{M}'$.
+ \begin{program}
+ Adversary $A^{T(\cdot), V(\cdot)}$: \+ \\
+ $(m, \tau') \gets A'^{\id{tag}(\cdot), \id{verify}(\cdot)}$; \\
+ \PARSE $\tau'$ \AS $n\colon z, \tau$; \\
+ \RETURN $(m, \tau)$;
+ \next
+ Oracle $\id{tag}(m)$: \+ \\
+ \RETURN $0^n \cat T(m)$; \- \\[\smallskipamount]
+ Oracle $\id{verify}(m, \tau')$: \+ \\
+ \PARSE $\tau'$ \AS $n\colon z, \tau$; \\
+ \IF $z \ne 0^n$ \THEN \RETURN $0$; \\
+ \ELSE \RETURN $V(m, \tau)$;
+ \end{program}
+\end{slide}
+
\begin{exercise}
\begin{parenum}
\item Suppose that $F\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^L$ is
a $(t, q, \epsilon)$-secure PRF. Let $T^{(\ell)}_K(x)$ be the leftmost
- $\ell$~bits of $F_K(x)$. Demonstrate the security of $T^{(\ell)}(\cdot)$
- as a MAC.
+ $\ell$~bits of $F_K(x)$ for $\ell \le L$. Demonstrate the security of
+ $T^{(\ell)}(\cdot)$ as a MAC.
\item Discuss the merits of truncating MAC tags in practical situations.
\end{parenum}
\answer%
to the tagging oracle.
\item Once a verification query succeeds, all subsequent verification
queries also succeed and the adversary returns a correct forgery (e.g.,
- by simply repeating the succeessful query).
+ by simply repeating the successful query).
\end{itemize}
It's clear that any adversary can be transformed into one which has these
properties and succeeds with probability at least as high.
return it; otherwise we guess randomly from the remaining $2^L - q$
possibilities. Now
\begin{eqnarray*}[rl]
- e_q &= e_{q-1} + (1 - e_{q-1}) \frac{1}{2^L - q} \\
+ e_q &= e_{q-1} + \frac{1 - e_{q-1}}{2^L - q} \\
&= \frac{q}{2^L} + \frac{2^L - q}{2^L} \cdot \frac{1}{2^L - q} \\
&= \frac{q + 1}{2^L}
\end{eqnarray*}
\xcalways\subsection{The HMAC construction}\x
\begin{slide}
- \head{The HMAC construction \cite{Bellare:1996:KHF}, 1: motivation}
-
+ \resetseq
+ \head{The HMAC construction \cite{Bellare:1996:KHF}, \seq: motivation}
+
It ought to be possible to construct a decent MAC using a hash function.
Many attempts have failed, however. For example, these constructions are
- weak if used with Merkle-Damg\aa{}rd iterated hashes:
+ weak if used with standard one-pass Merkle-Damg\aa{}rd iterated hashes.
\begin{itemize}
- \item Secret prefix: $T_K(m) = H(K \cat m)$.
- \item Secret suffix: $T_K(m) = H(m \cat K)$.
+ \item Secret prefix: $T_K(m) = H(K \cat m)$. Given $H(K \cat m)$, it's
+ easy to compute $H(K \cat m \cat p \cat m')$ for a padding string $p$ and
+ arbitrary suffix $m'$.
+ \item Secret suffix: $T_K(m) = H(m \cat K)$. Finding a collision $H(m) =
+ H(m')$ yields $H(m \cat K) = H(m' \cat K)$. We saw earlier that
+ adversaries which know collisions \emph{exist} even if we don't know how
+ to describe them.
\end{itemize}
It would be nice to have a construction whose security was provably related
\end{slide}
\begin{slide}
- \head{The HMAC construction, 2: definition of NMAC}
+ \head{The HMAC construction, \seq: definition of NMAC}
Let $H\colon \{0, 1\}^* \to \{0, 1\}^k$ be an iterated hash, constructed
from the compression function $F\colon \{0, 1\}^k \times \{0, 1\}^L \to
\end{slide}
\begin{slide}
- \head{The HMAC construction, 3: security of NMAC}
+ \head{The HMAC construction, \seq: security of NMAC}
Consider a function $F\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^k$.
We say that $F$ is \emph{$(t, q, \epsilon)$-weakly collision resistant} if,
\end{slide}
\begin{slide}
- \head{The HMAC construction, 4: NMAC security proof}
+ \head{The HMAC construction, \seq: NMAC security proof}
Let $A$ be an adversary which forges a $\Xid{T}{NMAC}^H$ tag in time $t$,
using $q_T$ tagging queries and $q_V$ verification queries with probability
\end{slide}
\begin{slide}
- \head{The HMAC construction, 5: from NMAC to HMAC}
+ \head{The HMAC construction, \seq: from NMAC to HMAC}
Implementing NMAC involves using strange initialization vectors and
generally messing about with your hash function. HMAC is an attempt to
\end{slide}
\begin{slide}
- \head{The HMAC construction, 6: comparison with NMAC}
+ \head{The HMAC construction, \seq: comparison with NMAC}
Comparing the two constructions, we see that
\[ \Xid{T}{HMAC}^H_K =
$i \in \{0, 1\}$) using the $H_K$ construction. Verification in each
case consists of computing the tag and comparing to the one offered.
\begin{eqlines*}
- T^0_K(x) = H_K(x); \qquad T^1_K(x) = H_K(x \cat K)
+ T^0_K(x) = H_K(x); \qquad T^1_K(x) = H_K(x \cat K); \\
V^i_K(x, \tau) = \begin{cases}
1 & if $\tau = T^i_K(x)$ \\
0 & otherwise
- \end{cases}
+ \end{cases}.
\end{eqlines*}
Decide whether each of these constructions is secure. A full proof is
rather hard: an informal justification would be good.
The former is trickier. This needs a lot more work to make it really
rigorous, but we show the idea. Assume that the bad event has not
- occured. Consider a query $x_0, x_1, \ldots, x_{n-1}$. If it's the
+ occurred. Consider a query $x_0, x_1, \ldots, x_{n-1}$. If it's the
same as an earlier query, then $A$ learns nothing (because it could
have remembered the answer from last time). If it's \emph{not} a
prefix of some previous query, then we must add a new edge to our
as $\G1$, except that if $A$ makes any query of the form $p \cat K
\cat q$ with $|p| = t$ and $|q| = \ell - k$ then the game halts
immediately, and let $F_2$ be the event that this occurs. By
- Lemma~\ref{lem:shoup} (page~\pageref{lem:shoup}), then, $|{\Pr[S_2]} -
+ Lemma~\ref{lem:shoup} (slide~\pageref{lem:shoup}), then, $|{\Pr[S_2]} -
\Pr[S_1]| \le \Pr[F_2]$. Let game~$\G3$ be the same as $\G2$ except
that we give $A$ an oracle for $F_K$ rather than $F'_K$. Since $F$
and $F'$ differ only on queries of the form $p \cat K \cat q$, we have
as $p \cat K' \cat q$ with $|p| = t$, $|K'| = k$ and $|q| = \ell - k$;
then, if $F_{K'}(0) = F(0) \land F_{K'}(1) = F(1) \land \cdots \land
F_{K'}(n - 1) = F(n - 1)$, $B$ immediately returns $1$, claiming that
- its oracle $F$ is the function $F_{K'}$; if this never occirs, $B$
+ its oracle $F$ is the function $F_{K'}$; if this never occurs, $B$
returns $0$. Clearly, if $B$ is given an instance $F_K$ of $F$ then
it succeeds with probability $\Pr[F_2]$; however, if $F$ is a random
function then $B$ returns $1$ with probability at most $q 2^{-nk}$.
queries, and takes time $t + O(n q)$. Wrapping everything up, we get
\[ \InSec{prf}(F'; t, q) \le
2\cdot\InSec{prf}(F; t + O(q n), q + n) + \frac{q}{2^{nk}}. \]%
- This completes the proof of generic insecurty for $\mathcal{M}^1$.
+ This completes the proof of generic insecurity for $\mathcal{M}^1$.
\end{exercise}
\xcalways\subsection{Universal hashing}\x
\begin{slide}
\topic{almost-universal hash functions}
- \head{Universal hashing, 1: definition}
+ \resetseq
+ \head{Universal hashing, \seq: definition}
Consider a family of hash functions $H\colon \keys H \times \dom H \to
\ran H$. We define
\begin{slide}
\topic{dynamic view}
- \head{Universal hashing, 2: a dynamic view}
+ \head{Universal hashing, \seq: a dynamic view}
Suppose that $H$ is $\epsilon$-almost universal. Consider this experiment:
\begin{program}
\end{slide}
\begin{slide}
- \head{Universal hashing, 3: the dynamic view (cont.)}
+ \head{Universal hashing, \seq: the dynamic view (cont.)}
Now we treat $\rho$ as a random variable, selected from some distribution
$P$ on the set $\{0, 1\}^*$. We see that
\begin{slide}
\topic{composition}
- \head{Universal hashing, 4: composition}
+ \head{Universal hashing, \seq: composition}
Suppose that $G$ is $\epsilon$-almost universal, and $G'$ is
$\epsilon'$-almost universal, and $\dom G = \ran G'$. We define the
\begin{slide}
\topic{the collision game}
- \head{Universal hashing, 5: the collision game}
+ \head{Universal hashing, \seq: the collision game}
Suppose that, instead of merely a pair $(x, y)$, our adversary was allowed
to return a \emph{set} $Y$ of $q$ elements, and measure the probability
that $H_K(x) = H_K(y)$ for some $x \ne y$ with $x, y \in Y$, and for $K
\inr \keys H$.
- Let $\InSec{uh-set}(H; q)$ be maximum probability acheivable for sets $Y$
+ Let $\InSec{uh-set}(H; q)$ be maximum probability achievable for sets $Y$
with $|Y| \le q$. Then
\[ \InSec{uh-set}(H; q) \le \frac{q(q - 1)}{2} \cdot \InSec{uh}(H) .\]
\end{slide}
The worst that can happen is that $A'$ accidentally removes the one
colliding element from $Y$. This occurs with probability $2/q$. So
\[ \Succ{uh-set}{H}(A') \ge \frac{q - 2}{q} \Succ{uh-set}{H}(A). \]
- Rearranging and maximzing gives
+ Rearranging and maximizing gives
\[ \InSec{uh-set}(H; q) \le
\frac{q}{q - 2} \cdot \InSec{uh-set}(H; q - 1). \]
Note that $\InSec{uh-set}(H; 2) = \InSec{uh}(H)$ is our initial notion. A
\begin{slide}
\topic{a MAC}
- \head{Universal hashing, 6: a MAC}
+ \head{Universal hashing, \seq: a MAC}
- Suppse that $H\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^l$ is an
- almost universal hash fucntion, and $F\colon \{0, 1\}^{k'} \times \{0,
+ Suppose that $H\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^l$ is an
+ almost universal hash function, and $F\colon \{0, 1\}^{k'} \times \{0,
1\}^l \to \{0, 1\}^L$ is a PRF\@. Define a MAC $\Xid{\mathcal{M}}{UH}^{H,
F} = (\Xid{T}{UH}^{H, F}, \Xid{V}{UH}^{H, F})$ where:
\begin{eqnarray*}[rl]
\begin{slide}
\topic{almost XOR-universality}
- \head{Almost XOR-universality, 1: definition}
+ \resetseq
+ \head{Almost XOR-universality, \seq: definition}
Consider a family of hash functions $H\colon \keys H \times \dom H \to
\{0, 1\}^L$. Define
technique as for almost universal functions.
If $H$ is $2^{-L}$-almost XOR universal then we say that $H$ is
- \emph{XOR-universal}. This is the best acheivable.
+ \emph{XOR-universal}. This is the best achievable.
\end{slide}
\begin{proof}
\begin{slide}
\topic{composition}
- \head{Almost XOR-universality, 2: composition}
+ \head{Almost XOR-universality, \seq: composition}
We extend our result about composition of almost-universal functions.
Suppose that $G$ is $\epsilon$-almost XOR universal, and $G'$ is
\begin{slide}
\topic{a better MAC}
- \head{Almost XOR-universality, 3: a better MAC}
+ \head{Almost XOR-universality, \seq: a better MAC}
The security result for the UH-based MAC contains a factor $q_T$, which
it'd be nice to remove. Our new scheme uses an AXU hash $H\colon \keys H
\end{slide}
\begin{slide}
- \head{Almost XOR-universality, 4: security of AXU-based MACs}
+ \head{Almost XOR-universality, \seq: security of AXU-based MACs}
For the stateful scheme presented earlier, provided $q_T \le 2^l$, we have
\begin{eqnarray*}[Ll]
\end{slide}
\begin{slide}
- \head{Almost XOR-universality, 5: randomized AXU-based MAC}
+ \head{Almost XOR-universality, \seq: randomized AXU-based MAC}
We can avoid statefulness by using randomization. This new scheme is
$\Xid{\mathcal{M}}{XUH$\$$}^{H, F} = (\Xid{T}{XUH$\$$}^{H, F},
\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, 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 / commitdiff