Reliable communication over partially authenticated networks

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 pairs sharing keys define a natural ``authentication graph{''}, which may be guile 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. (C) 1999 Elsevier Science B.V. All rights reserved.