**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.

**Category / Keywords: **foundations / Trapdoor Permuations, Claw-free Permutations, Full Domain Hash, RSA, Signature Schemes, Black-Box Reductions, Exact Security

**Date: **received 2 Aug 2002

**Contact author: **dodis at cs nyu edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20020802:195029 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]