Article

On the composition of authenticated byzantine agreement

Authors:

Yehuda Lindell,

Anna Lysyanskaya,

Tal RabinAuthors Info & Claims

STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing

Pages 514 - 523

https://doi.org/10.1145/509907.509982

Published: 19 May 2002 Publication History

Abstract

A fundamental problem of distributed computing is that of simulating a (secure) broadcast channel, within the setting of a point-to-point network. This problem is known as Byzantine Agreement and has been the focus of much research. Lamport et al. showed that in order to achieve Byzantine Agreement in the standard model, more than 2/3 of the participating parties must be honest. They further showed that by augmenting the network with a public-key infrastructure, it is possible to obtain secure protocols for any number of faulty parties. This augmented problem is called "authenticated Byzantine Agreement".In this paper we consider the question of concurrent, parallel and sequential composition of authenticated Byzantine Agreement protocols. We present surprising impossibility results showing that:

Authenticated Byzantine Agreement cannot be composed in parallel or concurrently (even twice), if 1/3 or more of the parties are faulty.

Deterministic authenticated Byzantine Agreement protocols that run for r rounds and tolerate 1/3 or more faulty parties, can only be composed sequentially less than 2r times.

In contrast, we present randomized protocols for authenticated Byzantine Agreement that compose sequentially for any polynomial number of times. We exhibit two such protocols: The first protocol tolerates corruptions of up to 1/2 of themparties, while In the first protocol, the number of faulty parties may be any number less than 1/2. On the other hand, the second protocol can tolerate any number of faulty parties, but is limited to the case that the overall number of parties is O(log k), where k is a security parameter. Finally, we show that when the model is further augmented so that unique and common session identifiers are assigned to each concurrent session, then any polynomial number of authenticated Byzantine agreement protocols can be concurrently executed, while tolerating any number of faulty parties.

References

[1]

D. Beaver. Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority. Journal of Cryptology, 4:75--122, 1991.]]

Digital Library

[2]

R. Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143--202, 2000.]]

Digital Library

[3]

R. Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In 42st FOCS, pages 136--145. 2001.]]

Digital Library

[4]

R. Canetti, J. Kilian, E. Petrank, and A. Rosen. Black-Box Concurrent Zero-Knowledge Requires Omega(log n) Rounds. In 33th STOC, pages 570--579. 2001.]]

Digital Library

[5]

Y. Dodis and S. Micali. Parallel Reducibility for Information-Theoretically Secure Computation. In Crypto '00, pages 74--92, 2000. LNCS No. 1880.]]

Digital Library

[6]

C. Dwork, M. Naor, and A. Sahai. Concurrent zero-knowledge. In 30th STOC, pages 409--418. 1998.]]

Digital Library

[7]

M. Fischer, N. Lynch, and M. Merritt. Easy Impossibility Proofs for Distributed Consensus Problems. Distributed Computing, 1(1):26--39, 1986.]]

Digital Library

[8]

M. Fitzi and U. Maurer. From partial consistency to global broadcast. In 32th STOC, pages 494--503. 2000.]]

Digital Library

[9]

O. Goldreich. Concurrent Zero-Knowledge With Timing Revisited. In 34th STOC. 2002.]]

Digital Library

[10]

O. Goldreich and H. Krawczyk. On the composition of zero-knowledge proof systems. SIAM. J. Computing, 25(1):169--192, 1996.]]

Digital Library

[11]

S. Goldwasser, S. Micali, and R. L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Computing, 17(2):281--308, Apr. 1988.]]

Digital Library

[12]

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

[13]

L. Lamport, R. Shostack, and M. Pease. The Byzantine generals problem. ACM Trans. Prog. Lang. and Systems, 4(3):382--401, 1982.]]

Digital Library

[14]

S. Micali and P. Rogaway. Secure computation. In Crypto '91, pages 392--404, 1991. LNCS No. 576.]]

Digital Library

[15]

M. Pease, R. Shostak, and L. Lamport. Reaching Agreement in the Presence of Faults. Journal of the ACM, 27(2):228--234, 1980.]]

Digital Library

[16]

B. Pfitzmann and M. Waidner. Information-Theoretic Pseudosignatures and Byzantine Agreement for t ρ= n/3$. Technical Report RZ 2882 (#90830), IBM Research, 1996.]]

[17]

R. Richardson and J. Kilian. On the concurrent composition of zero-knowledge proofs. In Eurocrypt '99, pages 311--326, 1999. LNCS No. 1592.]]

Digital Library

[18]

R. L. Rivest, A. Shamir, and L. M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communication of the ACM, 21(2):120--126, 1978.]]

Digital Library

Cited By

