###
On the Power of Claw-Free Permutations

by
Yevgeniy Dodis and Leonid Reyzin

**Abstract**
The popular random-oracle-based signature schemes, such as
Probabilistic Signature Scheme (PSS) and Full Domain Hash (FDH), output
a signature of the form [*f*^{-1}(*y*),*pub*],
where *y* somehow
depends on the message signed (and *pub*) and *f*
is some public trapdoor permutation
(typically RSA). Interestingly, all these signature schemes can be
proven *asymptotically* secure for an *arbitrary*
trapdoor permutation *f*,
but their *exact* security seems to be significantly better for
*special* trapdoor permutations like RSA.
This leads to two natural questions: (1) can the asymptotic security
analysis be improved with general trapdoor permutations; and, if not,
(2) what *
general cryptographic assumption* on *f* --- enjoyed by specific
functions like RSA --- is *responsible* for the improved security?

We answer both these questions. First, we show that if *f* is a
"black-box" trapdoor permutation,
then the poor exact security is unavoidable. More
specifically, the "security loss" for general trapdoor permutations is
Omega(q_{hash}), where q_{hash}
is the number of random oracle
queries made by the adversary (which could be quite large). On the
other hand, we show that all the security benefits of the RSA-based
variants come into effect once *f* comes from a family of *claw-free
permutation*
pairs. Our results significantly narrow the current "gap" between
general trapdoor permutations and RSA to the ``gap'' between trapdoor
permutations and clawfree permtuations.
Additionally, they can be viewed as the first *security/efficiency*
separation between these basic cryptographic
primitives. In other words, while it was already believed that certain
cryptographic objects *can* be built from claw-free permutations but
*not*
from general trapdoor permutations,
we show that certain important schemes (like
FDH and PSS) provably work with *either*, but enjoy a much better
tradeoff between security and efficiency when deployed with claw-free
permutations.

This work appears in Security in Communication Networks,
Third International Conference, SCN 2002, Cimato, Galdi,
Persiano, editors, Lecture Notes in Computer Science 2576, © Springer-Verlag, 2003.