Certifying permutations: Non-interactive zero-knowledge based on any trapdoor permutation

Authors: M. Bellare and M. Yung

Abstract: In cryptographic protocols it is often necessary to verify/certify the ``tools'' in use. This work demonstrates certain subtleties in treating a family of trapdoor permutations in this context, noting the necessity to ``check'' certain properties of these functions. The particular case we illustrate is that of non-interactive zero-knowledge. We point out that the elegant recent protocol of Feige, Lapidot and Shamir for proving NP statements in non-interactive zero-knowledge requires an additional certification of the underlying trapdoor permutation, and suggest a method for certifying permutations which fills this gap.

Ref: Appears in Journal of Cryptology Vol. 9, No. 1, pp. 149--166, 1996. Extended abstract appeared in Crypto 92. Full paper available below.

Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).