עמוס ביימל

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 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.