**On Monotone Function Closure of Statistical Zero-Knowledge**

*Ronald Cramer and Ivan Damgaard*

**Abstract: **Assume we are given a language L with an honest verifier
perfect zero-knowledge proof system. Assume also that the proof system is an
Arthur-Merlin game with at most 3 moves. The class of such languages
includes all random self-reducible language, and also any language with a
perfect zero-knowledge non-interactive proof.
We show that such a language satisfies a certain closure property, namely
that languages constructed from L by applying certain monotone functions to
statements on membership in L have perfect zero-knowledge proof systems.
The new set of languages we can build includes L itself, but also for
example languages consisting of n words of which at least t are in L.
A similar closure property is shown to hold for the complement of L and for
statistical zero-knowledge. The property we need for the monotone functions used
to build the new languages is that there are efficient secret sharing schemes
for their associated access structures. This includes (but is not necessarily
limited to) all monotone functions with polynomial size monotone formulas.

**Category / Keywords: **Interactive Proofs, Zero-Knowledge, Secret Sharing

**Publication Info: **Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.

**Date: **received May 14th, 1996.

**Contact author: **ivan at daimi aau dk

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Short URL: **ia.cr/1996/003

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]