Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Non-Interactive Zero-Knowledge, Trapdoor Permutations, Indistinguishability Obfuscation

Date: received 27 Jun 2017, last revised 27 Dec 2017

Contact author: amitlich at post tau ac il

Available format(s): PDF | BibTeX Citation

Version: 20171227:213023 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]