Paper 2017/631
Certifying Trapdoor Permutations, Revisited
Ran Canetti and Amit Lichtenberg
Abstract
The modeling of trapdoor permutations has evolved over the years. Indeed, finding an appropriate abstraction that bridges between the existing candidate constructions and the needs of applications has proved to be challenging. In particular, the notions of certifying permutations (Bellare and Yung, 96), enhanced and doubly enhanced trapdoor permutations (Goldreich, 04, 08, 11, Goldreich and Rothblum, 13) were added to bridge the gap between the modeling of trapdoor permutations and needs of applications. We identify an additional gap in the current abstraction of trapdoor permutations: Previous works implicitly assumed that it is easy to recognize elements in the domain, as well as uniformly sample from it, even for illegitimate function indices. We demonstrate this gap by using the (Bitansky-Paneth-Wichs, 15) doubly-enhanced trapdoor permutation family to instantiate the Feige-Lapidot-Shamir (FLS) paradigm for constructing non-interactive zero-knowledge (NIZK) protocols, and show that the resulting proof system is unsound. To close this gap, we propose a general notion of certifiably injective doubly enhanced trapdoor functions, which provide a way of certifying that a given key defines an injective function over the domain defined by it, even when that domain is not efficiently recognizable and sampleable. We show that this notion suffices for instantiating the FLS paradigm; more generally, we argue that this notion is needed whenever the generation process of the function is not trusted. We then show two very different ways to realize this notion: One is via the traditional method of RSA/Rabin with the Bellare-Yung certification mechanism, and the other using indistinguishability obfuscation and injective pseudorandom generators. In particular the latter is the first candidate injective trapdoor function from assumptions other than factoring, that suffices for the FLS paradigm.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Non-Interactive Zero-KnowledgeTrapdoor PermutationsIndistinguishability Obfuscation
- Contact author(s)
- amitlich @ post tau ac il
- History
- 2018-09-25: last of 6 revisions
- 2017-06-27: received
- See all versions
- Short URL
- https://ia.cr/2017/631
- License
-
CC BY