auth-mac: Rewrite the stuff about universal hashing.

[doc/ips] / auth-sig.tex

\xcalways\section{Digital signatures}\x

\xcalways\subsection{Definitions and security notions}\x

\begin{slide}
  \topic{syntax}
  \head{Syntax of digital signature schemes}

  A \emph{digital signature scheme} is a triple $\mathcal{S} = (G, S, V)$ of
  algorithms:
  \begin{itemize}
  \item The \emph{key-generation} algorithm $G$ is a probabilistic algorithm
    which, given no arguments (or a security parameter $1^k$ represented in
    unary, in the asymptotic setting) returns a pair $(P, K)$ of public and
    private values.
  \item The \emph{signing} algorithm $S$ is a probabilistic algorithm.
    If $(P, K) \in G$, and $m \in \{0, 1\}^*$ is some message, then $S(K, m)$
    (usually written $S_K(m)$) returns a \emph{signature} $\sigma$ on $m$.
  \item The \emph{verification} algorithm $V$ is a deterministic algorithm
    returning a single bit. If $(P, K) \in G$ then $V(P, m) = 1$ iff $\sigma
    \in S_K(m)$.  We usually write $V_P(M)$ instead of $V(P, M)$.
  \end{itemize}
  There are many other similar formulations of digital signature schemes.
\end{slide}

\begin{slide}
  \topic{forgery goals}
  \head{Forgery goals}
  
  We recognize several different types of forgeries which can be made:
  \begin{itemize}
  \item An \emph{existential forgery} occurs when an adversary creates a
    valid signature for some arbitrary message not of its choosing.
  \item An \emph{selective forgery} occurs when an adversary creates a valid
    signature for a message that it chooses.
  \item A \emph{universal forgery} occurs when an adversary creates a valid
    signature for some specific given message.
  \item A \emph{total break} occurs when the adversary acquires the secret
    key $K$, or equivalent information, and can continue to sign given
    messages.
  \end{itemize}
  The formal definitions don't quite match up to these categories.
\end{slide}

