Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-159 | 4th September 2012 10:18

Enhancements of Trapdoor Permutations

RSS-Feed




Revision #1
Authors: Oded Goldreich, Ron Rothblum
Accepted on: 4th September 2012 10:18
Downloads: 3104
Keywords: 


Abstract:

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.



Changes to previous version:

Discussion on enhancements of 1-1 trapdoor functions and other minor changes.


Paper:

TR11-159 | 27th November 2011 19:26

Enhancements of Trapdoor Permutations





TR11-159
Authors: Oded Goldreich, Ron Rothblum
Publication: 27th November 2011 19:34
Downloads: 4525
Keywords: 


Abstract:

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.


Comment(s):

Comment #1 to TR11-159 | 28th March 2018 18:35

Basing NIZKs on Doubly-Enhanced TDP

Authors: Ron Rothblum
Accepted on: 28th March 2018 18:35
Keywords: 


Comment:

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.




ISSN 1433-8092 | Imprint