DIMACS TR: 97-41

Reliable Communication over Partially Authenticated Networks

Authors: Amos Beimel and Matthew Franklin


Reliable communication between parties in a network is a basic requirement for executing any protocol. In this work, we consider the effect on reliable communication when some pairs of parties have common authentication keys. The %%%distribution of pairs sharing keys define a natural ``authentication graph'', which may be quite different from the ``communication graph'' of the network. We characterize when reliable communication is possible in terms of these two graphs, focusing on the very strong setting of a Byzantine adversary with unlimited computational resources.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-41.ps.gz
DIMACS Home Page