The Great Upheaval -- step 1.

[doc/ips] / basics.tex

\xcalways\section{Basics}\x

\xcalways\subsection{Introduction and motivation}\x

\begin{slide}
  \topic{joke}
  \head{Mandatory joke}
  
  An elderly Frenchman rises every morning at 5, goes out to the street in
  front of his house, and sprinkles a white powder up and down the street.
  
  One day, a neighbour, who has watched his routine for many years, confronts
  him.  `What is this powder you sprinkle on the street every morning,
  Pierre?'
  
  `It is elephant powder, \emph{mon ami},' the gentleman says.  `It keeps the
  elephants away.'
  
  `But Pierre,' says the neighbour.  `Everybody knows that there are no
  elephants in France.'
  
  Says the older man matter-of-factly, `I guess it must be working, then.'
\end{slide}

The joke has its mandatory corresponding serious message.  Cryptography is
like elephant powder.  If it seems to work, and keeps the attackers -- our
elephants -- away, then we trust it.  This isn't really very satisfactory.
When the elephant powder fails, a 2-ton elephant turns up, with three of its
chums in a Mini, and you notice it hiding upside-down in your bowl of
custard.  Let's face it: elephants aren't good at being surreptitious.

But if your cryptography is no good, you may never know.

\begin{slide}
  \topic{serious message}
  \head{Cryptography is elephant powder}

  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
    ahead of the bad guy.
  \item Build useful constructions from trusted primitives in a modular way.
    \emph{Prove that the constructions are secure.}
  \end{itemize}
  Here we look at this second part of the approach.
\end{slide}

\xcalways\subsection{Approach}\x

\begin{slide}
  \head{The provable security approach}

  \begin{itemize}
  \item Define notions of security.  Now we know what to aim for, and what to
    expect of our components.
  \item Prove how the security of a construction relates to the security of
    its primitives.  If it breaks, we know who to blame.
  \end{itemize}
\end{slide}

\begin{slide}
  \topic{adversaries}
  \head{Adversaries}

  We model our adversary as a \emph{probabilistic algorithm}; i.e., the
  algorithm is allowed to \emph{flip coins} to make decisions.  The
  adversary's output (for some input) follows a probability distribution.  We
  define what it means for an adversary to \emph{break} our construction, and
  examine the probability with which this happens.

  We provide the adversary with \emph{oracles}:
  \begin{itemize}
  \item Oracles compute using secrets hidden from the adversary.
  \item We count the number of \emph{queries} made to an oracle.
  \item We can restrict the types of queries the adversary makes.
  \end{itemize}

  Oracles are written as superscripts.  For example, an adversary given a
  chosen-plaintext oracle might be written as $A^{E_K(\cdot)}$.
\end{slide}

\begin{slide}
  \topic{the asymptotic approach}
  \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
  $k \ge n$.  That is, $\nu(k)$ is `eventually' less than any polynomial
  function of $k$.
  
  We examine families of constructions, with a \emph{security parameter} $k$.
  We say that a function is (asymptotically) secure in some sense if, for any
  polynomial $p(k)$ there is a negligible function $\nu(k)$ such that, for
  any construction in the family, parameterized by $k$, no adversary which
  runs for time $p(k)$ has success probability better than $\nu(k)$.
\end{slide}

\begin{slide}
  \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
  do this by contradiction:
  \begin{enumerate}
  \item Suppose an adversary $A$ breaks the encryption scheme with
    better-than-negligible probability.
  \item Show a polynomial-time \emph{reduction}: an algorithm which uses $A$
    to break the one-way function, in polynomial time, and with
    better-than-negligible probability,
  \item Claim that this violates the assumption of a secure one-way function.
  \end{enumerate}
  
  This doesn't work with real constructions.  We don't know where the
  asymptotics set in, and they can conceal large constants.  It's still
  better than nothing.
\end{slide}

