Paper 1996/003

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.

Metadata
Available format(s)
PS
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords
Interactive ProofsZero-KnowledgeSecret Sharing
Contact author(s)
ivan @ daimi aau dk
History
1996-05-14: received
Short URL
https://ia.cr/1996/003
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:1996/003,
      author = {Ronald Cramer and Ivan Damgaard},
      title = {On Monotone Function Closure of Statistical Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 1996/003},
      year = {1996},
      note = {\url{https://eprint.iacr.org/1996/003}},
      url = {https://eprint.iacr.org/1996/003}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.