File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-030-45388-6_9
- Scopus: eid_2-s2.0-85090019948
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Sublinear-Round Byzantine Agreement Under Corrupt Majority
Title | Sublinear-Round Byzantine Agreement Under Corrupt Majority |
---|---|
Authors | |
Keywords | Byzantine agreement Sublinear round complexity Corrupt majority |
Issue Date | 2020 |
Publisher | Springer. |
Citation | Public-Key Cryptography – PKC 2020: 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Edinburgh, UK, 4-7 May2020. In Proceedings, Part 2, p. 246-265 How to Cite? |
Abstract | Although Byzantine Agreement (BA) has been studied for three decades, perhaps somewhat surprisingly, there still exist significant gaps in our understanding regarding its round complexity. A long-standing open question is the following: can we achieve BA with sublinear round complexity under corrupt majority? Due to the beautiful works by Garay et al. (FOCS’07) and Fitzi and Nielsen (DISC’09), we have partial and affirmative answers to this question albeit for the narrow regime f=n/2+o(n) where f is the number of corrupt nodes and n is the total number of nodes. So far, no positive result is known about the setting f>0.51n even for static corruption!
In this paper, we make progress along this somewhat stagnant front. We show that there exists a corrupt-majority BA protocol that terminates in O(1ϵlog1δ) rounds in the worst case, satisfies consistency with probability at least 1−δ , and tolerates (1−ϵ) fraction of corrupt nodes. Our protocol secures against an adversary that can corrupt nodes adaptively during the protocol execution but cannot perform “after-the-fact” removal of honest messages that have already been sent prior to corruption. Our upper bound is optimal up to a logarithmic factor in light of the elegant Ω(1/ϵ) lower bound by Garay et al. (FOCS’07). |
Persistent Identifier | http://hdl.handle.net/10722/301420 |
ISBN | |
Series/Report no. | Lecture Notes in Computer Science (LNCS) ; v. 12111 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, HTH | - |
dc.contributor.author | Pass, R | - |
dc.contributor.author | Shi, E | - |
dc.date.accessioned | 2021-07-27T08:10:48Z | - |
dc.date.available | 2021-07-27T08:10:48Z | - |
dc.date.issued | 2020 | - |
dc.identifier.citation | Public-Key Cryptography – PKC 2020: 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Edinburgh, UK, 4-7 May2020. In Proceedings, Part 2, p. 246-265 | - |
dc.identifier.isbn | 9783030453879 | - |
dc.identifier.uri | http://hdl.handle.net/10722/301420 | - |
dc.description.abstract | Although Byzantine Agreement (BA) has been studied for three decades, perhaps somewhat surprisingly, there still exist significant gaps in our understanding regarding its round complexity. A long-standing open question is the following: can we achieve BA with sublinear round complexity under corrupt majority? Due to the beautiful works by Garay et al. (FOCS’07) and Fitzi and Nielsen (DISC’09), we have partial and affirmative answers to this question albeit for the narrow regime f=n/2+o(n) where f is the number of corrupt nodes and n is the total number of nodes. So far, no positive result is known about the setting f>0.51n even for static corruption! In this paper, we make progress along this somewhat stagnant front. We show that there exists a corrupt-majority BA protocol that terminates in O(1ϵlog1δ) rounds in the worst case, satisfies consistency with probability at least 1−δ , and tolerates (1−ϵ) fraction of corrupt nodes. Our protocol secures against an adversary that can corrupt nodes adaptively during the protocol execution but cannot perform “after-the-fact” removal of honest messages that have already been sent prior to corruption. Our upper bound is optimal up to a logarithmic factor in light of the elegant Ω(1/ϵ) lower bound by Garay et al. (FOCS’07). | - |
dc.language | eng | - |
dc.publisher | Springer. | - |
dc.relation.ispartof | Public-Key Cryptography – PKC 2020: IACR International Conference on Practice and Theory of Public-Key Cryptography | - |
dc.relation.ispartofseries | Lecture Notes in Computer Science (LNCS) ; v. 12111 | - |
dc.subject | Byzantine agreement | - |
dc.subject | Sublinear round complexity | - |
dc.subject | Corrupt majority | - |
dc.title | Sublinear-Round Byzantine Agreement Under Corrupt Majority | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Chan, HTH: hubert@cs.hku.hk | - |
dc.identifier.authority | Chan, HTH=rp01312 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1007/978-3-030-45388-6_9 | - |
dc.identifier.scopus | eid_2-s2.0-85090019948 | - |
dc.identifier.hkuros | 323567 | - |
dc.identifier.volume | Part 2 | - |
dc.identifier.spage | 246 | - |
dc.identifier.epage | 265 | - |
dc.publisher.place | Cham | - |