\begin{slide}
  \topic{the concrete (quantitative) approach}
  \head{The concrete (quantitative) approach}

  We constrain the resources we allow the adversary:
  \begin{itemize}
  \item Running time (including program size).
  \item Number of oracle queries.
  \item Maximum size of oracle queries.
  \end{itemize}
  Write that something is \emph{$(t, q, \epsilon)$-secure} if no adversary
  which runs in time $t$ and makes $q$ oracle queries can break it with
  probability better than $\epsilon$.
  
  We make statements like `foo is $(t, q, 2 q \epsilon)$-secure if bar is $(t
  + O(q), 2 q, \epsilon)$-secure'. 
  
  This is a much more satisfactory approach.  However, we still have to
  \emph{assume} the security of our primitive operations.
\end{slide}

\xcalways\subsection{Notation}\x

\begin{slide}
  \topic{boolean operators}
  \resetseq
  \head{Notation, \seq: boolean operators}

  If $P$ and $Q$ are \emph{predicates} -- i.e., either true or false -- then:
  \begin{itemize}
  \item $P \land Q$ is true if both $P$ \emph{and} $Q$ is true;
  \item $P \lor Q$ is true if either $P$ \emph{or} $Q$ (or both) is true;
  \item $\lnot P$ is true if $P$ is false; and
  \item $P \implies Q$ is true if $Q$ is true or $P$ is false.
  \end{itemize}
\end{slide}

\begin{slide}
  \topic{sets}
  \head{Notation, \seq: sets}

  For our purposes, we can think of sets as being collections of objects.
  
  We use the usual notations for set membership ($x \in X$), intersection ($X
  \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 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, \seq: sets (cont.)}
  
  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, \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{range} (or sometimes \emph{codomain}) $Y$.  The notation $\dom f$
  describes the domain of an arbitrary function; $\ran f$ describes its
  range.

  We sometimes apply the function notation to sets, indicating that the
  function should be applied pointwise; i.e., $f(Z) = \{ f(z) \mid z \in Z
  \}$.  The \emph{image} of a function $f$ is the set $f(\dom f)$.
  
  If $f\colon X \to Y$ preserves equality, i.e., $f(x) = f(x') \implies x =
  x'$ for all $x, x' \in X$, then we say $f$ is \emph{injective} (or
  \emph{1-to-1}).  If $f(X) = Y$ then we say that it is \emph{surjective} (or
  \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, \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,
  y) \in f$ and $(x, y') \in f$ then $y = y'$.

  We shall use this view in some of the algorithms we present.  In addition,
  we shall use the \emph{maplet} notation $x \mapsto y$ rather than the
  ordered pair notation $(x, y)$ to reinforce the notion of a mapping.

  We might write, for example,
  \begin{program}
    $f \gets f \cup \{ x \mapsto y \}$;
  \end{program}
  to augment a function by the addition of a new mapping.  This is clearly
  only valid if $x \notin \dom f$ (or $f(x) = y$) initially.
\end{slide}

\begin{slide}
  \topic{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^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$.
  
  If $x, y \in A^*$ are strings then their \emph{concatenation}, written $x
  \cat y$, or sometimes just $x y$, is the result of writing the symbols in
  $x$ followed by the symbols in $y$, in order.  We have $|x y| = |x| + |y|$.
\end{slide}

\begin{slide}
  \head{Notation, \seq: strings (cont.)}
  
  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 the natural number
  \[ \overrightarrow{x} = \sum_{0 \le i < n} 2^i x_i. \]

  The other natural mapping is
  \[ \overleftarrow{x} = \sum_{0 \le i < n} 2^{n-i-1} x_i. \]
  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 implicitly.
\end{slide}

\begin{slide}
  \topic{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{program}
    \PARSE $x$ \AS $n_0\colon x_0, n_1\colon x_1, \ldots, n_k\colon x_k$;
  \end{program}
  to mean that the string $x$ is broken up into individual strings $x_0$,
  $x_1$, \ldots, $x_k$, such that
  \begin{itemize}
  \item $x = x_0 \cat x_1 \cat \cdots \cat x_k$; and
  \item $|x_i| = n_i$ for all $0 \le i \le k$.
  \end{itemize}
  We may omit one of the $n_i$ length indicators, since it can be deduced
  from the length of the string $x$ and the other $n_j$.
\end{slide}

\begin{slide}
  \topic{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 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$.

  When we apply functions to vectors, we mean that they are applied
  pointwise, as for sets.  Thus, if we write that $\vect{y} =
  f(\vect{x})$ then $|\vect{y}| = |\vect{x}|$ and $\vect{y}[i] =
  f(\vect{x}[i])$ for all $0 \le i < |\vect{x}|$.
\end{slide}

\begin{slide}
  \topic{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
  \[ \sum_{x \in X} \mathcal{D}(x) = 1. \]
  
  The \emph{support} of $\mathcal{D}$, written $\supp \mathcal{D}$, is the
  set $\{ x \in X \mid \mathcal{D}(x) \ne 0 \}$; i.e., those elements of $X$
  which occur with nonzero probability.
  
  We write $x \getsr \mathcal{D}$ in algorithms to indicate that $x$ is to be
  chosen independently at random, according to the distribution
  $\mathcal{D}$.  The notation $x \inr \mathcal{D}$ indicates that $x$ has
  been chosen at independently at random according to $\mathcal{D}$.
  
  The \emph{uniform distribution} over a (finite) set $X$ is
  $\mathcal{U}_X\colon X \to [0, 1]$ defined by $\mathcal{U}_X(x) = 1/|X|$
  for all $x \in X$.  We shall write $x \getsr X$ and $x \inr X$ as
  convenient shorthands, meaning $x \getsr \mathcal{U}_X$ and $x \inr
  \mathcal{U}_X$ respectively.
\end{slide}

\xcalways\subsection{Background}\x

\begin{slide}
  \topic{distinguishability}
  \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{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
  \[ x \in \supp \mathcal{Y} \land \mathcal{X}(x) = \mathcal{Y}(y). \]
\end{slide}

\begin{slide}
  \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$,
  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}, 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, \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}
  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[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 -- 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
  more than one ball -- a \emph{collision}.
  
  Let $B_{q, n}$ be the event that the $q$-th ball collides with a
  previous one.  Obviously, the worst case for this is when none of the other
  balls have collided, so
  \[ \Pr[B_{q, n}] \le \frac{q - 1}{n}. \]
  Then
  \begin{eqnarray*}[rl]
    \Pr[C_{q, n}]
    &\le \Pr[B_{2, n}] + \Pr[B_{3, n}] + \cdots + \Pr[B_{q, 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}

\xcalways\subsection{Primitives}\x

\begin{slide}
  \topic{one-way functions}
  \resetseq
  \head{One-way functions, \seq: introduction}

  Intuition: a one-way function is easy to compute but hard to invert.

  Choose a function $f\colon X \to Y$.  Let $I$ be a prospective inverter.
  Now we play a game:
  \begin{enumerate}
  \item Choose $x \in X$ at random.  Compute $y = f(x)$.
  \item Let $x'$ be the output of $I$ when run on input $y$.
  \item We say that $I$ `wins' if $f(x') = y$; otherwise it loses.
  \end{enumerate}
  Note that we don't care whether $x = x'$.

  Examples: SHA-1, or $x \mapsto g^x \bmod p$.
