Welcome to the resource topic for 2002/103
Title:
On the Power of Claw-Free Permutations
Authors: Yevgeniy Dodis, 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.
ePrint: https://eprint.iacr.org/2002/103
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .