Paper 2002/103

On the Power of Claw-Free Permutations

Yevgeniy Dodis and Leonid Reyzin

Abstract

Probabilistic Signature Scheme (PSS), Full Domain Hash (FDH) and several of their variants are widely used signature schemes, which can be formally analyzed in the random oracle model. These schemes 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 {\em asymptotically} secure for an {\em arbitrary} trapdoor permutation f, but their {\em exact} security seems to be significantly better for {\em 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 {\em 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 {\em claw-free permutation} pairs. Our results significantly 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 {\em security/efficiency} separation between these basic cryptographic primitives. In other words, while it was already believed that certain cryptographic objects {\em can} be build from claw-free permutations but {\em not} from general trapdoor permutations, we show that certain important schemes (like FDH and PSS) provably work with {\em either}, but enjoy a much better tradeoff between security and efficiency when deployed with claw-free permutations.