\end{slide}

\begin{slide}
  \head{One-way functions, \seq: formalism}

  The \emph{success probability} of an inverter $I$ against the function $f$
  is
  \[ \Succ{owf}{f}(I) =
     \Pr[x \getsr X;
         y \gets f(x);
         x' \gets I(y) :
         f(x') = y] \]%
  where the probability is taken over all choices of $x$ and all coin flips
  made by $I$.
  
  We measure the \emph{insecurity} of a one-way function (OWF) by maximizing
  over possible inverters:
  \[ \InSec{owf}(f; t) = \max_I \Succ{owf}{f}(I) \]
  where the maximum is taken over all $I$ running in time $t$.

  If $\InSec{owf}(f; t) \le \epsilon$ then we say that $f$ is a \emph{$(t,
  \epsilon)$-secure one-way function}.
\end{slide}

\begin{slide}
  \head{One-way functions, \seq: trapdoors}
  
  Intuition: a \emph{trapdoor} is secret information which makes inverting a
  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
    returns a pair $(P, K)$, containing the public parameters $P$ for
    computing an instance of the one-way function, and the secret trapdoor
    information $K$ for inverting it.  We write $(P, K) \in G(k)$.
    
  \item The algorithm $f$ implements the one-way function.  That is, if $(P,
    K) \in G(k)$ then $f(P, \cdot)$ (usually written $f_P(\cdot)$) is a
    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 $y =
    f_P(T(K, y))$.  We usually write $T_K(\cdot)$ instead of $T(K, \cdot)$.
  \end{itemize}
\end{slide}

\begin{slide}
  \topic{pseudorandom generators (PRGs)}
  \head{Pseudorandom generators (PRGs)}
  
  A pseudorandom generator (PRG) `stretches' an input seed into a longer
  string which `looks' random.
  
  Let $G\colon \{0, 1\}^k \to \{0, 1\}^L$ be a function from $k$-bit strings
  to $L$-bit strings.  The \emph{advantage} of a distinguisher $D$ against
  $G$ is:
  \begin{eqnarray*}[rl]
    \Adv{prg}{G}(D) = &
       \Pr[x \getsr \{0, 1\}^k; y \gets G(x) : D(y) = 1] - {}\\
    &  \Pr[y \getsr \{0, 1\}^L : D(y) = 1].
  \end{eqnarray*}
  The \emph{insecurity} is simply the maximum advantage:
  \[ \InSec{prg}(G; t) = \max_D \Adv{prg}{G}(D) \]
  where the maximum is taken over all distinguishers $D$ running in time
  $t$.  If $\InSec{prg}(G; t) \le \epsilon$ then we also say that $G$ is a
  $(t, \epsilon)$-secure PRG\@.
\end{slide}

\begin{exercise}
  We say that a PRG $g\colon \{0, 1\}^k \to \{0, 1\}^L$ is \emph{trivial} if
  $k \ge L$.
  \begin{enumerate}
  \item Show that trivial PRGs exist.
  \item Show that if $g$ is nontrivial, then $g$ is also a one-way function,
    with
    \[ \InSec{owf}(g; t) \le \InSec{prg}(g; t) + 2^{k-L}. \]
  \end{enumerate}
  \answer%
  \begin{parenum}
  \item The identity function $I(x) = x$ is a trivial PRG, with
    $\InSec{prg}(I, t) = 0$, as is easily seen from the definition.
  \item Suppose $A$ inverts $g$.  Then consider adversary $B(y)$: \{ $x \gets
    A(y)$; \IF $g(x) = y$ \THEN \RETURN $1$; \ELSE \RETURN $0$;~\}.  If $y$
    is the output of $g$, then $A$ inverts $y$ with probability
    $\Succ{owf}{g}(A)$; if $y$ is random in $\{0, 1\}^L$ then there is a
    probability at least $1 - 2^{k-L}$ that $y$ has \emph{no} inverse,
    proving the result.  Note that \cite{Wagner:2000:PSU} provides a better
    security bound than this simplistic analysis.
  \end{parenum}
\end{exercise}

\begin{exercise}
  \label{ex:dbl-prg}
  Suppose that we have a \emph{length-doubling} PRG $g\colon \{0, 1\}^k \to
  \{0, 1\}^{2k}$.  Let $g_0(\cdot)$ be the first $k$ bits of $g(x)$ and
  $g_1(\cdot)$ be the second $k$ bits.  Define the sequence of generators
  $g^{(i)}$ (for $i >= 1$) by
  \[ g^{(1)}(x) = g(x); \qquad
     g^{(i+1)}(x) = g_0(x) \cat g^{(i)}(g_1(x)). \]%
  Relate the security of $g^{(i)}$ to that of $g$.
  \answer%
  The description of the function $g^{(i)}$ is deliberately terse and
  unhelpful.  It probably helps understanding if you make a diagram.

  Let $A$ be an adversary running in time $t$ and attacking $g^{(i+1)}$.
  Firstly, we attack $g$: consider adversary $B(y)$: \{ \PARSE $y$ \AS $y_0,
  k\colon y_1$; $z \gets g^{(i)}$; $b \gets A(y_0 \cat z)$; \RETURN $b$;~\}.
  Then $\Adv{prg}{g}(B) \ge \Adv{prg}{g^{(i+1)}}(A) + \delta$, so
  $\InSec{prg}(g^{(i+1)}; t) \le \InSec{prg}(g; t) + \delta$, where
  \begin{eqnarray*}[rl]
    \delta = &\Pr[x_0 \gets \{0, 1\}^k; x_1 \gets \{0, 1\}^k;
                  y \gets g^{(i)}(x) : A(x_0 \cat y) = 1] - \\
              &\Pr[y \getsr \{0, 1\}^{(i+2)k} : A(y) = 1].
  \end{eqnarray*}
  We attack $g^{(i)}$ to bound $\delta$: consider adversary $C(y)$: \{ $x_0
  \getsr \{0, 1\}^k$; $b \gets A(x_0 \cat y)$; \RETURN $b$;~\}.  Now $\delta
  \le \Adv{prg}{g^{(i)}}(C) \le \InSec{prg}(g^{(i)}; t)$.  So by induction,
  \[ \InSec{prg}(g^{(i)}; t) \le i \cdot \InSec{prg}(g; t). \]
\end{exercise}

\begin{slide}
  \topic{advantage}
  \head{Notes about advantage}

  Advantage is a concept used in many definitions of security notions:
  \begin{eqnarray*}[rl]
     \Adv{}{}(A) = &
        \Pr[\text{$A$ returns 1 in setting $a$}] - {} \\
     &  \Pr[\text{$A$ returns 1 in setting $b$}].
  \end{eqnarray*}
  \begin{enumerate}
  \item We have $-1 \le \Adv{}{}(A) \le +1$.
  \item Zero means that the adversary couldn't distinguish.
  \item Negative advantage means the adversary got them the wrong way
    around.  There is another adversary which uses the same resources but has
    positive advantage.
  \item \label{item:adv-guess} If $A$ is attempting to guess some hidden bit
    $b^* \inr \{0, 1\}$, we have
    \[ \Pr[b \gets A : b = b^*] = \frac{\Adv{}{}(A)}{2} + \frac{1}{2}. \]
  \end{enumerate}
\end{slide}

\begin{proof}
  Let $b$ be the bit that $A$ returns, and let $b^*$ be the experiment's
  hidden bit.  Then
  \[ \Adv{}{}(A) = \Pr[b = 1 \mid b^* = 1] - \Pr[b = 1 \mid b^* = 0]. \]
  Addressing the above claims in order:
  \begin{enumerate}
  \item By definition of probability, $0 \le \Pr[b = 1 \mid b^* = 1] \le 1$
    and $0 \le \Pr[b = 1 \mid b^* = 0]$, so their absolute difference can be
    at most 1.
  \item This is a corollary of \ref{item:adv-guess}.
  \item Consider the adversary $\bar{A}$ which runs $A$ and returns the
    complement bit $\bar{b} = b \xor 1$.  Then
    \begin{eqnarray*}[rl]
      \Adv{}{}(\bar{A})
      &= \Pr[\bar{b} = 1 \mid b^* = 1] - \Pr[\bar{b} = 1 \mid b^* = 0] \\
      &= \Pr[b = 0 \mid b^* = 1] - \Pr[b = 0 \mid b^* = 0] \\
      &= (1 - \Pr[b = 1 \mid b^* = 1]) - (1 - \Pr[b = 1 \mid b^* = 0]) \\
      &= \Pr[b = 1 \mid b^* = 0] - \Pr[b = 1 \mid b^* = 1] \\
      &= -\Adv{}{}(A).
    \end{eqnarray*}
  \item Note that $\Pr[b^* = 1] = \Pr[b^* = 0] = \frac{1}{2}$.  Then
    \begin{eqnarray*}[rl]
      \Pr[b = b^*]
      &= \Pr[b = 1 \land b^* = 1] + \Pr[b = 0 \land b^* = 0] \\
      &= \frac{1}{2}(\Pr[b = 1 \mid b^* = 1] + \Pr[b = 1 \mid b^* = 0]) \\
      &= \frac{1}{2}(\Pr[b = 1 \mid b^* = 1] +
                     (1 - \Pr[b = 0 \mid b^* = 0])) \\
      &= \frac{1}{2}(1 + \Pr[b = 1 \mid b^* = 1] -
                           \Pr[b = 0 \mid b^* = 0]) \\
      &= \frac{\Adv{}{}(A)}{2} + \frac{1}{2}.
    \end{eqnarray*}
  \end{enumerate}
  All present and correct.
\end{proof}

\begin{slide}
  \topic{pseudorandom functions (PRFs)}
  \head{Pseudorandom functions (PRFs)}
  
  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$.  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
  with the same `shape'.

  We provide the adversary with an \emph{oracle}, either for a randomly
  selected $F_K$, or for completely random function, and ask it to try and
  say which it is given.

  We write $\Func{l}{L}$ as the set of \emph{all} functions from $\{0, 1\}^l$
  to $\{0, 1\}^L$.
\end{slide}

\begin{slide}
  \head{Pseudorandom functions (cont.)}

  We define the advantage of a distinguisher $D$ against the PRF $F$ as
  follows:
  \begin{eqnarray*}[rl]
    \Adv{prf}{F}(D) = &
       \Pr[K \getsr \{0, 1\}^k : D^{F_K(\cdot)} = 1] - {}\\
    &  \Pr[R \getsr \Func{l}{L} : D^{R(\cdot)} = 1].
  \end{eqnarray*}
  The insecurity of the PRF is then measured as
  \[ \InSec{prf}(F; t, q) = \max_D \Adv{prf}{F}(D) \]
  where the maximum is taken over all distinguishers $D$ which run for time
  $t$ and make $q$ oracle queries.  As is usual, if $\InSec{prf}(F; t, q)
  \le \epsilon$ then we say that $F$ is a $(t, q, \epsilon)$-secure PRF.
\end{slide}

\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.  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]
    \Adv{prp}{F}(D) = &
       \Pr[K \getsr \{0, 1\}^k : D^{F_K(\cdot)} = 1] - {}\\
    &  \Pr[R \getsr \Perm{L} : D^{R(\cdot)} = 1].
  \end{eqnarray*}

  We define $\InSec{prp}(F; t, q) = \max_D \Adv{prp}{F}(D)$ exactly as for
  PRFs, and the notion of $(t, q, \epsilon)$-security is the same.
\end{slide}

\begin{slide}
  \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[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
  insecurity:
  \[ \InSec{sprp}(F; t, q, q') = \max_D \Adv{sprp}{F}(D) \]
  where the maximum is taken over all distinguishers $D$ which run for time
  $t$, make $q$ queries to the standard oracle, and $q'$ queries to the
  inverse oracle.  If $\InSec{sprp}(F; t, q, q') \le \epsilon$ then we say
  $F$ is a $(t, q, q', \epsilon)$-secure super PRP\@.
\end{slide}

\begin{exercise}
  Note that the key length hasn't appeared anywhere in the definition of
  insecurity for a PRP.  Derive lower bounds for the insecurity of a PRP with
  a $k$-bit key.
  \answer%
  Let $E\colon \{0, 1\}^k \times \{0, 1\}^L \to \{0, 1\}^L$ be a PRP.  Fix
  $n$ and $c$.  Then consider adversary $S^{E(\cdot)}$: \{ \FOR $i = 0$ \TO
  $c - 1$ \DO $y[i] \gets E(i)$; \FOR $K = 0$ \TO $n - 1$ \DO \{ $i \gets 0$;
  $\id{good} \gets 1$; \WHILE $i < c \land \id{good} = 1$ \DO \{ \IF $E_K(i)
  \ne y[i]$ \THEN $\id{good} \gets 0$;~\} \IF $\id{good} = 1$ \THEN \RETURN
  $1$;~\}~\}.  Then $\Adv{prp}{E}(S) \ge n(2^{-k} - 2^{-Lc})$.
\end{exercise}

\begin{slide}
  \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
  good' PRF, as long as it's not over-used.

  Let $F$ be any PRP family.  Then
  \[ \InSec{prf}(F; t, q) \le
     \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}}. \]%
  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}.  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{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 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]
    \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*}
  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}
  \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
  question to answer.
  \begin{itemize}
  \item One-wayness.  We've seen a definition for this already.  But it's not
    enough.
  \item Collision-resistance.  This is the property usually claimed as the
    requirement for use in digital signature systems.  We'll look at this
    later.
  \item Randomness.  What does this mean, when the function is completely
    public?  A distinguishability criterion is clearly hopeless.
  \end{itemize}
\end{slide}
  
\begin{slide}
  \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}
  function.  Now consider the function $H\colon \{0, 1\}^* \to \{0, 1\}^k$
  which transforms an input string $x$ as follows:
  \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 $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}
  
  Suppose we have two strings $x \ne y$, such that $H(x) = H(y)$; i.e., a
  \emph{collision}.  Then \emph{either} we can find a collision for $F$
  \emph{or} a string $z$ for which $F(z) = I$.  (This is why initialization
  vectors for hash functions have such obviously regular forms.)
\end{slide}

\begin{proof}
  Let $x_0, x_1, \ldots, x_{n-1}$ and $x'_0, x'_1, \ldots, x'_{n'-1}$ be
  the $l$-bit blocks of two distinct (padded) messages, and without loss
  of generality suppose that $n \ge n'$.  Let $I_0 = I'_0 = I$, let
  $I_{i+1} = F(I_i \cat x_i)$, and $I'_{i+1} = F(I'_i \cat x'_i)$.  We
  have $I_n = I'_{n'}$.
  
  We prove the result by induction on $n$.  The case $n = 0$ is trivially
  true, since there is only one zero-block message.  Suppose, then, that the
  result is true for $n$-block messages.  There are three cases to consider.
  Firstly, if $n' = 0$ then $F(I_n \cat x_n) = I$.  Secondly, if $I_n \ne
  I'_{n'}$ or $x_n \ne x'_{n'}$, then we have a collision, for $F(I_n \cat
  x_n) = I_n = I'_{n'} = F(I'_{n'} \cat x'_{n'})$.  Finally, if $I_n =
  I'_{n'}$ and $x_n = x'_{n'}$ then we remove the final block from both
  messages, and because the remaining messages must differ in at least one
  block, we can apply the inductive hypothesis on these shorter messages to
  complete the proof.
\end{proof}

\begin{slide}
  \head{Hash functions, \seq: Merkle-Damg\aa{}rd iterated hashing (cont.)}

  \vfil
  \[ \begin{graph}
    []!{0; <2cm, 0cm>: <0cm, 0.9cm>::}
    *+=(1, 0)+[F]{\mathstrut I_0 = I} :[d] *+[F]{F}="f"
    [urrr] *+=(3, 0)+[F]{\mathstrut x_0} :`d"f" "f" :[d]
    *+=(1, 0)+[F]{\mathstrut I_1} :[d] *+[F]{F}="f"
    [urrr] *+=(3, 0)+[F]{\mathstrut x_1} :`d"f" "f" :@{-->}[dd]
    *+=(1, 0)+[F]{\mathstrut I_{n-1}} :[d] *+[F]{F}="f"
    [urrr] *+=(3, 0)+[F]{\mathstrut x_{n-1}} :`d"f" "f" :[d]
    *+=(1, 0)+[F:thicker]{\mathstrut H(x) = I_n}
  \end{graph} \]
  \vfil
\end{slide}

\begin{slide}
  \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$
  where $H(x) = H(y)$.  How do we formalize this?  Here's one attempt:
  \begin{eqlines*}
    \Succ{acr}{H}(A) = \Pr[(x, y) \gets A : x \ne y \land H(x) = H(y)]; \\
    \InSec{acr}(H; t) = \max_A \Succ{acr}{H}(A).
  \end{eqlines*}
  But this doesn't work.  There clearly \emph{exists} an adversary which
  already `knows' the a collision for $H$ and just outputs the right answer.
  It succeeds very quickly, and with probability 1.  So this definition is
  impossible to satisfy.
\end{slide}

\begin{slide}
  \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
  functions.  They're not really keyed, because the indices aren't kept
  secret.

  When making a signature, an index $i$ is chosen at random, and the
  signature for message $m$ is formed over the pair $(i, H_i(M))$.

  TCR-hash functions are the subject of ongoing research.  No practical
  designs exist at the moment.
\end{slide}

\begin{slide}
  \head{Hash functions, \seq: targetted collision resistance (cont.)}

  Consider the following experiment:
  \begin{program}
    $\Expt{tcr}{H}(A)$: \+ \\
      $(x, s) \gets A(\cookie{find})$; \\
      $i \getsr \keys H$; \\
      $y \gets A(\cookie{collide}, i, s)$; \\
      \IF $x \ne y \land H_i(x) = H_i(y)$
      \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \end{program}
  The security of a TCR-hash function is measured as:
  \[ \InSec{tcr}(H; t) = \max_A \Pr[\Expt{tcr}{H}(A) = 1] \]
  where the maximum is taken over all adversaries running in time $t$.  We
  define $(t, \epsilon)$-security as usual.
\end{slide}

\begin{slide}
  \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
  hard to quantify.
  
  One approach is to model a hash function as a `random oracle', i.e., an
  oracle containing a function chosen at random, used by the construction
  under consideration, and made available to the adversary.  The idea is that
  reductions can `capture' the knowledge of an adversary by examining the
  queries it makes to its random oracle.

  Hash functions \emph{aren't} random oracles.  But a random oracle proof is
  better than nothing.
\end{slide}

\xcalways\subsection{Standard assumptions}\x

\begin{slide}
  \head{Standard assumptions}

  There are a number of `standard' assumptions that are made about the
  difficulty of various problems:
  \begin{itemize}
  \item IFP, the Integer Factorization Problem;
  \item QRP, the Quadratic Residuosity Problem;
  \item DLP, the Discrete Logarithm Problem;
  \item RSAP, the RSA Problem; and
  \item CDH, the Computational Diffie-Hellman problem and its variants
  \end{itemize}
  \cite{Menezes:1997:HAC} has excellent material on the above.
\end{slide}

\begin{slide}
  \topic{integer factorization}
  \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.
  Specifically, there is no algorithm which will factor such an $n$ in time
  bounded by a polynomial function of $\log n$.

  The difficulty of various other problems, e.g., Quadratic Residuosity, or
  RSA, depend on the difficulty of factoring; however, it is not yet known
  whether the ability to solve QRP or RSAP can be used to factor.
\end{slide}

\begin{slide}
  \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
  digital signature schemes.  We shall analyse these later.
  
  Suppose $Q(n, y)$ is an algorithm which returns an $x$ such that $x^2
  \equiv y \pmod{n}$, provided such an $x$ exists.  Then we can find a
  nontrivial factor of $n$ as follows:
  \begin{program}
    Algorithm $\id{find-factor}(n)$: \+ \\
      \REPEAT \\ \quad\=\+\kill
        $x \getsr \{1, 2, \ldots, n - 1\}$; \\
        $y \gets x^2 \bmod n$; \\
        $x' \gets Q(n, y)$; \\
        $p \gets \gcd(x + x', n)$; \\
        \IF $p \notin \{1, n\}$ \THEN \RETURN $p$; \- \\
      \FOREVER;
  \end{program}
\end{slide}

\begin{proof}
  The program attempts to find two square roots of $y$ mod $n$.  It's easy to
  see that this might lead to factors of $n$.  If $x^2 \equiv x'^2 \pmod{n}$
  then $x^2 - x'^2 = k n$ for some constant $k$.  Then $(x + x')(x - x')$ is
  a factorization of $k n$.  It remains to prove the probability bound on $x
  + x'$ being a nontrivial factor of $n$.

  Let $n$ be an odd composite.  Then, if $x \not\equiv \pm y \pmod{n}$ but
  $x^2 \equiv y^2 \pmod{n}$, then $\gcd(x + y, n)$ is a nontrivial factor of
  $n$.
  
  Firstly, we claim that, if $p$ is an odd prime then the congruence $x^2
  \equiv y \pmod{p}$ has precisely two solutions $x$, $x'$ such that $x
  \equiv -x' \pmod{p}$.  Let $g$ be primitive mod $p$, with $x = g^\alpha$,
  $x' = g^\beta$.  Then $g^{2 \alpha} \equiv g^{2 \beta} \pmod{p}$, so $2
  \alpha \equiv 2 \beta \pmod{p - 1}$.  But $p - 1$ is even, by hypothesis,
  so $\alpha \equiv \beta \pmod{(p - 1)/2}$.  But $g^{(p-1)/2} \equiv -1
  \pmod{p}$; hence $x \equiv \pm x' \pmod{p}$, proving the claim.
  
  There must exist odd primes $p$, $q$, such that $p|n$ and $q|n$, and $x
  \equiv -y \pmod{p}$ and $x \equiv y \pmod{q}$, for if not, then $x \equiv
  \pm y \pmod{n}$ contrary to hypothesis.  But then $x + y \equiv 0
  \pmod{p}$, so $p|(x + y)$; but $x + y \equiv 2 x \not\equiv 0 \pmod{q}$,
  since $q$ is odd.  Hence, $p$ divides $x + y$, but $q$ does not, so $\gcd(x
  + y, n)$ is a nontrivial factor of $n$, completing the proof.
\end{proof}

\begin{slide}
  \topic{quadratic residuosity}
  \head{The Quadratic Residuosity Problem}

  If there is an $x$ such that $x^2 \equiv y \pmod{n}$ then $y$ is a
  \emph{quadratic residue modulo $n$}, and we write $y \in Q_n$; if there is
  no such $x$ then $y$ is a \emph{quadratic nonresidue modulo $n$}.

  If $p$ is prime, then we can use the \emph{Legendre symbol} to decide
  whether $x$ is a quadratic residue mod $p$:
  \[ \jacobi{x}{p} = x^{(p-1)/2} \bmod p =
     \begin{cases}
        0 & if $p$ divides $x$ \\
       -1 & if $x$ is a quadratic nonresidue mod $p$ \\
       +1 & if $x$ is a quadratic residue mod $p$
     \end{cases}. \]%
  The \emph{Jacobi symbol} (written the same way) is defined for odd~$n$: if
  $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ where the $p_i$ are prime, then
  \[ \jacobi{x}{n} =
     \jacobi{x}{p_1}^{a_1} \jacobi{x}{p_2}^{a_2} \cdots
       \jacobi{x}{p_k}^{a_k}. \]%
  This can be efficiently computed without knowledge of the factors of $n$
  \cite[Section~2.4.5]{Menezes:1997:HAC}.
\end{slide}

\begin{slide}
  \head{The Quadratic Residuosity Problem (cont.)}

  If $\jacobi{x}{n} = -1$ then $x$ is certainly \emph{not} a quadratic
  residue mod $n$; however, if $\jacobi{x}{n} = 1$ then $x$ might be a
  quadratic residue or it might not; if not, then we say that $x$ is a
  \emph{pseudosquare}.
  
  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}, \]
  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
  solve this problem without factoring $n$.
\end{slide}

\begin{slide}
  \topic{discrete logarithms}
  \head{The Discrete Logarithm Problem}
  
  The (Integer) Discrete Logarithm Problem asks for the solution $x$ given a
  congruence of the form $g^x \equiv y \pmod{n}$.  This seems to be about as
  difficult as factoring.  (The ability to solve discrete logs modulo $n$ is
  sufficient to factor $n$.  The best known algorithms for IFP and DLP have
  the same running time.)

  The problem generalizes to other cyclic groups, e.g., elliptic curves over
  finite fields.
\end{slide}

\begin{slide}
  \topic{self-reducibility}
  \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
  \emph{randomly self-reducible}; i.e., an instance of the problem can be
  transformed into many different derived instances \emph{without skewing the
    probability distribution of problem instances}, such that a solution to
  one of the derived instances yields a solution to the original one.

  This is a good property to have.  It implies that `most' problem instances
  are as hard as the hardest instances.
\end{slide}

\begin{slide}
  \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 arbitrary $y$:
  \begin{program}
    Algorithm $\id{solve-rsa}(n, e, y)$: \+ \\
      \REPEAT \\ \quad\=\+\kill
        $x' \getsr \{1, 2, \ldots, n - 1\}$; \\
        \IF $\gcd(x', n) = 1$ \THEN \\ \quad\=\+\kill
          $y' \gets y x'^e \bmod n$; \\
          $x \gets S(n, e, y')$; \\
          \IF $x \ne \bot$ \THEN \RETURN $x x'^{-1} \bmod n$; \-\- \\
      \FOREVER;
  \end{program}
\end{slide}

\begin{slide}
  \topic{the Diffie-Hellman problem}
  \head{The Diffie-Hellman problem \cite{Diffie:1976:NDC}}
  
  Let $G = \langle g \rangle$ be a cyclic group or order $q$.  Let $\alpha$
  and $\beta$ be indices, $\alpha, \beta \in \Z/q\Z$.
  
  The (computational) \emph{Diffie-Hellman} problem is, given $g^\alpha$ and
  $g^\beta$, to find $g^{\alpha\beta}$.
  
  The (computational) Diffie-Hellman \emph{assumption} is that there is no
  probabilistic algorithm which solves the computational Diffie-Hellman
  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
  that the Diffie-Hellman problem is easier than the discrete log problem.

  The Diffie-Hellman problem is self-reducible.
\end{slide}

\begin{slide}
  \head{The Decisional Diffie-Hellman assumption \cite{Boneh:1998:DDP}}

  The computational Diffie-Hellman assumption makes a statement only about
  algorithms which compute the \emph{entire} answer $g^{\alpha\beta}$.  Since
  Diffie-Hellman is frequently used for key-exchange, what can we say about
  the ability of an adversary to guess any of the bits?
  
  The Decisional Diffie-Hellman (DDH) assumption asserts that, if you don't
  know $\alpha$ or $\beta$, then it's hard to tell $g^{\alpha\beta}$ from a
  random element of $G$; that is, that the distributions of the following
  experiments are computationally indistinguishable:
  \begin{program}
    $\alpha \getsr \Z/q\Z;$ \\
    $\beta  \getsr \Z/q\Z;$ \\
    \RETURN $(g^\alpha, g^\beta, g^{\alpha\beta})$;
  \next
    $\alpha \getsr \Z/q\Z;$ \\
    $\beta  \getsr \Z/q\Z;$ \\
    $\gamma \getsr \Z/q\Z;$ \\
    \RETURN $(g^\alpha, g^\beta, g^\gamma)$;
  \end{program}
\end{slide}

\begin{slide}
  \head{The Decisional Diffie-Hellman assumption (cont.)}
  
  If $A$ is an algorithm attempting to solve DDH in the group $G$, then we
  write its advantage as
  \begin{eqnarray*}[rl]
    \Adv{ddh}{G}(A) =
    & \Pr[\alpha \getsr \Z/q\Z; \beta \getsr \Z/q\Z :
          A(g^\alpha, g^\beta, g^{\alpha\beta}) = 1] - {} \\
    & \Pr[\alpha \getsr \Z/q\Z; \beta \getsr \Z/q\Z; 
          \gamma \getsr \Z/q\Z :
          A(g^\alpha, g^\beta, g^\gamma) = 1]
  \end{eqnarray*}
  and the insecurity of DDH in $G$ as
  \[ \InSec{ddh}(G; t) = \max_A \Adv{ddh}{G}(A) \]
  with the maximum over all algorithms $A$ running in time $t$.
\end{slide}

\begin{slide}
  \head{The Decisional Diffie-Hellman assumption (cont.)}

  If you can solve the computational Diffie-Hellman problem, you can solve
  the decisional version.  If you can compute discrete logs, you can solve
  both.
  
  There \emph{are} groups in which the computation problem is (believed to
  be) hard, but the decisional problem is easy.  In particular, if the group
  order $q$ has small factors then the decisional problem isn't hard.
\end{slide}

\endinput

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "ips"
%%% End: