We present improved distributed broadcast and MST algorithms that are unconditionally secure against an eavesdropper controlling a fixed set of at most f edges in an n-node m-edge D-diameter graph. We strive for secure algorithms with sublinear round and subquadratic message complexities (in n) for any f. This is in contrast to the exponential or polynomial dependence on f in prior works. Our main results are:

We consider the fundamental problem of designing classical consensus-related distributed abstractions for large-scale networks, where the number of parties can be huge. Specifically, we consider tasks such as Byzantine Agreement, Broadcast, and Committee Election, and our goal is to design scalable protocols in the sense that each honest party processes and sends a number of bits which is sub-linear in n, the total number of parties. In this work, we construct the first such scalable protocols for all of the above tasks. In our protocols, each party processes and sends Õ (√n) bits throughout Õ (1) rounds of communication, and correctness is guaranteed for at most 1/3−є fraction of static byzantine corruptions for every constant є>0 (in the full information model). All previous protocols for the considered agreement tasks were non-scalable, either because the communication complexity was linear or because the computational complexity was super polynomial. We complement our result with a matching lower bound showing that any Byzantine Agreement protocol must have Ω(√n) complexity in our model. Previously, the state of the art was the well-known Ω(∛n) lower bound of Holtby, Kapron, and King (Distributed Computing, 2008).