You are looking at a specific version 20171227:213023 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.