Trapdoor permutations (TDPs) are among the most widely studied
building blocks of cryptography. Despite the extensive body of
work that has been dedicated to their study, in many setting and
applications (enhanced) trapdoor permutations behave
unexpectedly. In particular, a TDP may become easy to invert when
the inverter is given auxiliary information about the element to
be inverted (e.g., the random coins that sampled the element).
Enhanced TDPs were defined in order to address the latter special
case, but there are settings in which they apparently do not
suffice (as demonstrated by the introduction of doubly-enhanced
TDPs).

We study the hardness of inverting TDP in natural settings, which
reflect the security concerns that arise in various applications
of TDPs to the construction of complex primitives (e.g., Oblivious
Transfer and NIZK). For each such setting, we define a
corresponding variant of the notion of an enhanced TDP such that
this variant is hard to invert in this setting. This yields a
taxonomy of such variants, which lie between enhanced TDPs and
doubly-enhanced TDPs. This work explores this taxonomy and its
relation to various applications.

For example, one of the abstract settings that we consider arises
in the standard protocol for one-out-of-$k$ oblivious transfer,
based on enhanced trapdoor permutations. In the case of $k>2$,
this protocol provides a natural separation between barely
enhanced TDPs and a corresponding variant (which belongs to the
aforementioned taxonomy). We comment that, for the case of $k=2$
the standard protocol is secure as is.