A Taxonomy of Enhanced Trapdoor Permutations.
Ron D. Rothblum · Electronic colloquium on computational complexity · 2010
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. ∗Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel. Email: [email protected]. This research was partially supported by the Israel Science Foundation (grant No. 1041/08). ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Report No. 145 (2010)