Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation
type: Item
instance of: scholarly article
title: Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation
zbMATH Open document ID: 0861.94013
author: M. Bellare
author: Moti Yung
published in: Journal of Cryptology
publication date: 1997-05-19T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 68P25
zbMATH DE Number: 934939
zbMATH Keywords: cryptographic protocols
zbMATH Keywords: certification
zbMATH Keywords: trapdoor permutations
zbMATH Keywords: noninteractive zero-knowledge (NIZK) proofs
reviewed by: Jozef Vyskoč
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 934939