Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > A-Z > Z:
A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

Z
TR02-001 | 8th January 2002
Cynthia Dwork, Moni Naor

#### Zaps and Their Applications

A zap is a two-round, witness-indistinguishable protocol in which
the first round, consisting of a message from the verifier to the
prover, can be fixed once-and-for-all" and applied to any instance,
and where the verifier does not use any private coins.
We present a zap for every language in NP, ... more >>>

TR14-068 | 5th May 2014
Eric Allender, Bireswar Das

#### Zero Knowledge and Circuit Minimization

Revisions: 1

We show that every problem in the complexity class SZK (Statistical Zero Knowledge) is
efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RP^MCSP.

This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these ... more >>>

TR06-139 | 14th November 2006

#### Zero Knowledge and Soundness are Symmetric

Revisions: 1

We give a complexity-theoretic characterization of the class of problems in NP having zero-knowledge argument systems that is symmetric in its treatment of the zero knowledge and the soundness conditions. From this, we deduce that the class of problems in NP intersect coNP having zero-knowledge arguments is closed under complement. ... more >>>

TR14-160 | 27th November 2014
Gil Cohen, Igor Shinkar

An $(n,k)$-bit-fixing source is a distribution on $n$ bit strings, that is fixed on $n-k$ of the coordinates, and jointly uniform on the remaining $k$ bits. Explicit constructions of bit-fixing extractors by Gabizon, Raz and Shaltiel [SICOMP 2006] and Rao [CCC 2009], extract $(1-o(1)) \cdot k$ bits for $k = ... more >>> TR14-078 | 7th June 2014 Mika Göös, Toniann Pitassi, Thomas Watson #### Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication We study whether information complexity can be used to attack the long-standing open problem of proving lower bounds against Arthur--Merlin (AM) communication protocols. Our starting point is to show that---in contrast to plain randomized communication complexity---every boolean function admits an AM communication protocol where on each yes-input, the distribution of ... more >>> TR02-063 | 3rd December 2002 Oded Goldreich #### Zero-Knowledge twenty years after its invention Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, contributed to the development of other areas of cryptography and complexity ... more >>> TR02-015 | 13th February 2002 Philippe Moser #### ZPP is hard unless RP is small Revisions: 1 We use Lutz's resource bounded measure theory to prove that either \tbf{RP} is small or \tbf{ZPP} is hard. More precisely we prove that if \tbf{RP} has not p-measure zero, then \tbf{EXP} is contained in$\mbf{ZPP}/n\$.
We also show that if \tbf{RP} has not p-measure zero,
\tbf{EXP} equals ... more >>>

ISSN 1433-8092 | Imprint