Secure Communication in Minimal Connectivity Models

Matthew Franklin, Rebecca N. Wright

Ivan Damgård, Divya Ravi, Lawrence Roy +2 more

Manan Nayak, Shashank Agrawal, Kannan Srinathan

Abstract. In this paper we give the minimal connectivity required in a synchronous directed network, which is under the influence of a computationally unbounded Byzantine adversary that can corrupt a subset of nodes, so that Secure Message Transmission is possible between sender S and receiver R. We also show that secure communication between a pair of nodes in a given synchronous directed network is possible in both directions if and only if reliable communication is possible between them. We assume that in a network, every node is capable of computation and we model the network along the lines of [14].

Kannan Srinathan, Manoranjan Kumar, U Rangan

Abstract. We study the problem of secure communication tolerating generalized mixed adversaries across an underlying completely asynchronous incomplete network. We explore the interplay between the minimal network connectivity required and the degree of security attainable, and completely characterize the network requirements for attaining perfect and unconditional (with negligible error) security. We also consider networks with additional broadcast capabilities and prove that unconditionally secure communication can be achieved with much lesser connectivity if the network assures the broadcast primitive. 1

Nkm Nieke Aerts

Matt Franklin