Brorsson JDavid BGentile LPagnin EWagner P(2023)PAPR: Publicly Auditable Privacy Revocation for Anonymous CredentialsTopics in Cryptology – CT-RSA 202310.1007/978-3-031-30872-7_7(163-190)Online publication date: 19-Apr-2023
https://doi.org/10.1007/978-3-031-30872-7_7
Canetti R(2020)Universally Composable SecurityJournal of the ACM10.1145/340245767:5(1-94)Online publication date: 16-Sep-2020
https://dl.acm.org/doi/10.1145/3402457
Baum CDavid BDowsley R(2020)Insured MPC: Efficient Secure Computation with Financial PenaltiesFinancial Cryptography and Data Security10.1007/978-3-030-51280-4_22(404-420)Online publication date: 18-Jul-2020
https://doi.org/10.1007/978-3-030-51280-4_22
Show More Cited By

Index Terms

On the composition of authenticated byzantine agreement

Recommendations

On the composition of authenticated Byzantine Agreement

A fundamental problem of distributed computing is that of simulating a secure broadcast channel, within the setting of a point-to-point network. This problem is known as Byzantine Agreement (or Generals) and has been the focus of much research. Lamport ...
Grouping Byzantine Agreement

The reliability of the distributed system has always been an important topic of research. Byzantine Agreement (BA) protocol, which allows the fault-free processors to agree on a common value, is one of the most fundamental problems studied in a ...
Detectable byzantine agreement secure against faulty majorities
PODC '02: Proceedings of the twenty-first annual symposium on Principles of distributed computing

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

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing

May 2002

840 pages

ISBN:1581134959

DOI:10.1145/509907

Conference Chair:
John Reif
Duke University

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

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC02

Sponsor:

SIGACT

STOC02: Symposium on the Theory of Computing

May 19 - 21, 2002

Quebec, Montreal, Canada

Acceptance Rates

STOC '02 Paper Acceptance Rate 91 of 287 submissions, 32%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
19
Total Downloads

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

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Brorsson JDavid BGentile LPagnin EWagner P(2023)PAPR: Publicly Auditable Privacy Revocation for Anonymous CredentialsTopics in Cryptology – CT-RSA 202310.1007/978-3-031-30872-7_7(163-190)Online publication date: 19-Apr-2023
https://doi.org/10.1007/978-3-031-30872-7_7
Canetti R(2020)Universally Composable SecurityJournal of the ACM10.1145/340245767:5(1-94)Online publication date: 16-Sep-2020
https://dl.acm.org/doi/10.1145/3402457
Baum CDavid BDowsley R(2020)Insured MPC: Efficient Secure Computation with Financial PenaltiesFinancial Cryptography and Data Security10.1007/978-3-030-51280-4_22(404-420)Online publication date: 18-Jul-2020
https://doi.org/10.1007/978-3-030-51280-4_22
Goldreich O(2019)On the foundations of cryptographyProviding Sound Foundations for Cryptography10.1145/3335741.3335759(411-496)Online publication date: 4-Oct-2019
https://dl.acm.org/doi/10.1145/3335741.3335759
Cohen RCoretti SGaray JZikas V(2019)Probabilistic Termination and Composability of Cryptographic ProtocolsJournal of Cryptology10.1007/s00145-018-9279-y32:3(690-741)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s00145-018-9279-y
Cohen RCoretti SGaray JZikas V(2016)Probabilistic Termination and Composability of Cryptographic ProtocolsProceedings, Part III, of the 36th Annual International Cryptology Conference on Advances in Cryptology --- CRYPTO 2016 - Volume 981610.1007/978-3-662-53015-3_9(240-269)Online publication date: 14-Aug-2016
https://dl.acm.org/doi/10.1007/978-3-662-53015-3_9
Chandran NChongchitmate WGaray JGoldwasser SOstrovsky RZikas VRoughgarden T(2015)The Hidden Graph ModelProceedings of the 2015 Conference on Innovations in Theoretical Computer Science10.1145/2688073.2688102(153-162)Online publication date: 11-Jan-2015
https://dl.acm.org/doi/10.1145/2688073.2688102
Hong YVaidya JWang S(2013)A Survey of Privacy-Aware Supply Chain Collaboration: From Theory to ApplicationsJournal of Information Systems10.2308/isys-5069228:1(243-268)Online publication date: 1-Dec-2013
https://doi.org/10.2308/isys-50692
Gupta AGopal PBansal PSrinathan K(2010)Authenticated Byzantine generals in dual failure modelProceedings of the 11th international conference on Distributed computing and networking10.5555/2018057.2018072(79-91)Online publication date: 3-Jan-2010
https://dl.acm.org/doi/10.5555/2018057.2018072
Gupta AHans SSrinathan KRangan C(2010)On composability of reliable unicast and broadcastProceedings of the 11th international conference on Distributed computing and networking10.5555/2018057.2018070(54-66)Online publication date: 3-Jan-2010
https://dl.acm.org/doi/10.5555/2018057.2018070
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