RSA ⇒ Claw-free TDP

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

If RSA is hard for , the following is a claw-free pair of trapdoor permutations — folklore. samples and , and outputs the pair

of permutations of , computable in polynomial time from the index , with trapdoors and : and . The domain sampler draws until , for at most trials, and outputs if all fail; since for distinct primes , its output is within statistical distance of uniform on — standard.

Sketch

Given an RSA challenge , the reduction runs the claw finder on the pair , which is distributed as outputs it, since for uniform is uniform in . A claw with gives , so inverts the challenge — standard.