All reports by Author Jonathan Katz:

__
TR13-013
| 18th January 2013
__

Daniel Apon, Jonathan Katz, Alex Malozemoff#### One-Round Multi-Party Communication Complexity of Distinguishing Sums

Revisions: 1

__
TR07-065
| 13th July 2007
__

Jonathan Katz#### Which Languages Have 4-Round Zero-Knowledge Proofs?

__
TR06-028
| 21st February 2006
__

Jonathan Katz, Chiu-Yuen Koo#### On Expected Constant-Round Protocols for Byzantine Agreement

Daniel Apon, Jonathan Katz, Alex Malozemoff

We consider an instance of the following problem: Parties $P_1,..., P_k$ each receive an input $x_i$, and a coordinator (distinct from each of these parties) wishes to compute $f(x_1,..., x_k)$ for some predicate $f$. We are interested in one-round protocols where each party sends a single message to the coordinator; ... more >>>

Jonathan Katz

We show that if a language $L$ has a 4-round, black-box, computational zero-knowledge proof system with negligible soundness error, then $\bar L \in MA$. Assuming the polynomial hierarchy does not collapse, this means, in particular, that $NP$-complete languages do not have 4-round zero-knowledge proofs (at least with respect to black-box ... more >>>

Jonathan Katz, Chiu-Yuen Koo

In a seminal paper, Feldman and Micali (STOC '88) show an n-party Byzantine agreement protocol tolerating t < n/3 malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., $t < n/2$), and relying only on the ... more >>>