We take a closer look at several enhancements of the notion of trapdoor permutations. Specifically, we consider the notions of enhanced trapdoor permutation (Goldreich 2004) and doubly enhanced trapdoor permutation (Goldreich 2008) as well as intermediate notions (Rothblum 2010). These enhancements arose in the study of Oblivious Transfer and NIZK, but they address natural concerns that may arise also in other applications of trapdoor permutations. We clarify why these enhancements are needed in such applications, and show that they actually suffice for these needs.
Discussion on enhancements of 1-1 trapdoor functions and other minor changes.
We take a closer look at several enhancements of the notion of trapdoor permutations. Specifically, we consider the notions of enhanced trapdoor permutation (Goldreich 2004) and doubly enhanced trapdoor permutation (Goldreich 2008) as well as intermediate notions (Rothblum 2010). These enhancements arose in the study of Oblivious Transfer and NIZK, but they address natural concerns that may arise also in other applications of trapdoor permutations. We clarify why these enhancements are needed in such applications, and show that they actually suffice for these needs.
This article, originally posted in 2012, stated that doubly-enhanced trapdoor permutations
suffice for constructing NIZKs for NP.
Unfortunately, as pointed out by Ran Canetti and Amit Lichtenberg (in their work Certifying Trapdoor Permutations, Revisited), the proposed enhancements may not suffice for the NIZK application. One possibility is further enhancing the notion of TDP by mandating (1) that the domain of the permutation be defined and almost uniformly sampleable also when the index is not legitimate, and that (2) this domain be efficiently recognizable. Other possibilities are discussed in the aforementioned work.
