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

__
TR14-068
| 5th May 2014
__

Eric Allender, Bireswar Das#### Zero Knowledge and Circuit Minimization

Revisions: 1

__
TR06-139
| 14th November 2006
__

Shien Jin Ong, Salil Vadhan#### Zero Knowledge and Soundness are Symmetric

Revisions: 1

__
TR14-160
| 27th November 2014
__

Gil Cohen, Igor Shinkar#### Zero-Fixing Extractors for Sub-Logarithmic Entropy

__
TR14-078
| 7th June 2014
__

Mika Göös, Toniann Pitassi, Thomas Watson#### Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication

__
TR02-063
| 3rd December 2002
__

Oded Goldreich#### Zero-Knowledge twenty years after its invention

__
TR02-015
| 13th February 2002
__

Philippe Moser#### ZPP is hard unless RP is small

Revisions: 1

Cynthia Dwork, Moni Naor

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 >>>

Eric Allender, Bireswar Das

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 >>>

Shien Jin Ong, Salil Vadhan

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 >>>

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 >>>

Mika Göös, Toniann Pitassi, Thomas Watson

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 >>>

Oded Goldreich

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 >>>

Philippe Moser

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 >>>