\begin{slide}
  \topic{attack types}
  \head{Types of attacks}

  We recognize a number of different types of attack:
  \begin{itemize}
  \item In a \emph{key-only} attack, the adversary is given only a public
    key.
  \item In a \emph{known-signature} attack, the adversary given the public
    key and a collection of messages with valid signatures.
  \item In a \emph{chosen-message} attack, the adversary is provided with an
    oracle which signs messages of the adversary's choosing.
  \end{itemize}
  In order to have `won' the game, we require that the adversary return a
  signature on a message which wasn't one of the known-signature messages or
  a query to the signing oracle.
\end{slide}

\begin{slide}
  \topic{funny abbreviations}
  \head{Funny abbreviations}
  
  For each goal/attack type pair, we have a notion of security for digital
  signature schemes.  To save typing, there are standard (ish) abbreviations
  for these notions, e.g., EUF-CMA.
  
  The first part is the forger's goal: EUF, SUF, UUF for existentially,
  selectively and universally unforgeable, respectively.

  The second part is the attack time: KOA, KSA, CMA for key-only,
  known-signature and chosen-message attack, respectively.

  The strongest notion is EUF-CMA, and that's what we concentrate on.
\end{slide}

\begin{slide}
  \topic{formal definitions}
  \head{Formal definition of EUF-CMA}
  
  Consider this experiment involving a signature scheme $\mathcal{S} = (G, S,
  V)$ and an adversary:
  \begin{program}
    Experiment $\Expt{euf-cma}{\mathcal{S}}(A)$: \+ \\
      $(P, K) \gets G$; \\
      $\Xid{m}{list} \gets \emptyset$; \\
      $(m, \sigma) \gets A^{\id{sign}(\cdot)}(P)$; \\
      \IF $m \notin \Xid{m}{list} \land V_P(m, \sigma) = 1$
      \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$; \- \\[\smallskipamount]
    Oracle $\id{sign}(m)$: \+ \\
      $\Xid{m}{list} \gets \Xid{m}{list} \cup \{m\}$; \\
      \RETURN $S_K(m)$;
  \end{program}
\end{slide}

\begin{slide}
  \head{Formal definition of EUF-CMA (cont.)}

  We define:
  \begin{eqnarray*}[rl]
    \Succ{euf-cma}{\mathcal{S}}(A)
    &= \Pr[\Expt{euf-cma}{\mathcal{S}}(A) = 1]; \\
    \InSec{euf-cma}(\mathcal{S}; t, q)
    &= \max_A \Succ{euf-cma}{\mathcal{S}}(A).
  \end{eqnarray*}
  where the maximum is taken over adversaries $A$ running in time $t$ and
  issuing $q$ signing queries.

  If $\InSec{euf-cma}(\mathcal{S}; t, q) \le \epsilon$ then we say that
  $\mathcal{S}$ is a \emph{$(t, q, \epsilon)$-secure EUF-CMA digital
  signature scheme}.
\end{slide}

\xcalways\subsection{Signature schemes from trapdoor one-way functions}\x

\begin{slide}
  \topic{RSA}
  \head{RSA as a digital signature scheme}

  RSA is, we assume, a one-way trapdoor permutation.  We'd like to be able to
  turn this into a signature scheme.
  
  The obvious thing to do is just define $S_{(n, d)}(m) = m^d \bmod n$ and
  $V_{(n, e)}(m, \sigma) = 1 \iff \sigma^e \equiv m \pmod{n}$.  But this
  doesn't work.
  \begin{itemize}
  \item It allows key-only existential forgery.  Suppose we're given a public
    key $(n, e)$.  Choose a signature $\sigma \in \Z/n\Z$.  Compute $m =
    \sigma^e$.  Then $(m, \sigma)$ is a valid signed message.
  \item It allows universal forgery under chosen message attack.  Suppose
    we're given a public key $(n, e)$, and asked to forge a signature for
    message $m$.  Choose $k \inr (\Z/n\Z)^*$, and request a signature
    $\sigma'$ of $m' = m k^e$.  Then $\sigma' = m^d k^{ed} = m^d k$, so
    $\sigma = \sigma' k^{-1}$ is a valid signature on $m$.
  \end{itemize}
\end{slide}

\begin{slide}
  \topic{hash-then-sign}
  \head{Hash-then-sign}
  
  We could fix the problems with RSA if we preprocessed the message before
  signing.  The first idea is to use a collision-resistant hash function $H$,
  and to produce a signature on a message $m$, you compute $\sigma = H(m)^d
  \bmod n$.

  This doesn't work either.
  \begin{itemize}
  \item Collision-resistance isn't sufficient for security.  Just because $H$
    is collision-resistant doesn't mean that $H(x) H(y) \ne H(x y)$ with
    non-negligible probability.  If $H$ is partially multiplicative then
    universal or selective forgery is still possible.
  \item Recall the definition of a one-way function: if $x \inr \dom f$ then
    finding $x'$ such that $f(x') = f(x)$ is hard, given only $f(x)$.  But
    the range of a hash function like SHA-1 is only a tiny portion of the
    domain of RSA.
  \end{itemize}
\end{slide}

\begin{slide}
  \topic{\PKCS1 padding}
  \head{\PKCS1 signature padding \cite{RSA:1993:PRE}}
  
  Let $n = p q$ be an RSA modulus, with $2^{8(k-1)} < n < 2^{8k)}$ -- i.e.,
  $n$ is a $k$-byte number.  Let $m$ be the message to be signed.
  
  We compute $\hat{m} = 0^8 \cat T \cat 1^z \cat 0^8 \cat I_H \cat H(m)$ for
  some hash function $m$, where:
  \begin{itemize}
  \item $|\hat{m}| = 8k$, i.e., $\hat{m}$ is a $k$-byte string;
  \item $0^8$ is the string of 8 zero-bits;
  \item $T = 00000001$ is an 8-bit \emph{type} code;
  \item $1^z$ is a padding string of one-bits (with $z$ chosen so that
    $\hat{m}$ has the right length; \PKCS1 requires $z \ge 64$); and
  \item $I_H$ is an identifier for the chosen hash function $H$.
  \end{itemize}
  This bit string is then converted into an integer, using a big-endian
  representation.  Note that $\hat{m} < n$, since its top byte is zero.
\end{slide}

\begin{slide}
  \head{\PKCS1 signature padding (cont.)}

  Diagrammatically, \PKCS1 signature looks like this:
  \begin{tabular}[C]{r|c|c|c|c|c|} \hlx{c{2-6}v}
    \hex{00} & \hex{01} &
    \hex{FF} \hex{FF} \ldots \hex{FF} &
    \hex{00} &
    $I_H$ &
    $H(m)$
    \\ \hlx{vc{2-6}}
  \end{tabular}
  
  This partially obscures the multiplicative structure of RSA, but doesn't
  expand the range of the transform at all.  \PKCS1 padding only uses a tiny
  part of the domain of the RSA function.
  
  In \cite{Brier:2001:CRS}, Brier, Clavier, Coron and Naccache analyse
  general affine padding schemes, of which the \PKCS1 scheme is an example,
  and show that the schemes can be broken if the `message' -- the hash -- is
  more than a third the size of the modulus.  In particular, existential
  forgery is possible in polynomial time, and selective forgery in
  subexponential time (though much faster than factoring the modulus).
