Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation (Q1924194)

Some cryptographic primitives like trapdoor or one-way functions are in addition to public key cryptosystems also used as ``tools'' in the design of various cryptographic protocols. In such scenarios however, one also has to consider adversarial behavior of communicating parties, particularly in a protocol incorrect creation of such tool could be suspected. Thus, certain certification of the correctness of the tools used during the protocol is needed. The article concentrates on one particular instance of this issue, namely on the use of trapdoor permutations in noninteractive zero-knowledge (NIZK) proofs. First, it is pointed out that in the first step of the NIZK proposed by Feige, Lapidot, and Shamir there is a potential for prover to cheat, and it is suggested that what is needed is to find a way how to certify that a map is really a permutation. Then an NIZK proof that a map is almost a permutation (in a well defined sense) is given and it is shown how this result combined with the Feige, Lapidot, and Sharmir's NIZK proof yields an NIZK proof system for any NP language.