Detectable byzantine agreement secure against faulty majorities

ABSTRACT

It is well-known that n players, connected only by pairwise secure channels, can achieve Byzantine agreement only if the number t of cheaters satisfies t < n/3, even with respect to computational security. However, for many applications it is sufficient to achieve detectable broadcast. With this primitive, broadcast is only guaranteed when all players are non-faulty ("honest"), but all non-faulty players always reach agreement on whether broadcast was achieved or not. We show that detectable broadcast can be achieved regardless of the number of faulty players (i.e., for all t < n). We give a protocol which is unconditionally secure, as well as two more efficient protocols which are secure with respect to computational assumptions, and the existence of quantum channels, respectively.These protocols allow for secure multi-party computation tolerating any t < n, assuming only pairwise authenticated channels. Moreover, they allow for the setup of public-key infrastructures that are consistent among all participants --- using neither a trusted party nor broadcast channels.Finally, we show that it is not even necessary for players to begin the protocol at the same time step. We give a "detectable Firing Squad" protocol which can be initiated by a single user at any time and such that either all honest players end up with synchronized clocks, or all honest players abort.

REFERENCES

• 1: H. Barnum, C. Crépeau, D. Gottesman, A. Smith, and A. Tapp. Authentication of quantum messages. Manuscript, 2001.
• 2: Donald Beaver , Shafi Goldwasser, Multiparty computation with faulty majority, Proceedings on Advances in cryptology, p.589-590, July 1989, Santa Barbara, California, United States
• 3: Charles H Bennett , Gilles Brassard, An update on quantum cryptography, Proceedings of CRYPTO 84 on Advances in cryptology, p.475-480, August 1985, Santa Barbara, California, United States
• 4: J. E. Burns and N. A. Lynch. The byzantine firing squad problem. In F. P. Preparata, editor, Advances in Computing Research, Parallel and Distributed Computing, volume 4, pages 147-161. JAI Press, Inc., Greenwich, Conn., 1987.
• 5: Ran Canetti , Uri Feige , Oded Goldreich , Moni Naor, Adaptively secure multi-party computation, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.639-648, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238015]
• 6: R Cleve, Limits on the security of coin flips when half the processors are faulty, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.364-369, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12168]
• 7: B. A. Coan , D. Dolev , C. Dwork , L. Stockmeyer, The distributed firing squad problem, SIAM Journal on Computing, v.18 n.5, p.990-1012, Oct. 1989 [doi>10.1137/0218068]
• 8: D. Dolev and H. R. Strong. Authenticated algorithms for Byzantine agreement. SIAM Journal on Computing, 12(4):656-666, 1983.
• 9: Pesech Feldman , Silvio Micali, An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement, SIAM Journal on Computing, v.26 n.4, p.873-933, Aug. 1997 [doi>10.1137/S0097539790187084]
• 10: Michael J. Fischer , Nancy A. Lynch , Michael Merritt, Easy impossibility proofs for distributed consensus problems, Distributed Computing, v.1 n.1, p.26-39, Jan. 1986 [doi>10.1007/BF01843568]
• 11: Matthias Fitzi , Juan A. Garay , Ueli M. Maurer , Rafail Ostrovsky, Minimal Complete Primitives for Secure Multi-party Computation, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.80-100, August 19-23, 2001
• 12: M. Fitzi, N. Gisin, and U. Maurer. Quantum solution to the Byzantine agreement problem. Physical Review Letters, 87(21), Nov. 2001.
• 13: Matthias Fitzi , Nicolas Gisin , Ueli M. Maurer , Oliver von Rotz, Unconditional Byzantine Agreement and Multi-party Computation Secure against Dishonest Minorities from Scratch, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.482-501, May 02, 2002
• 14: O. Goldreich. Secure multi-party computation, working draft, version 1.2, Mar. 2000.
• 15: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 16: Shafi Goldwasser , Leonid A. Levin, Fair Computation of General Functions in Presence of Immoral Majority, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.77-93, August 11-15, 1990
• 17: S. Goldwasser and Y. Lindell. Secure computation without a broadcast channel. http://eprint.iacr.org/2002/040.ps, Apr. 2002.
• 18: L. Gong, P. Lincoln, and J. Rushby. Byzantine agreement with authentication: Observations and applications in tolerating hybrid and link faults. In Dependable Computing for Critical Applications, 1995.
• 19: D. Gottesman and I. Chuang. Quantum digital signatures. Manuscript, 2001.
• 20: A. Karlin and A. C. Yao. Manuscript.
• 21: L. Lamport, The Weak Byzantine Generals Problem, Journal of the ACM (JACM), v.30 n.3, p.668-676, July 1983 [doi>10.1145/2402.322398]
• 22: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 23: Yehuda Lindell , Anna Lysyanskaya , Tal Rabin, On the composition of authenticated byzantine agreement, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509982]
• 24: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 25: B. Pfitzmann and M. Waidner. Information-theoretic pseudosignatures and byzantine agreement for t >= n/3. Research report, IBM Research, Nov. 1996. Submitted for Publication.

INDEX TERMS

Keywords:
broadcast, byzantine agreement, multi-party computation, public-key infrastructure, quantum signatures