Enhancements of Trapdoor Permutations

Webpage for a paper by Oded Goldreich and Ron Rothblum


We take a closer look at several enhancements of the notion of trapdoor permutations (TDPs). 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.

Errata (2017)

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.

Material available on-line

Back to either Oded Goldreich's homepage or general list of papers.