1 \xcalways\section{Digital signatures
}\x
3 \xcalways\subsection{Definitions and security notions
}\x
7 \head{Syntax of digital signature schemes
}
9 A
\emph{digital signature scheme
} is a triple $
\mathcal{S
} = (G, S, V)$ of
12 \item The
\emph{key-generation
} algorithm $G$ is a probabilistic algorithm
13 which, given no arguments (or a security parameter $
1^k$ represented in
14 unary, in the asymptotic setting) returns a pair $(P, K)$ of public and
16 \item The
\emph{signing
} algorithm $S$ is a probabilistic algorithm.
17 If $(P, K)
\in G$, and $m
\in \
{0,
1\
}^*$ is some message, then $S(K, m)$
18 (usually written $S_K(m)$) returns a
\emph{signature
} $
\sigma$ on $m$.
19 \item The
\emph{verification
} algorithm $V$ is a deterministic algorithm
20 returning a single bit. If $(P, K)
\in G$ then $V(P, m) =
1$ iff $
\sigma
21 \in S_K(m)$. We usually write $V_P(M)$ instead of $V(P, M)$.
23 There are many other similar formulations of digital signature schemes.
30 We recognize several different types of forgeries which can be made:
32 \item An
\emph{existential forgery
} occurs when an adversary creates a
33 valid signature for some arbitrary message not of its choosing.
34 \item An
\emph{selective forgery
} occurs when an adversary creates a valid
35 signature for a message that it chooses.
36 \item A
\emph{universal forgery
} occurs when an adversary creates a valid
37 signature for some specific given message.
38 \item A
\emph{total break
} occurs when the adversary acquires the secret
39 key $K$, or equivalent information, and can continue to sign given
42 The formal definitions don't quite match up to these categories.
47 \head{Types of attacks
}
49 We recognize a number of different types of attack:
51 \item In a
\emph{key-only
} attack, the adversary is given only a public
53 \item In a
\emph{known-signature
} attack, the adversary given the public
54 key and a collection of messages with valid signatures.
55 \item In a
\emph{chosen-message
} attack, the adversary is provided with an
56 oracle which signs messages of the adversary's choosing.
58 In order to have `won' the game, we require that the adversary return a
59 signature on a message which wasn't one of the known-signature messages or
60 a query to the signing oracle.
64 \topic{funny abbreviations
}
65 \head{Funny abbreviations
}
67 For each goal/attack type pair, we have a notion of security for digital
68 signature schemes. To save typing, there are standard (ish) abbreviations
69 for these notions, e.g., EUF-CMA.
71 The first part is the forger's goal: EUF, SUF, UUF for existentially,
72 selectively and universally unforgeable, respectively.
74 The second part is the attack time: KOA, KSA, CMA for key-only,
75 known-signature and chosen-message attack, respectively.
77 The strongest notion is EUF-CMA, and that's what we concentrate on.
81 \topic{formal definitions
}
82 \head{Formal definition of EUF-CMA
}
84 Consider this experiment involving a signature scheme $
\mathcal{S
} = (G, S,
87 Experiment $
\Expt{euf-cma
}{\mathcal{S
}}(A)$: \+ \\
89 $
\Xid{m
}{list
} \gets \emptyset$; \\
90 $(m,
\sigma)
\gets A^
{\id{sign
}(
\cdot)
}(P)$; \\
91 \IF $m
\notin \Xid{m
}{list
} \land V_P(m,
\sigma) =
1$
93 \ELSE \RETURN $
0$; \- \\
[\smallskipamount]
94 Oracle $
\id{sign
}(m)$: \+ \\
95 $
\Xid{m
}{list
} \gets \Xid{m
}{list
} \cup \
{m\
}$; \\
101 \head{Formal definition of EUF-CMA (cont.)
}
104 \begin{eqnarray*
}[rl
]
105 \Succ{euf-cma
}{\mathcal{S
}}(A)
106 &=
\Pr[\Expt{euf-cma
}{\mathcal{S
}}(A) =
1]; \\
107 \InSec{euf-cma
}(
\mathcal{S
}; t, q)
108 &=
\max_A \Succ{euf-cma
}{\mathcal{S
}}(A).
110 where the maximum is taken over adversaries $A$ running in time $t$ and
111 issuing $q$ signing queries.
113 If $
\InSec{euf-cma
}(
\mathcal{S
}; t, q)
\le \epsilon$ then we say that
114 $
\mathcal{S
}$ is a
\emph{$(t, q,
\epsilon)$-secure EUF-CMA digital
118 \xcalways\subsection{Signature schemes from trapdoor one-way functions
}\x
122 \head{RSA as a digital signature scheme
}
124 RSA is, we assume, a one-way trapdoor permutation. We'd like to be able to
125 turn this into a signature scheme.
127 The obvious thing to do is just define $S_
{(n, d)
}(m) = m^d
\bmod n$ and
128 $V_
{(n, e)
}(m,
\sigma) =
1 \iff \sigma^e
\equiv m
\pmod{n
}$. But this
131 \item It allows key-only existential forgery. Suppose we're given a public
132 key $(n, e)$. Choose a signature $
\sigma \in \Z/n
\Z$. Compute $m =
133 \sigma^e$. Then $(m,
\sigma)$ is a valid signed message.
134 \item It allows universal forgery under chosen message attack. Suppose
135 we're given a public key $(n, e)$, and asked to forge a signature for
136 message $m$. Choose $k
\inr (
\Z/n
\Z)^*$, and request a signature
137 $
\sigma'$ of $m' = m k^e$. Then $
\sigma' = m^d k^
{ed
} = m^d k$, so
138 $
\sigma =
\sigma' k^
{-
1}$ is a valid signature on $m$.
143 \topic{hash-then-sign
}
144 \head{Hash-then-sign
}
146 We could fix the problems with RSA if we preprocessed the message before
147 signing. The first idea is to use a collision-resistant hash function $H$,
148 and to produce a signature on a message $m$, you compute $
\sigma = H(m)^d
151 This doesn't work either.
153 \item Collision-resistance isn't sufficient for security. Just because $H$
154 is collision-resistant doesn't mean that $H(x) H(y)
\ne H(x y)$ with
155 non-negligible probability. If $H$ is partially multiplicative then
156 universal or selective forgery is still possible.
157 \item Recall the definition of a one-way function: if $x
\inr \dom f$ then
158 finding $x'$ such that $f(x') = f(x)$ is hard, given only $f(x)$. But
159 the range of a hash function like SHA-
1 is only a tiny portion of the
165 \topic{\PKCS1 padding
}
166 \head{\PKCS1 signature padding
\cite{RSA:
1993:PRE
}}
168 Let $n = p q$ be an RSA modulus, with $
2^
{8(k-
1)
} < n <
2^
{8k)
}$ -- i.e.,
169 $n$ is a $k$-byte number. Let $m$ be the message to be signed.
171 We compute $
\hat{m
} =
0^
8 \cat T
\cat 1^z
\cat 0^
8 \cat I_H
\cat H(m)$ for
172 some hash function $m$, where:
174 \item $|
\hat{m
}| =
8k$, i.e., $
\hat{m
}$ is a $k$-byte string;
175 \item $
0^
8$ is the string of
8 zero-bits;
176 \item $T =
00000001$ is an
8-bit
\emph{type
} code;
177 \item $
1^z$ is a padding string of one-bits (with $z$ chosen so that
178 $
\hat{m
}$ has the right length;
\PKCS1 requires $z
\ge 64$); and
179 \item $I_H$ is an identifier for the chosen hash function $H$.
181 This bit string is then converted into an integer, using a big-endian
182 representation. Note that $
\hat{m
} < n$, since its top byte is zero.
186 \head{\PKCS1 signature padding (cont.)
}
188 Diagrammatically,
\PKCS1 signature looks like this:
189 \begin{tabular
}[C
]{r|c|c|c|c|c|
} \hlx{c
{2-
6}v
}
190 \hex{00} &
\hex{01} &
191 \hex{FF
} \hex{FF
} \ldots \hex{FF
} &
198 This partially obscures the multiplicative structure of RSA, but doesn't
199 expand the range of the transform at all.
\PKCS1 padding only uses a tiny
200 part of the domain of the RSA function.
202 In
\cite{Brier:
2001:CRS
}, Brier, Clavier, Coron and Naccache analyse
203 general affine padding schemes, of which the
\PKCS1 scheme is an example,
204 and show that the schemes can be broken if the `message' -- the hash -- is
205 more than a third the size of the modulus. In particular, existential
206 forgery is possible in polynomial time, and selective forgery in
207 subexponential time (though much faster than factoring the modulus).
210 \xcalways\subsection{Full-domain hashing
}\x
214 \head{Full-domain hashing
}
216 Suppose we have an
\emph{ideal hash
}, whose range covers the whole of the
217 domain of our RSA transformation. Would this be secure? If we model the
218 ideal hash as a random oracle, the answer is yes.
220 Let $
\mathcal{T
} = (G, f, T)$ be a trapdoor one-way function generator.
221 Then we define the signature scheme $
\Xid{\mathcal{S
}}{FDH
}^
{\mathcal{T
},
222 H
} = (
\Xid{G
}{FDH
}^
{\mathcal{T
}, H(
\cdot)
},
\Xid{S
}{FDH
}^
{\mathcal{T
},
223 H(
\cdot)
},
\Xid{V
}{FDH
}^
{\mathcal{T
}, H(
\cdot)
})$ as follows:
225 \item $
\Xid{G
}{FDH
}^
{\mathcal{T
}, H(
\cdot)
}(
\cdot) = G(
\cdot)$, i.e., we
226 use $
\mathcal{T
}$'s key generator directly.
227 \item $
\Xid{S
}{FDH
}^
{\mathcal{T
}, H(
\cdot)
}_K(m) = T_K(H(m))$: we
228 implicitly (and deterministically) coerce $H$'s output so that $H(
\cdot)$
229 is uniformly distributed over $
\ran f_P$.
230 \item $
\Xid{V
}{FDH
}^
{\mathcal{T
}, H(
\cdot)
}_P(m,
\sigma) =
1 \iff
236 \topic{security results
}
237 \head{Security results for FDH
}
239 The full-domain hash signature scheme $
\Xid{\mathcal{S
}}{FDH
}^
{\mathcal{T
},
240 H
}$ is EUF-CMA if $
\mathcal{T
} = (G, f, T)$ is a trapdoor one-way
241 permutation. The standard quantitative result is:
242 \
[ \InSec{euf-cma
}(
\Xid{\mathcal{S
}}{FDH
}^
{\mathcal{T
}, H
}; t, q_S, q_H)
244 q_H
\InSec{owf
}(
\mathcal{T
}; t + O(q_H t_f)). \
]%
245 Here, $t_f$ is the length of time required to compute $f$. The additional
246 $q_H$ term is the number of random oracle (hashing) queries. This doesn't
247 count queries made by the signing oracle.
249 This isn't a terribly promising bound. The problem comes because there is
250 a conflict between getting the adversary to invert the required point, and
251 being able to answer signing queries.
255 Let $A$ be an adversary against $
\Xid{\mathcal{S
}}{FDH
}^
{\mathcal{T
}}$
256 making $q_S$ signing and $q_H$ random oracle queries: we present an
257 inverter $I$ for $
\mathcal{T
}$.
259 Inverter $I(P, y)$: \+ \\
260 $n
\getsr \
{0,
1,
\ldots, q_H -
1\
}$; \\
262 $
\Xid{I
}{map
} \gets \emptyset$; \\
263 $
\Xid{H
}{map
} \gets \emptyset$; \\
264 $(m,
\sigma)
\gets A^
{\id{sign
}(
\cdot),
\id{hash
}(
\cdot)
}(P)$; \\
267 Oracle $
\id{sign
}(m)$: \+ \\
268 \IF $m
\notin \dom \Xid{H
}{map
}$
\THEN \\
\quad \= \+
\kill
269 $h'
\getsr \dom f_P$; \\
270 $h
\gets f_P(h')$; \\
271 $
\Xid{H
}{map
} \gets \Xid{H
}{map
} \cup \
{m
\mapsto h\
}$; \\
272 $
\Xid{I
}{map
} \gets \Xid{I
}{map
} \cup \
{h
\mapsto h'\
}$; \- \\
273 $h
\gets \Xid{h
}{map
}(m)$; \\
274 \IF $h
\notin \dom \Xid{I
}{map
}$
\THEN \ABORT; \\
275 \RETURN $
\Xid{I
}{map
}(h)$;
277 Oracle $
\id{hash
}(x)$: \+ \\
278 \IF $x
\in \dom \Xid{H
}{map
}$
\THEN \RETURN $
\Xid{H
}{map
}(x)$; \\
279 \IF $i = n$
\THEN $h
\gets y$; \\
280 \ELSE \\
\quad \= \+
\kill
281 $h'
\getsr \dom f_P$; \\
282 $h
\gets f_P(h')$; \\
283 $
\Xid{I
}{map
} \gets \Xid{I
}{map
} \cup \
{h
\mapsto h'\
}$; \- \\
284 $
\Xid{H
}{map
} \gets \Xid{H
}{map
} \cup \
{x
\mapsto h\
}$; \\
287 Note that the inverter `cheats' a little. One of its random oracle replies
288 is chosen to be the inverter's input $y$. This is OK, because the rules of
289 the inverter's game say that that $y = f(x)$ for some $x$ chosen uniformly
290 at random from $
\dom f_P$, and hence $y$ is also uniformly distributed and
291 independent, as required.
293 The inverter also `cheats' because it ensures that it knows inverses for
294 all of the queries except for the $n$-th.
296 Let the $q_H$ query strings to the oracle
\id{hash
} be $M = \
{m_0, m_1,
297 \ldots, m_
{q_H-
1}\
}$. Let $m$ be the message returned by $A$ and let
298 $
\sigma$ be the returned signature.
300 Consider the event $N$ that $m
\notin M$; i.e., the random oracle was not
301 queried on the returned message. Then, since $A$ has knowledge of neither
302 $H(M)$ nor $y$, and both are uniformly distributed over $
\dom f_P$, the
303 probability that it succeeds in producing a valid forgery is equal to its
304 probability of successfully returning a correct inversion of $y$.
306 Now consider the complement event $
\lnot N$. Then there is at least a
307 $
1/q_H$ probability that $m = m_n$ -- the one which the inverter must
308 invert -- in which case $I$ succeeds if $A$ does. (The probability might
309 be greater in the event that the adversary queries on the same string
310 several times, though doing so doesn't make a great deal of sense.)
312 Let $F$ be the event that $A$ returns a correct forgery, and let $V$ be the
313 event that $I$ returns a correct inversion. Obviously,
314 \
[ \Pr[F
] =
\Pr[F
\land N
] +
\Pr[F
\land \lnot N
]
315 \quad \text{so
} \quad
316 \Pr[F
\land \lnot N
] =
\Pr[F
] -
\Pr[F
\land N
]. \
]%
317 From the above discussion, we have
318 \
[ \Pr[V
\land N
] =
\Pr[F
\land N
]
319 \quad \text{and
} \quad
320 \Pr[V
\land \lnot N
] \ge \frac{1}{q_H
} \Pr[F
\land \lnot N
]. \
]%
322 \begin{eqnarray*
}[rl
]
323 \Pr[V
] &=
\Pr[V
\land N
] +
\Pr[V
\land \lnot N
] \\
324 &
\ge \Pr[F
\land N
] +
\frac{1}{q_H
} \Pr[F
\land \lnot N
] \\
326 (
\Pr[F
\land N
] +
\Pr[F
] -
\Pr[F
\land \lnot N
]) \\
327 &=
\frac{1}{q_H
} \Pr[F
].
333 Most statements of this result seem to charge the adversary for hash
334 queries made by the experiment and by the constructed inverter, which seems
335 unreasonable. The above result shows that the standard security bound
336 still holds, even under more generous accounting.
339 \xcalways\subsection{The Probabilistic Signature Scheme
}\x
342 \head{The Probabilistic Signature Scheme
\cite{Bellare:
1996:ESD
}}
344 We can improve the security bounds on FDH by making the signing operation
347 Let $
\mathcal{T
} = (G, f, T)$ be a trapdoor one-way function generator, as
348 before, but this time we require that the problem of inverting $f$ be
349 \emph{self-reducible
}.
351 For some public parameter $P$, choose $n$ such that $
2^
{8n
} \le
352 |
{\dom f_P
}| <
2^
{8n+
1}$, and fix a security parameter $k$. Then we need
353 two random oracles $H
\colon \
{0,
1\
}^*
\to \
{0,
1\
}^k$ and $H'
\colon \
{0,
354 1\
}^k
\to \
{0,
1\
}^
{8n-k
}$.
359 \head{Definition of PSS
}
361 We define the signature scheme $
\Xid{\mathcal{S
}}{PSS
}^
{\mathcal{T
}} =
362 (
\Xid{G
}{PSS
}^
{\mathcal{T
}, H(
\cdot), H'(
\cdot)
},
363 \Xid{S
}{PSS
}^
{\mathcal{T
}, H(
\cdot), H'(
\cdot)
},
\Xid{V
}{PSS
}^
{\mathcal{T
},
364 H(
\cdot), H'(
\cdot)
})$:
366 $
\Xid{G
}{PSS
}^
{\mathcal{T
}, H(
\cdot), H'(
\cdot)
}(x)$: \+ \\
367 $(P, K)
\gets G(x)$; \\
370 $
\Xid{S
}{PSS
}^
{\mathcal{T
}, H(
\cdot), H'(
\cdot)
}(K, m)$: \+ \\
371 $r
\getsr \
{0,
1\
}^k$; \\
372 $h
\gets H(m
\cat r)$; \\
373 $h'
\gets (r
\cat 0^
{8n-
2k
})
\xor H'(h)$; \\
374 $y
\gets 0^
8 \cat h
\cat h'$; \\
377 $
\Xid{V
}{PSS
}^
{\mathcal{T
}, H(
\cdot), H'(
\cdot)
}
378 (P, m,
\sigma)$: \+ \\
379 $y
\gets f_P(
\sigma)$; \\
380 \PARSE $y$
\AS $z, k
\colon h,
8n - k
\colon h'$; \\
381 \PARSE $h'
\xor H'(h)$
\AS $k
\colon r, z$; \\
382 \IF $z =
0 \land z' =
0 \land h = H(m
\cat r)$
383 \THEN \RETURN $
1$; \\
389 \head{Diagram of PSS
}
391 %% m <- {0,1}^* r <-R {0, 1}^k
395 %% [H]<---------------------------|
399 %% | [||]<---- 0^{8n-2k}
403 %% |-----------[H']------------>(+)
407 %% < 00 > < s = H(m || r) > < (r || 0^{8n-2k}) (+) H'(s) >
412 {m
\in \
{0,
1\
}^*
}="m"
[rrrr
] {r
\inr \
{0,
1\
}^k
}="r"
413 "m" :
[d
] *+
[F
]{H
}="h"
414 :
[ddd
] *+=(
2,
0)+
[F:thicker
]{\strut s = H(m
\cat r)
}
415 []!
{-(
2.5,
0)
} *+=(
1,
0)+
[F:thicker
]{\strut \hex{00}}
416 "r" :
[dd
] *
{\ocat}="cat"
[r
] *+
[r
]{\mathstrut 0^
{8n-
2k
}} :"cat"
417 :
[d
] *
{\xor}="x"
[uu
] :"h"
418 "m"
[ddd
] :
[rr
] *+
[F
]{H'
} :"x"
419 :
[d
] *+=(
4,
0)+
[F:thicker
]{\strut t = (r
\cat 0^
{8n-
2k
})
\xor H'(s)
}
425 \topic{security results
}
426 \head{Security results for PSS
}
428 For the PSS scheme we've seen, we have
429 \begin{eqnarray*
}[Ll
]
430 \InSec{euf-cma
}(
\Xid{\mathcal{S
}}{PSS
}^
{\mathcal{T
}};
431 t, q_S, q_H, q_
{H'
})
\le \\
432 &
\InSec{owf
}(
\mathcal{T
}; t + O(t_n (q_S + q_H) + q_
{H'
})) +
433 \frac{3(q_H + q_
{H'
} +
2)
}{2^k
}.
435 Here, $q_H$ and $q_H$ are the number of queries to the random oracles $H$
436 and $H'$, and $t_n$ is a magical constant relating to, among other things,
437 the time required for the self-reduction on the original problem and the
438 difference between $|
{\dom f_P
}|$ and $
2^
{8n
}$. For RSA or Rabin with a
439 multiple-of-
8-bit modulus, $t_n$ will be some small multiple of $k$ times
440 the length of time for a public key operation.
444 Suppose $A$ can forge a signature under the
445 $
\Xid{\mathcal{S
}}{PSS
}^
{\mathcal{T
}}$ scheme. We present an inverter $I$
446 which inverts $
\mathcal{T
}$.
448 We shall need to make use of the self-reducibility property of inverting
449 $
\mathcal{T
}$. To do this in an abstract way, we require two algorithms:
451 \item $
\id{sr-choose
}(P, y)$ returns a pair $(s, y')$, where $s$ is some
452 state information, and $y'$ is a new problem instance uniformly selected
453 from the domain of $f_P$; and
454 \item $
\id{sr-solve
}(s, x)$ solves an instance of the problem given a
455 solution to the instance created by
\id{sr-choose
}.
457 If $P$ is a public parameter for $f$, $y$ is some point in $
\ran f_P$,
458 $
\id{sr-choose
}(P, y)$ returns $(s, y')$ and $f_P(x') = y'$ then we require
459 that $
\id{sr-solve
}(s, x')$ returns an $x$ such that $f_P(x) = y$.
461 By way of example, we present implementations of these algorithms for the
462 RSA function, where $P = (n, e)$:
464 Algorithm $
\id{sr-choose
}(P, y)$: \+ \\
466 \REPEAT $z
\getsr \
{1,
2,
\ldots, n -
1\
}$; \\
467 \UNTIL $
\gcd(z, n) =
1$; \\
468 $s
\gets (n, z^
{-
1} \bmod n)$; \\
469 \RETURN $(s, y z^e
\bmod n)$;
471 Algorithm $
\id{sr-solve
}(s, x')$: \+ \\
473 \RETURN $x' i
\bmod n$;
475 (The loop in
\id{sr-choose
} hardly ever needs more than one iteration.
476 Indeed, if the condition $
\gcd{z, n
} =
1$ fails, we've found a factor,
477 and could use that to solve the problem instance directly.) We shall
478 assume that the
\id{sr-choose
} algorithm effectively completes in
481 We shall also need to be able to convert between elements of $
\ran f_P$ and
482 binary strings. We shall assume that there is a `natural' mapping between
483 the integers $\
{0,
1,
\ldots, |
{\ran f_P
}| -
1\
}$ and the elements of $
\ran
484 f_P$, and omit explicit conversions.
486 The inverter algorithm is shown in figure~
\ref{fig:pss-inverter
}.
490 Inverter $I(P, y)$: \+ \\
491 $
\Xid{H
}{map
} \gets \emptyset$; \\
492 $
\Xid{H'
}{map
} \gets \emptyset$; \\
493 $
\Xid{I
}{map
} \gets \emptyset$; \\
494 $
\Xid{m
}{list
} \gets \emptyset$; \\
495 $(m,
\sigma)
\gets A^
{\id{sign
}(
\cdot), H(
\cdot), H'(
\cdot)
}(P)$; \\
496 \IF $m
\in \Xid{m
}{list
}$
\THEN \ABORT; \\
497 $y'
\gets f_P(
\sigma)$; \\
498 \PARSE $y'$
\AS $z, k
\colon h,
8n - k
\colon g$; \\
499 \PARSE $g
\xor H'(h)$
\AS $k
\colon r, z'$; \\
500 $x
\gets m
\cat r$; \\
501 \IF $z
\ne 0 \lor z'
\ne 0$
\THEN \ABORT; \\
502 \IF $h
\ne H(x)$
\THEN \ABORT; \\
503 \IF $x
\notin \dom \Xid{I
}{map
}$
\THEN \ABORT; \\
504 \RETURN $
\id{sr-solve
}(
\Xid{I
}{map
}(x),
\sigma)$;
506 Oracle $
\id{sign
}(m)$: \+ \\
507 $r
\getsr \
{0,
1\
}^k$; \\
508 $x
\gets m
\cat r$; \\
509 \IF $x
\in \dom \Xid{H
}{map
}$
\THEN \ABORT; \\
510 \REPEAT \\
\quad \= \+
\kill
511 $
\sigma'
\getsr \ran f_P$; \\
512 $y'
\gets f_P(
\sigma')$; \- \\
513 \UNTIL $y' <
2^
{8n
}$; \\
514 \PARSE $y'$
\AS $z, k
\colon h,
8n - k
\colon g$; \\
515 \PARSE $g$
\AS $k
\colon r', g'$; \\
516 $h'
\gets (r
\xor r')
\cat g'$; \\
517 \IF $h
\in \dom \Xid{H'
}{map
}$
\THEN \ABORT; \\
518 $
\Xid{H
}{map
} \gets \Xid{H
}{map
} \cup \
{x
\mapsto h\
}$; \\
519 $
\Xid{H'
}{map
} \gets \Xid{H'
}{map
} \cup \
{h
\mapsto h'\
}$; \\
520 $
\Xid{m
}{list
} \gets \Xid{m
}{list
} \cup \
{m\
}$; \\
524 \IF $x
\in \dom \Xid{H
}{map
}$
\THEN \RETURN $
\Xid{H
}{map
}(x)$; \\
525 \REPEAT \\
\quad\=\+
\kill
526 $(s, y')
\gets \id{sr-choose
}(P, y)$; \\
527 \PARSE $x$
\AS $m, k
\colon r$; \- \\
528 \UNTIL $y' <
2^
{8n
}$; \\
529 \PARSE $y'$
\AS $z, k
\colon h,
8n - k
\colon g$; \\
530 \PARSE $g$
\AS $k
\colon r', g'$; \\
531 $h'
\gets (r
\xor r')
\cat g'$; \\
532 \IF $h
\in \dom \Xid{H'
}{map
}$
\THEN \ABORT; \\
533 $
\Xid{H
}{map
} \gets \Xid{H
}{map
} \cup \
{x
\mapsto h\
}$; \\
534 $
\Xid{H'
}{map
} \gets \Xid{H'
}{map
} \cup \
{h
\mapsto h'\
}$; \\
535 $
\Xid{I
}{map
} \gets \Xid{I
}{map
} \cup \
{x
\mapsto s\
}$; \\
536 \RETURN $h$; \- \\
[\smallskipamount]
537 Oracle $H'(x)$: \+ \\
538 \IF $x
\in \dom \Xid{H'
}{map
}$
\THEN \RETURN $
\Xid{H'
}{map
}(x)$; \\
539 $h'
\gets \
{0,
1\
}^
{8n - k
}$ \\
540 $
\Xid{H'
}{map
} \gets \Xid{H'
}{map
} \cup \
{h
\mapsto h'\
}$; \\
543 \caption{From the security proof of PSS -- the inverter for the trapdoor
545 \label{fig:pss-inverter
}
548 The oracle $H$ constructs related instances of the original inversion
549 problem and uses them to build the random oracle results. Because the
550 subroutine
\id{sr-choose
} selects problem instances uniformly over $\
{0,
551 1,
\ldots, |
{\ran f_P
}| -
1\
}$, and we iterate until $y' <
2^
{8n
}$, the
552 selected instance $y'$ is uniform over $\
{0,
1\
}^
{8n
}$. We then construct
553 $H$ and $H'$ replies as appropriate for the adversary to construct $y'$ as
554 a message representative for its chosen message $m$, such that if it
555 responds with a signature for $m$ then we can use
\id{sr-solve
} to solve
558 The oracle
\id{sign
} chooses oracle responses in order to fit in with a
559 previously chosen inverse (computed the easy way, by choosing a point in
560 the domain of $f_P$ and computing its image).
562 The oracle $H'$ just chooses random values.
564 Most of the
\ABORT statements in the main inverter routine detect incorrect
565 signatures. The final one, asserting $x
\notin \Xid{I
}{map
}$, can't happen
566 unless the signature is a duplicate of one we already gave.
568 The
\ABORT{}s in $H$ and
\id{sign
} detect conditions in which the
569 adversary has successfully distinguished its simulated environment from
570 that of the standard forging experiment.
572 The inverter succeeds whenever a correct forgery is made. To conclude the
573 proof, we must bound the probability that an
\ABORT occurs in $H$ or
576 The
\ABORT in $H$ occurs when the chosen $H(x)$ collides with a value for
577 which $H'$ is already defined. Since $H(x)$ values are chosen uniformly
578 from $\
{0,
1\
}^k$, this occurs with probability no more than $(q_H +
581 The first
\ABORT in
\id{sign
} occurs when the chosen point $x = m
\cat r$
582 already has an image defined in $H$: this happens with probability at most
583 $q_H/
2^k$. The second occurs when $h$ already has an image in $H'$, and
584 occurs with probability at most $(q_H + q_
{H'
})/
2^k$.
586 The loops in $H$ and
\id{sign
} don't complete in a deterministic amount
587 of time. But we can abort if they appear to be taking too long, and choose
588 the maximum number of iterations to achieve any given failure probability.
589 Let $d = |
{\dom f_P
}|$. Then the probability that any particular iteration
590 fails to select an appropriate problem instance is $
1 -
2^
{8n
}/d$. For RSA
591 or Rabin with a modulus bit length which is a multiple of
8, this is less
592 than $
\frac{1}{2}$. We choose the number of iterations in the entire
593 program to be such that we have a $
2^
{-k
}$ probability of failure. Thus,
594 we set our maximum as $-k/
\log_2 (
1-
2^
{8n
}/d)$ iterations in the entire
597 Fitting all of this together, we see that
598 \
[ \Succ{owf
}{\mathcal{T
}}(I)
\ge
599 \Succ{euf-cma
}{\Xid{\mathcal{S
}}{PSS
}^
{\mathcal{T
}}} -
600 \frac{3(q_H + q_
{H'
} +
2)
}{2^k
}. \
]%
601 completing the proof.
608 %%% TeX-master: "ips"