Secure End-to-End Communication with Optimal Throughput and Resilient Against Malicious Adversary

On the third day of DISC'13, the second session was on "Crypto, Thrust and Influence". The session started with my talk on the paper titled "Asynchronous Multiparty computation with Linear Communication Complexity". The next talk was by Paul Bunn on his work "Secure End-to-End Communication with Optimal Throughput and Resilient Against Malicious Adversary" with Rafi Ostrovsky. This post briefly covers the paper by Paul Bunn and Rafial Ostrovsky.

In the paper, the authors investigate the feasibility of routing or end-to-end communication in a network in which neither the nodes nor the links are reliable. Namely, for the network links, they do not assume any form of stability: the topology of the network is dynamic (links may spontaneously fail or come back to life at any time), transmission time across each link may vary from link to link as well as across the same link from one transmission to the next (i.e. asynchronous edges), and there is no guarantee enough links are available (even over time) for communication to even be possible. Unreliability of network nodes means that they may actively and maliciously deviate from protocol specifications, attempting to disrupt communication as much as possible. In particular, a malicious adversary may corrupt an arbitrary subset of nodes, taking complete control over them and coordinate attacks to interfere with communication between the uncorrupt nodes. Finally, the nodes are corrupted by polynomially bounded adversaries.

It is not hard to see that very few guarantees can be achieved by any protocol that is forced to operate in networks with so few assumptions. So in many situations, it may be possible that there is no robust protocol at all. Therefore, instead of measuring the efficacy of a given protocol in terms of its absolute performance for robustness, the authors employ competitive analysis to evaluate protocols: the throughput-performance of a given protocol with respect to the network conditions encountered is compared to the performance of an ideal protocol (one that has perfect information regarding the schedule of active/inactive links and corrupt nodes, and makes perfect routing decisions based on this information). Indeed, the combination of the strong notion of unreliability (of both edges and nodes) together with the use of competitive analysis provides a meaningful mechanism to evaluate routing protocols in networks that demonstrate unreliability in unknown ways. Competitive analysis is an existing and useful tool for evaluating protocols in unreliable networks and distributed algorithms with shared memory computation.

They present a protocol that routes effectively in the above network setting, utilizing standard cryptographic tools to guarantee correctness (i.e. Receiver gets all of the messages from Sender, in-order and without modification) with low memory burden per node. They show that their protocol achieves optimal throughput while evaluating the throughput-efficiency of their protocol using competitive-analysis. Specifically, they prove the following theorem.

Theorem. Assuming Public-Key Infrastructure and the existence of a group homomorphic encryption scheme, there exists a routing protocol that achieves correctness and optimal competitive-ratio in a distributed asynchronous network with bounded memory Θ(n²) and dynamic topology (and no connectivity assumptions), even if an arbitrary subset of malicious nodes deliberately disobey the protocol specifications in order to disrupt communication as much as possible.

The memory usage of their protocol matches the memory requirements of the protocols that do not provide security against corrupt nodes. Overall, the talk as well as the work appear pretty interesting.