Cryptology ePrint Archive: Report 2015/243

Reliable Message Transmission under Partial Knowledge

Aris Pagourtzis and Giorgos Panagiotakos and Dimitris Sakavalas

Abstract: A fundamental primitive in distributed computing is \emph{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 \emph{Partial Knowledge Model}~\cite{PPS14}, which encompasses both the full knowledge and the \textsl{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 RMT-PKA, a protocol that solves RMT whenever this is possible, therefore it is a \emph{unique} protocol (cf.~\cite{PP05}). To the best of our knowledge, this is the first unique protocol for RMT in against general adversaries in the partial knowledge model. (b) A study of efficiency in the case of the \textsl{ad hoc} network model: we show that either the $\calz$-CPA protocol~\cite{PPS14} is fully polynomial or no unique fully polynomial protocol for RMT exists, thus introducing a new notion of uniqueness with respect to efficiency that we call \emph{poly-time uniqueness}.

To obtain our results we introduce, among others, a \emph{joint view} operation on adversary structures, a new notion of separator (RMT-cut), appropriate for RMT in unreliable networks, and a self-reducibility property of the RMT problem, which we show by means of a protocol composition. The latter plays a crucial role in proving the poly-time uniqueness of $\calz$-CPA.

Category / Keywords: foundations / reliable message transmission, byzantine adversary, partial knowledge, general adversary, reliable broadcast, incomplete networks, ad hoc networks, distributed computing, topology knowledge

Date: received 14 Mar 2015, last revised 23 Jun 2015

Contact author: sakaval at corelab ntua gr

Available format(s): PDF | BibTeX Citation

Version: 20150623:092723 (All versions of this report)

Short URL: ia.cr/2015/243

Discussion forum: Show discussion | Start new discussion