Speaker: Ron Rothblum, Weizmann
Title: A Taxonomy of Enhanced Trapdoor Permutations
Abstract:
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.