On the Round Complexity of Randomized Byzantine Agreement We prove lower bounds on the round complexity of randomized Byzantine agreement (BA) protocols, bounding the halting probability of such protocols after one and two rounds. In particular, we prove that:  :31,BA protocols resilient against n3 resp., n4 corruptions terminate (under attack) at the end of the first round with probability at most o(1) resp., 12 o(1).  :31,BA protocols resilient against :58,n4 corruptions terminate at the end of the second round with probability at most 1Theta(1).  :78,For a large class of protocols (including all :31,BA protocols used in practice) and under a plausible combinatorial conjecture, :31,BA protocols resilient against n3 resp., n4 corruptions terminate at the end of the second round with probability at most o(1) resp., 12  o(1).  :123,141,above bounds hold even when the parties use a trusted setup phase, e.g., a publickey infrastructure (PKI).  third bound essentially matches the recent protocol of Micali (ITCSu002717) that tolerates up to n3 corruptions and terminates at the end of the third round with constant probability.

Estimating Gaps in Martingales and Applications to CoinTossing: Constructions and Hardness Consider designing a distributed cointossing protocol for n processors such that the probability of heads is X0 in 0,1, and an adversary can reset one processor to change the distribution of the final outcome. For X012, in the noncryptographic setting, Blumu0027s majority protocol is frac1sqrt2pi n insecure. For computationally bounded adversaries and any X0 in 0,1, the protocol of Moran,Naor,Segev (2009) is only O(1n) insecure. In this paper, we study discretetime martingales (X0,X1,..,Xn) such that Xi in 0,1, for all i in 0,..,n, and Xn in 0,1. In particular, for any X0 in 0,1, we construct martingales that yield frac12sqrtfracX_0(1X_0)n insecure cointossing protocols with nbit communication; irrespective of the number of bits required to represent the output distribution. Note that for sufficiently small X0, we achieve higher security than Moran et alu0027s protocol even against computationally unbounded adversaries. For X012, our protocol requires only 40% of the processors to obtain the same security as the majority protocol. We introduce a new inductive technique that uses geometric transformations to estimate the large gaps in these martingales. For any X0 in 0,1, we show that there exists a stopping time T such that mathbbEX_TX_T1geqfrac2sqrt2n1cdot X_0(1X_0). The inductive technique also constructs martingales that demonstrate the optimality of our bound  we construct optimal martingales such that any T hasmathbbEX_TX_T1leqfrac1sqrtncdotsqrtX_0(1X_0). Our lowerbound holds for all X0 in 0,1; while the previous bound of Cleve,Impagliazzo (1993) exists only for positive constant X0. Our approach only employs elementary techniques and avoids the complex probabilistic tools inherent to the approaches of Cleve,Impagliazzo (1993) and Beimel,Haitner,Makriyannis,Omri (2018).