\end{slide}

\xcalways\subsection{Full-domain hashing}\x

\begin{slide}
  \topic{description}
  \head{Full-domain hashing}

  Suppose we have an \emph{ideal hash}, whose range covers the whole of the
  domain of our RSA transformation.  Would this be secure?  If we model the
  ideal hash as a random oracle, the answer is yes.
  
  Let $\mathcal{T} = (G, f, T)$ be a trapdoor one-way function generator.
  Then we define the signature scheme $\Xid{\mathcal{S}}{FDH}^{\mathcal{T},
    H} = (\Xid{G}{FDH}^{\mathcal{T}, H(\cdot)}, \Xid{S}{FDH}^{\mathcal{T},
    H(\cdot)}, \Xid{V}{FDH}^{\mathcal{T}, H(\cdot)})$ as follows:
  \begin{itemize}
  \item $\Xid{G}{FDH}^{\mathcal{T}, H(\cdot)}(\cdot) = G(\cdot)$, i.e., we
    use $\mathcal{T}$'s key generator directly.
  \item $\Xid{S}{FDH}^{\mathcal{T}, H(\cdot)}_K(m) = T_K(H(m))$: we
    implicitly (and deterministically) coerce $H$'s output so that $H(\cdot)$
    is uniformly distributed over $\ran f_P$.
  \item $\Xid{V}{FDH}^{\mathcal{T}, H(\cdot)}_P(m, \sigma) = 1 \iff
    f_P(\sigma) = H(M)$.
  \end{itemize}
\end{slide}

\begin{slide}
  \topic{security results}
  \head{Security results for FDH}
  
  The full-domain hash signature scheme $\Xid{\mathcal{S}}{FDH}^{\mathcal{T},
  H}$ is EUF-CMA if $\mathcal{T} = (G, f, T)$ is a trapdoor one-way
  permutation.  The standard quantitative result is:
  \[ \InSec{euf-cma}(\Xid{\mathcal{S}}{FDH}^{\mathcal{T}, H}; t, q_S, q_H)
     \le
     q_H \InSec{owf}(\mathcal{T}; t + O(q_H t_f)). \]%
  Here, $t_f$ is the length of time required to compute $f$.  The additional
  $q_H$ term is the number of random oracle (hashing) queries.  This doesn't
  count queries made by the signing oracle.
  
  This isn't a terribly promising bound.  The problem comes because there is
  a conflict between getting the adversary to invert the required point, and
  being able to answer signing queries.
