Enhanced TDP ⇒ TDP

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

Statement

An enhanced trapdoor permutation is a trapdoor permutation with the same algorithms — folklore.

Sketch

Given an enhanced challenge , the reduction runs an inverter of on . Since is a bijection, is uniform for uniform , and is within of it, so the inverter succeeds with probability at least its success minus .