Claw-free TDP ⇒ TDP

Fully-black-box reduction · standard model · folklore · security loss: negligible additive: the sampler’s statistical distance

Statement

A claw-free pair of trapdoor permutations yields a trapdoor permutation on its domain : runs the pair’s generator and outputs , is the pair’s domain sampler, evaluates , and inverts it with — folklore.

Sketch

The reduction draws from the domain sampler and gives to an inverter of . Since is a permutation of , is within the sampler’s statistical distance of uniform, so with the inverter’s success probability up to that distance it returns with , a claw.