Show simple item record

dc.contributor.author
Blum, Erica
dc.contributor.author
Katz, Jonathan
dc.contributor.author
Liu Zhang, Chen-Da
dc.contributor.author
Loss, Julian
dc.contributor.editor
Pass, Rafael
dc.contributor.editor
Pietrzak, Krzysztof
dc.date.accessioned
2021-01-22T10:39:36Z
dc.date.available
2021-01-14T09:25:27Z
dc.date.available
2021-01-22T10:39:36Z
dc.date.issued
2020
dc.identifier.isbn
978-3-030-64374-4
en_US
dc.identifier.isbn
978-3-030-64375-1
en_US
dc.identifier.issn
0302-9743
dc.identifier.issn
1611-3349
dc.identifier.other
10.1007/978-3-030-64375-1_13
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/462445
dc.description.abstract
Understanding the communication complexity of Byzantine agreement (BA) is a fundamental problem in distributed computing. In particular, for protocols involving a large number of parties (as in, e.g., the context of blockchain protocols), it is important to understand the dependence of the communication on the number of parties n. Although adaptively secure BA protocols with o(n2) communication are known in the synchronous and partially synchronous settings, no such protocols are known in the fully asynchronous case. We show asynchronous BA protocols with (expected) subquadratic communication complexity tolerating an adaptive adversary who can corrupt f< (1 - ϵ) n/ 3 of the parties (for any ϵ> 0). One protocol assumes initial setup done by a trusted dealer, after which an unbounded number of BA executions can be run; alternately, we can achieve subquadratic amortized communication with no prior setup. We also show that some form of setup is needed for (non-amortized) subquadratic BA tolerating Θ(n) corrupted parties. As a contribution of independent interest, we show a secure-computation protocol in the same threat model that has o(n2) communication when computing no-input functionalities with short output (e.g., coin tossing).
en_US
dc.language.iso
en
en_US
dc.publisher
Springer
en_US
dc.title
Asynchronous Byzantine Agreement with Subquadratic Communication
en_US
dc.type
Conference Paper
dc.date.published
2020-12-09
ethz.book.title
Theory of Cryptography
en_US
ethz.journal.title
Lecture Notes in Computer Science
ethz.journal.abbreviated
LNCS
ethz.pages.start
353
en_US
ethz.pages.end
380
en_US
ethz.event
18th International Conference on Theory of Cryptography (TCCC 2020) (virtual)
en_US
ethz.event.location
Durham, NC, USA
en_US
ethz.event.date
November 16-19, 2020
en_US
ethz.notes
Due to the Coronavirus (COVID-19) the conference was conducted virtually.
en_US
ethz.publication.place
Cham
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03338 - Maurer, Ueli / Maurer, Ueli
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03338 - Maurer, Ueli / Maurer, Ueli
en_US
ethz.identifier.orcidWorkCode
85415448
ethz.date.deposited
2021-01-14T09:25:39Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2021-01-22T10:39:45Z
ethz.rosetta.lastUpdated
2021-02-15T23:29:39Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Asynchronous%20Byzantine%20Agreement%20with%20Subquadratic%20Communication&rft.jtitle=Lecture%20Notes%20in%20Computer%20Science&rft.date=2020&rft.spage=353&rft.epage=380&rft.issn=0302-9743&1611-3349&rft.au=Blum,%20Erica&Katz,%20Jonathan&Liu%20Zhang,%20Chen-Da&Loss,%20Julian&rft.isbn=978-3-030-64374-4&978-3-030-64375-1&rft.genre=proceeding&rft_id=info:doi/10.1007/978-3-030-64375-1_13&rft.btitle=Theory%20of%20Cryptography
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record