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 “blackbox” trapdoor permutation, then the poor exact security is unavoidable. More specifically, the “security loss”
for general trapdoor permutations is Ω(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 bene.ts of the RSA-based variants come into effect once f comes from a family of claw-free permutation pairs. Our results signifucantly narrow the current “gap” between general trapdoor permutations and RSA to the “gap” between trapdoor permutations and claw-free permutations. 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 tradeo. between security and efficiency when deployed with claw-free permutations.