Article

Detectable byzantine agreement secure against faulty majorities

Authors:

Matthias Fitzi,

Daniel Gottesman,

Thomas Holenstein,

Adam SmithAuthors Info & Claims

PODC '02: Proceedings of the twenty-first annual symposium on Principles of distributed computing

Pages 118 - 126

https://doi.org/10.1145/571825.571841

Published: 21 July 2002 Publication History

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]

D. Beaver and S. Goldwasser. Multiparty computation with faulty majority. In Advances in Cryptology: CRYPTO '89, pages 589-590, Berlin, Aug. 1990. Springer.]]

Digital Library

[3]

C. H. Bennett and G. Brassard. An update on quantum cryptography. In G. R. Blakley and D. Chaum, editors, Advances in Cryptology: Proceedings of CRYPTO 84, volume 196 of Lecture Notes in Computer Science, pages 475-480. Springer-Verlag, 1985, 19-22 Aug. 1984.]]

Digital Library

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

R. Canetti, U. Feige, O. Goldreich, and M. Naor. Adaptively secure multi-party computation. In Proc. 31st ACM Symposium on the Theory of Computing (STOC), pages 639-648, 1996.]]

Digital Library

[6]

R. Cleve. Limits on the security of coin flips when half the processors are faulty (extended abstract). In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 364-369, Berkeley, California, 28-30 1986.]]

Digital Library

[7]

B. A. Coan, D. Dolev, C. Dwork, and L. Stockmeyer. The distributed firing squad problem, SIAM Journal on Computing, 18(5):990-1012, Oct. 1989.]]

Digital Library

[8]

D. Dolev and H. R. Strong. Authenticated algorithms for Byzantine agreement. SIAM Journal on Computing, 12(4):656-666, 1983.]]

Digital Library

[9]

P. Feldman and S. Micali. An optimal probabilistic protocol for synchronous Byzantine agreement. SIAM Journal on Computing, 26(4):873-933, Aug. 1997.]]

Digital Library

[10]

M. J. Fischer, N. A. Lynch, and M. Merritt. Easy impossibility proofs for distributed consensus problems. Distributed Computing, 1:26-39, 1986.]]

Digital Library

[11]

M. Fitzi, J. A. Garay, U. Maurer, and R. Ostrovsky. Minimal complete primitives for unconditional multi-party computation. In Advances in Cryptology --- CRYPTO 2001, Lecture Notes in Computer Science, 2001.]]

Digital Library

[12]

M. Fitzi, N. Gisin, and U. Maurer. Quantum solution to the Byzantine agreement problem. Physical Review Letters, 87(21), Nov. 2001.]]

[13]

M. Fitzi, N. Gisin, U. Maurer, and O. von Rotz. Unconditional Byzantine agreement and multi-party computation secure against dishonest minorities from scratch. In Advances in Cryptology --- EUROCRYPT 2002, Lecture Notes in Computer Science, 2002.]]

Digital Library

[14]

O. Goldreich. Secure multi-party computation, working draft, version 1.2, Mar. 2000.]]

[15]

O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game --- a completeness theorem for protocols with honest majority. In Proc. 19th ACM Symposium on the Theory of Computing (STOC), pages 218-229, 1987.]]

Digital Library

[16]

S. Goldwasser and L. A. Levin. Fair computation of general functions in presence of immoral majority. In CRYPTO, pages 77-93, 1990.]]

Digital Library

[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, 30(3):668-676, July 1983.]]

Digital Library

[22]

L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382-401, July 1982.]]

Digital Library

[23]

Y. Lindell, A. Lysyanskaya, and T. Rabin. On the composition of authenticated byzantine agreement. In ACM, editor, Proc. 34thACM Symposium on the Theory of Computing (STOC), 2002.]]

Digital Library

[24]

M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, Apr. 1980.]]

Digital Library

[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.]]

Cited By

Weng CGao RBao YLi BLiu WXie YLu YYin HChen Z(2023)Beating the Fault-Tolerance Bound and Security Loopholes for Byzantine Agreement with a Quantum SolutionResearch10.34133/research.02726Online publication date: 21-Nov-2023
https://doi.org/10.34133/research.0272
Zhu JLi FChen J(2023)Communication-Efficient and Error-Free Gradecast with Optimal Resilience2023 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT54713.2023.10206579(108-113)Online publication date: 25-Jun-2023
https://doi.org/10.1109/ISIT54713.2023.10206579
Parida NJatoth CReddy VHussain MFaizi J(2023)Post-quantum distributed ledger technology: a systematic surveyScientific Reports10.1038/s41598-023-47331-113:1Online publication date: 25-Nov-2023
https://doi.org/10.1038/s41598-023-47331-1
Show More Cited By

