International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Efficient and Player-Optimal Strong Consensus

Authors:
Matthias Fitzi
Juan A. Garay
Download:
URL: http://eprint.iacr.org/2002/085
Search ePrint
Search Google
Abstract: In the {\em strong consensus} problem, $n$ players attempt to reach agreement on a value initially held by {\em one of the good players}, despite the (malicious) behavior of up to $t$ of them. Although the problem is closely related to the standard consensus problem (aka Byzantine agreement), the only known solution with the optimal number of players requires exponential computation and communication in the unconditional setting. In this paper we study this problem, and present {\em efficient} protocols and tight lower bounds for several standard distributed computation models --- unconditional, computational, synchronous, and asynchronous.
BibTeX
@misc{eprint-2002-11608,
  title={Efficient and Player-Optimal Strong Consensus},
  booktitle={IACR Eprint archive},
  keywords={},
  url={http://eprint.iacr.org/2002/085},
  note={ garay@research.bell-labs.com 11865 received 27 Jun 2002},
  author={Matthias Fitzi and Juan A. Garay},
  year=2002
}