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(qhash), where qhash 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.