\end{slide}

\begin{proof}
  Let $A$ be an adversary against $\Xid{\mathcal{S}}{FDH}^{\mathcal{T}}$
  making $q_S$ signing and $q_H$ random oracle queries: we present an
  inverter $I$ for $\mathcal{T}$.
  \begin{program}
    Inverter $I(P, y)$: \+ \\
      $n \getsr \{0, 1, \ldots, q_H - 1\}$; \\
      $i \gets 0$; \\
      $\Xid{I}{map} \gets \emptyset$; \\
      $\Xid{H}{map} \gets \emptyset$; \\
      $(m, \sigma) \gets A^{\id{sign}(\cdot), \id{hash}(\cdot)}(P)$; \\
      \RETURN $\sigma$;
  \newline
    Oracle $\id{sign}(m)$: \+ \\
      \IF $m \notin \dom \Xid{H}{map}$ \THEN \\ \quad \= \+ \kill
        $h' \getsr \dom f_P$; \\
        $h \gets f_P(h')$; \\
        $\Xid{H}{map} \gets \Xid{H}{map} \cup \{m \mapsto h\}$; \\
        $\Xid{I}{map} \gets \Xid{I}{map} \cup \{h \mapsto h'\}$; \- \\
      $h \gets \Xid{h}{map}(m)$; \\
      \IF $h \notin \dom \Xid{I}{map}$ \THEN \ABORT; \\
      \RETURN $\Xid{I}{map}(h)$;
  \next
    Oracle $\id{hash}(x)$: \+ \\
      \IF $x \in \dom \Xid{H}{map}$ \THEN \RETURN $\Xid{H}{map}(x)$; \\
      \IF $i = n$ \THEN $h \gets y$; \\
      \ELSE \\ \quad \= \+ \kill
        $h' \getsr \dom f_P$; \\
        $h \gets f_P(h')$; \\
        $\Xid{I}{map} \gets \Xid{I}{map} \cup \{h \mapsto h'\}$; \- \\
      $\Xid{H}{map} \gets \Xid{H}{map} \cup \{x \mapsto h\}$; \\
      \RETURN $h$;
  \end{program}
  Note that the inverter `cheats' a little.  One of its random oracle replies
  is chosen to be the inverter's input $y$.  This is OK, because the rules of
  the inverter's game say that that $y = f(x)$ for some $x$ chosen uniformly
  at random from $\dom f_P$, and hence $y$ is also uniformly distributed and
  independent, as required.

  The inverter also `cheats' because it ensures that it knows inverses for
  all of the queries except for the $n$-th.
  
  Let the $q_H$ query strings to the oracle \id{hash} be $M = \{m_0, m_1,
  \ldots, m_{q_H-1}\}$.  Let $m$ be the message returned by $A$ and let
  $\sigma$ be the returned signature.
  
  Consider the event $N$ that $m \notin M$; i.e., the random oracle was not
  queried on the returned message.  Then, since $A$ has knowledge of neither
  $H(M)$ nor $y$, and both are uniformly distributed over $\dom f_P$, the
  probability that it succeeds in producing a valid forgery is equal to its
  probability of successfully returning a correct inversion of $y$.
  
  Now consider the complement event $\lnot N$.  Then there is at least a
  $1/q_H$ probability that $m = m_n$ -- the one which the inverter must
  invert -- in which case $I$ succeeds if $A$ does.  (The probability might
  be greater in the event that the adversary queries on the same string
  several times, though doing so doesn't make a great deal of sense.)

  Let $F$ be the event that $A$ returns a correct forgery, and let $V$ be the
  event that $I$ returns a correct inversion.  Obviously,
  \[ \Pr[F] = \Pr[F \land N] + \Pr[F \land \lnot N]
     \quad \text{so} \quad
     \Pr[F \land \lnot N] = \Pr[F] - \Pr[F \land N]. \]%
  From the above discussion, we have
  \[ \Pr[V \land N] = \Pr[F \land N]
     \quad \text{and} \quad
     \Pr[V \land \lnot N] \ge \frac{1}{q_H} \Pr[F \land \lnot N]. \]%
  Finally,
  \begin{eqnarray*}[rl]
    \Pr[V] &= \Pr[V \land N] + \Pr[V \land \lnot N] \\
           &\ge \Pr[F \land N] + \frac{1}{q_H} \Pr[F \land \lnot N] \\
           &\ge \frac{1}{q_H}
                  (\Pr[F \land N] + \Pr[F] - \Pr[F \land \lnot N]) \\
           &= \frac{1}{q_H} \Pr[F].
  \end{eqnarray*}
  The result follows.
\end{proof}

\begin{remark*}
  Most statements of this result seem to charge the adversary for hash
  queries made by the experiment and by the constructed inverter, which seems
  unreasonable.  The above result shows that the standard security bound
  still holds, even under more generous accounting.
\end{remark*}

\xcalways\subsection{The Probabilistic Signature Scheme}\x

\begin{slide}
  \head{The Probabilistic Signature Scheme \cite{Bellare:1996:ESD}}
  
  We can improve the security bounds on FDH by making the signing operation
  randomized.
  
  Let $\mathcal{T} = (G, f, T)$ be a trapdoor one-way function generator, as
  before, but this time we require that the problem of inverting $f$ be
  \emph{self-reducible}.
  
  For some public parameter $P$, choose $n$ such that $2^{8n} \le
  |{\dom f_P}| < 2^{8n+1}$, and fix a security parameter $k$.  Then we need
  two random oracles $H\colon \{0, 1\}^* \to \{0, 1\}^k$ and $H'\colon \{0,
  1\}^k \to \{0, 1\}^{8n-k}$.
\end{slide}

\begin{slide}
  \topic{description}
  \head{Definition of PSS}
  
  We define the signature scheme $\Xid{\mathcal{S}}{PSS}^{\mathcal{T}} =
  (\Xid{G}{PSS}^{\mathcal{T}, H(\cdot), H'(\cdot)},
  \Xid{S}{PSS}^{\mathcal{T}, H(\cdot), H'(\cdot)}, \Xid{V}{PSS}^{\mathcal{T},
    H(\cdot), H'(\cdot)})$:
  \begin{program}
    $\Xid{G}{PSS}^{\mathcal{T}, H(\cdot), H'(\cdot)}(x)$: \+ \\
      $(P, K) \gets G(x)$; \\
      \RETURN $(P, K)$;
  \newline
    $\Xid{S}{PSS}^{\mathcal{T}, H(\cdot), H'(\cdot)}(K, m)$: \+ \\
      $r \getsr \{0, 1\}^k$; \\
      $h \gets H(m \cat r)$; \\
      $h' \gets (r \cat 0^{8n-2k}) \xor H'(h)$; \\
      $y \gets 0^8 \cat h \cat h'$; \\
      \RETURN $T_K(y)$;
  \next
    $\Xid{V}{PSS}^{\mathcal{T}, H(\cdot), H'(\cdot)}
      (P, m, \sigma)$: \+ \\
      $y \gets f_P(\sigma)$; \\
      \PARSE $y$ \AS $z, k\colon h, 8n - k\colon h'$; \\
      \PARSE $h' \xor H'(h)$ \AS $k\colon r, z$; \\
      \IF $z = 0 \land z' = 0 \land h = H(m \cat r)$
      \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \end{program}
\end{slide}

\begin{slide}
  \head{Diagram of PSS}

  %%                 m <- {0,1}^*                r <-R {0, 1}^k
  %%                     |                             |
  %%                     |                             |
  %%                     v                             |
  %%                    [H]<---------------------------|
  %%                     |                             |
  %%                     |                             |
  %%                     |                             v
  %%                     |                            [||]<---- 0^{8n-2k}
  %%                     |                             |
  %%                     |                             |
  %%                     v                             v
  %%                     |-----------[H']------------>(+)
  %%                     |                             |
  %%                     |                             |
  %%                     |                             v
  %%    < 00 >   < s = H(m || r) >          < (r || 0^{8n-2k}) (+) H'(s) >

  \vfil
  \[ \begin{graph}
    []!{0; <1cm, 0cm>:}
    {m \in \{0, 1\}^*}="m" [rrrr] {r \inr \{0, 1\}^k}="r"
    "m" :[d] *+[F]{H}="h"
        :[ddd] *+=(2, 0)+[F:thicker]{\strut s = H(m \cat r)}
    []!{-(2.5, 0)} *+=(1, 0)+[F:thicker]{\strut \hex{00}}
    "r" :[dd] *{\ocat}="cat" [r] *+[r]{\mathstrut 0^{8n-2k}} :"cat"
    :[d] *{\xor}="x" [uu] :"h"
    "m" [ddd] :[rr] *+[F]{H'} :"x"
    :[d] *+=(4, 0)+[F:thicker]{\strut t = (r \cat 0^{8n-2k}) \xor H'(s)}
  \end{graph} \]
  \vfil
\end{slide}

\begin{slide}
  \topic{security results}
  \head{Security results for PSS}
  
  For the PSS scheme we've seen, we have
  \begin{eqnarray*}[Ll]
    \InSec{euf-cma}(\Xid{\mathcal{S}}{PSS}^{\mathcal{T}};
                    t, q_S, q_H, q_{H'}) \le \\
    & \InSec{owf}(\mathcal{T}; t + O(t_n (q_S + q_H) + q_{H'})) +
      \frac{3(q_H + q_{H'} + 2)}{2^k}.
  \end{eqnarray*}
  Here, $q_H$ and $q_H$ are the number of queries to the random oracles $H$
  and $H'$, and $t_n$ is a magical constant relating to, among other things,
  the time required for the self-reduction on the original problem and the
  difference between $|{\dom f_P}|$ and $2^{8n}$.  For RSA or Rabin with a
  multiple-of-8-bit modulus, $t_n$ will be some small multiple of $k$ times
  the length of time for a public key operation.
\end{slide}

\begin{proof}
  Suppose $A$ can forge a signature under the
  $\Xid{\mathcal{S}}{PSS}^{\mathcal{T}}$ scheme.  We present an inverter $I$
  which inverts $\mathcal{T}$.

  We shall need to make use of the self-reducibility property of inverting
  $\mathcal{T}$.  To do this in an abstract way, we require two algorithms:
  \begin{itemize}
  \item $\id{sr-choose}(P, y)$ returns a pair $(s, y')$, where $s$ is some
    state information, and $y'$ is a new problem instance uniformly selected
    from the domain of $f_P$; and
  \item $\id{sr-solve}(s, x)$ solves an instance of the problem given a
    solution to the instance created by \id{sr-choose}.
  \end{itemize}
  If $P$ is a public parameter for $f$, $y$ is some point in $\ran f_P$,
  $\id{sr-choose}(P, y)$ returns $(s, y')$ and $f_P(x') = y'$ then we require
  that $\id{sr-solve}(s, x')$ returns an $x$ such that $f_P(x) = y$.

  By way of example, we present implementations of these algorithms for the
  RSA function, where $P = (n, e)$:
  \begin{program}
    Algorithm $\id{sr-choose}(P, y)$: \+ \\
      $(n, e) \gets P$; \\
      \REPEAT $z \getsr \{1, 2, \ldots, n - 1\}$; \\
      \UNTIL $\gcd(z, n) = 1$; \\
      $s \gets (n, z^{-1} \bmod n)$; \\
      \RETURN $(s, y z^e \bmod n)$;
  \next
    Algorithm $\id{sr-solve}(s, x')$: \+ \\
      $(n, i) \gets s$; \\
      \RETURN $x' i \bmod n$;
  \end{program}
  (The loop in \id{sr-choose} hardly ever needs more than one iteration.
  Indeed, if the condition $\gcd{z, n} = 1$ fails, we've found a factor,
  and could use that to solve the problem instance directly.)  We shall
  assume that the \id{sr-choose} algorithm effectively completes in
  deterministic time.)
  
  We shall also need to be able to convert between elements of $\ran f_P$ and
  binary strings.  We shall assume that there is a `natural' mapping between
  the integers $\{0, 1, \ldots, |{\ran f_P}| - 1\}$ and the elements of $\ran
  f_P$, and omit explicit conversions.

  The inverter algorithm is shown in figure~\ref{fig:pss-inverter}.

  \begin{figure}
  \begin{program}
    Inverter $I(P, y)$: \+ \\
      $\Xid{H}{map} \gets \emptyset$; \\
      $\Xid{H'}{map} \gets \emptyset$; \\
      $\Xid{I}{map} \gets \emptyset$; \\
      $\Xid{m}{list} \gets \emptyset$; \\
      $(m, \sigma) \gets A^{\id{sign}(\cdot), H(\cdot), H'(\cdot)}(P)$; \\
      \IF $m \in \Xid{m}{list}$ \THEN \ABORT; \\
      $y' \gets f_P(\sigma)$; \\
      \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\
      \PARSE $g \xor H'(h)$ \AS $k\colon r, z'$; \\
      $x \gets m \cat r$; \\
      \IF $z \ne 0 \lor z' \ne 0$ \THEN \ABORT; \\
      \IF $h \ne H(x)$ \THEN \ABORT; \\
      \IF $x \notin \dom \Xid{I}{map}$ \THEN \ABORT; \\
      \RETURN $\id{sr-solve}(\Xid{I}{map}(x), \sigma)$;
  \newline
    Oracle $\id{sign}(m)$: \+ \\
      $r \getsr \{0, 1\}^k$; \\
      $x \gets m \cat r$; \\
      \IF $x \in \dom \Xid{H}{map}$ \THEN \ABORT; \\
      \REPEAT \\ \quad \= \+ \kill
        $\sigma' \getsr \ran f_P$; \\
        $y' \gets f_P(\sigma')$; \- \\
      \UNTIL $y' < 2^{8n}$; \\
      \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\
      \PARSE $g$ \AS $k\colon r', g'$; \\
      $h' \gets (r \xor r') \cat g'$; \\
      \IF $h \in \dom \Xid{H'}{map}$ \THEN \ABORT; \\
      $\Xid{H}{map} \gets \Xid{H}{map} \cup \{x \mapsto h\}$; \\
      $\Xid{H'}{map} \gets \Xid{H'}{map} \cup \{h \mapsto h'\}$; \\
      $\Xid{m}{list} \gets \Xid{m}{list} \cup \{m\}$; \\
      \RETURN $\sigma'$;
  \next
    Oracle $H(x)$: \+ \\
      \IF $x \in \dom \Xid{H}{map}$ \THEN \RETURN $\Xid{H}{map}(x)$; \\
      \REPEAT \\ \quad\=\+\kill
        $(s, y') \gets \id{sr-choose}(P, y)$; \\
        \PARSE $x$ \AS $m, k\colon r$; \- \\
      \UNTIL $y' < 2^{8n}$; \\
      \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\
      \PARSE $g$ \AS $k\colon r', g'$; \\
      $h' \gets (r \xor r') \cat g'$; \\
      \IF $h \in \dom \Xid{H'}{map}$ \THEN \ABORT; \\
      $\Xid{H}{map} \gets \Xid{H}{map} \cup \{x \mapsto h\}$; \\
      $\Xid{H'}{map} \gets \Xid{H'}{map} \cup \{h \mapsto h'\}$; \\
      $\Xid{I}{map} \gets \Xid{I}{map} \cup \{x \mapsto s\}$; \\
      \RETURN $h$; \- \\[\smallskipamount]
    Oracle $H'(x)$: \+ \\
      \IF $x \in \dom \Xid{H'}{map}$ \THEN \RETURN $\Xid{H'}{map}(x)$; \\
      $h' \gets \{0, 1\}^{8n - k}$ \\
      $\Xid{H'}{map} \gets \Xid{H'}{map} \cup \{h \mapsto h'\}$; \\
      \RETURN $h'$;
  \end{program}
  \caption{From the security proof of PSS -- the inverter for the trapdoor
    one-way function}
  \label{fig:pss-inverter}
  \end{figure}
  
  The oracle $H$ constructs related instances of the original inversion
  problem and uses them to build the random oracle results.  Because the
  subroutine \id{sr-choose} selects problem instances uniformly over $\{0,
  1, \ldots, |{\ran f_P}| - 1\}$, and we iterate until $y' < 2^{8n}$, the
  selected instance $y'$ is uniform over $\{0, 1\}^{8n}$.  We then construct
  $H$ and $H'$ replies as appropriate for the adversary to construct $y'$ as
  a message representative for its chosen message $m$, such that if it
  responds with a signature for $m$ then we can use \id{sr-solve} to solve
  our initial problem.
  
  The oracle \id{sign} chooses oracle responses in order to fit in with a
  previously chosen inverse (computed the easy way, by choosing a point in
  the domain of $f_P$ and computing its image).

  The oracle $H'$ just chooses random values.
  
  Most of the \ABORT statements in the main inverter routine detect incorrect
  signatures.  The final one, asserting $x \notin \Xid{I}{map}$, can't happen
  unless the signature is a duplicate of one we already gave.
  
  The \ABORT{}s in $H$ and \id{sign} detect conditions in which the
  adversary has successfully distinguished its simulated environment from
  that of the standard forging experiment.
  
  The inverter succeeds whenever a correct forgery is made.  To conclude the
  proof, we must bound the probability that an \ABORT occurs in $H$ or
  \id{sign}.
  
  The \ABORT in $H$ occurs when the chosen $H(x)$ collides with a value for
  which $H'$ is already defined.  Since $H(x)$ values are chosen uniformly
  from $\{0, 1\}^k$, this occurs with probability no more than $(q_H +
  q_{H'} + 2)/2^k$.

  The first \ABORT in \id{sign} occurs when the chosen point $x = m \cat r$
  already has an image defined in $H$: this happens with probability at most
  $q_H/2^k$.  The second occurs when $h$ already has an image in $H'$, and
  occurs with probability at most $(q_H + q_{H'})/2^k$.
  
  The loops in $H$ and \id{sign} don't complete in a deterministic amount
  of time.  But we can abort if they appear to be taking too long, and choose
  the maximum number of iterations to achieve any given failure probability.
  Let $d = |{\dom f_P}|$.  Then the probability that any particular iteration
  fails to select an appropriate problem instance is $1 - 2^{8n}/d$.  For RSA
  or Rabin with a modulus bit length which is a multiple of 8, this is less
  than $\frac{1}{2}$.  We choose the number of iterations in the entire
  program to be such that we have a $2^{-k}$ probability of failure.  Thus,
  we set our maximum as $-k/\log_2 (1-2^{8n}/d)$ iterations in the entire
  program.

  Fitting all of this together, we see that
  \[ \Succ{owf}{\mathcal{T}}(I) \ge
       \Succ{euf-cma}{\Xid{\mathcal{S}}{PSS}^{\mathcal{T}}} -
       \frac{3(q_H + q_{H'} + 2)}{2^k}. \]%
  completing the proof.
\end{proof}

\endinput

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