Detectable byzantine agreement secure against faulty majorities

Recommendations

Asynchronous Byzantine Agreement with optimal resilience

We present an efficient, optimally-resilient Asynchronous Byzantine Agreement (ABA) protocol involving $$n = 3t+1$$n=3t+1 parties over a completely asynchronous network, tolerating a computationally unbounded Byzantine adversary, capable of corrupting ...
Simple and efficient asynchronous byzantine agreement with optimal resilience
PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

Consider a completely asynchronous network consisting of n parties where every two parties are connected by a private channel. An adversary A_t with unbounded computing power actively controls at most t = ([n/3] − 1) out of n parties in Byzantine ...
Secure Multi-Party Computation without Agreement

It has recently been shown that authenticated Byzantine agreement, in which more than a third of the parties are corrupted, cannot be securely realized under concurrent or parallel (stateless) composition. This result puts into question any usage of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '02: Proceedings of the twenty-first annual symposium on Principles of distributed computing

July 2002

307 pages

ISBN:1581134851

DOI:10.1145/571825

Conference Chair:
Aleta Ricciardi
Valaran Corp.

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 July 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC02

Sponsor:

PODC02: Principles of Distributed Computing

July 21 - 24, 2002

California, Monterey

Acceptance Rates

PODC '02 Paper Acceptance Rate 43 of 149 submissions, 29%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
638
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Weng CGao RBao YLi BLiu WXie YLu YYin HChen Z(2023)Beating the Fault-Tolerance Bound and Security Loopholes for Byzantine Agreement with a Quantum SolutionResearch10.34133/research.02726Online publication date: 21-Nov-2023
https://doi.org/10.34133/research.0272
Zhu JLi FChen J(2023)Communication-Efficient and Error-Free Gradecast with Optimal Resilience2023 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT54713.2023.10206579(108-113)Online publication date: 25-Jun-2023
https://doi.org/10.1109/ISIT54713.2023.10206579
Parida NJatoth CReddy VHussain MFaizi J(2023)Post-quantum distributed ledger technology: a systematic surveyScientific Reports10.1038/s41598-023-47331-113:1Online publication date: 25-Nov-2023
https://doi.org/10.1038/s41598-023-47331-1
Qu ZZhang ZLiu BTiwari PNing XMuhammad K(2023)Quantum detectable Byzantine agreement for distributed data trust management in blockchainInformation Sciences10.1016/j.ins.2023.03.134637(118909)Online publication date: Aug-2023
https://doi.org/10.1016/j.ins.2023.03.134
Alon BCohen ROmri ESuad T(2023)On the Power of an Honest Majority in Three-Party Computation Without BroadcastJournal of Cryptology10.1007/s00145-023-09456-436:3Online publication date: 7-Jun-2023
https://dl.acm.org/doi/10.1007/s00145-023-09456-4
Yamashita KYasunaga K(2023)Rational Broadcast Protocols Against Timid AdversariesDecision and Game Theory for Security10.1007/978-3-031-50670-3_14(277-293)Online publication date: 29-Dec-2023
https://doi.org/10.1007/978-3-031-50670-3_14
Bacho RCollins DLiu-Zhang CLoss J(2023)Network-Agnostic Security Comes (Almost) for Free in DKG and MPCAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38557-5_3(71-106)Online publication date: 9-Aug-2023
https://doi.org/10.1007/978-3-031-38557-5_3
Abraham IAsharov GMilani AWoelfel P(2022)Gradecast in Synchrony and Reliable Broadcast in Asynchrony with Optimal Resilience, Efficiency, and Unconditional SecurityProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538451(392-398)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538451
Gao XXu JFan J(2022)A Novel Quantum Byzantine Consensus Protocol Based on Malicious Node Prevention Mechanism2022 International Conference on Blockchain Technology and Information Security (ICBCTIS)10.1109/ICBCTIS55569.2022.00053(202-205)Online publication date: Jul-2022
https://doi.org/10.1109/ICBCTIS55569.2022.00053
Kondi YMagri BOrlandi CShlomovits O(2021)Refresh When You Wake Up: Proactive Threshold Wallets with Offline Devices2021 IEEE Symposium on Security and Privacy (SP)10.1109/SP40001.2021.00067(608-625)Online publication date: May-2021
https://doi.org/10.1109/SP40001.2021.00067
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents