RSA ⇒ TDP over bit strings

Fully-black-box reduction · standard model · RST01 · security loss: additive : an inverter of with advantage gives an RSA solver with advantage at least

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.