RSA ⇒ TDP over bit strings
Statement
Let output moduli of at most bits, and let be a polynomial with , so that is super-polynomial. If the RSA assumption holds for , then for the map with for when , and the identity on the remaining points, is a trapdoor permutation over bit strings with trapdoor — RST01.
Sketch
permutes and inverts it, so permutes each block and inverts . A uniform point of lies in the identity region with probability below , and elsewhere inverting is inverting RSA at a uniform point of , which lies outside with probability , negligible — standard.