Efficient reliable communication over partially authenticated networks |
| |
Authors: | Amos Beimel Lior Malka |
| |
Affiliation: | (1) Department of Computer Science, Ben Gurion University, 84105 Beer Sheva, Israel |
| |
Abstract: | Reliable communication between processors in a network is a basic requirement for executing any protocol. Dolev 7] and Dolev
et al. 8] showed that reliable communication is possible if and only if the communication network is sufficiently connected.
Beimel and Franklin 1] showed that the connectivity requirement can be relaxed if some pairs of processors share authentication
keys. That is, costly communication channels can be replaced by authentication keys.
In this work, we continue this line of research. We consider the scenario where there is a specific sender and a specific
receiver in a synchronous network. In this case, the protocol of 1] has nO(n) rounds even if there is a single Byzantine processor. We present a more efficient protocol with round complexity of (n/t)O(t), where n is the number of processors in the network and t is an upper bound on the number of Byzantine processors in the network. Specifically, our protocol is polynomial when the
number of Byzantine processors is O(1), and for every t its round complexity is bounded by 2O(n). The same improvements hold for reliable and private communication. The improved protocol is obtained by analyzing the properties
of a "communication and authentication graph" that characterizes reliable communication.
Received: 13 January 2004, Accepted: 22 September 2004, Published online: 13 January 2005
A preliminary version of this paper appeared in 2]. |
| |
Keywords: | Reliable communication Fault tolerance Authentication Incomplete networks |
本文献已被 SpringerLink 等数据库收录! |
|