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

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

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