International Association
for Cryptologic Research

A fundamental primitive in distributed computing is Reliable Message Transmission (RMT), which refers to the task of correctly sending a message from a party to another, despite the presence of byzantine corruptions. In this work we address the problem in the general adversary model of Hirt and Maurer, which subsumes earlier models such as the global or local threshold adversaries. Regarding the topology knowledge, we employ the recently introduced Partial Knowledge Model [13], which encompasses both the full knowledge and the ad hoc model; the latter assumes knowledge of the local neighborhood only.

Our main contributions are: (a) a necessary and sufficient condition for achieving RMT in the partial knowledge model with a general adversary; in order to show sufficiency, we propose a protocol that solves RMT whenever this is possible, therefore the protocol is unique (cf.[14]), and (b) a study of efficiency in the special case of the ad hoc network model; we present a

unique protocol scheme that is fully polynomial for a class of instances, if there exists any fully polynomial protocol for RMT on the decomposition of this class to instances of a certain basic topology.

To obtain our results we employ, among others, an operation on adversary structures, an appropriate notion of separator in unreliable networks, and a self-reducibility property of the RMT problem.