Bounds and Constructions for 1-Round (0,δ)-Secure Message Transmission against Generalized Adversary

In the Secure Message Transmission (SMT) problem, a sender $\cal S$ is connected to a receiver $\cal R$ through n node-disjoint paths in the network, a subset of which are controlled by an adversary with unlimited computational power. $\cal{S}$ wants to send a message m to $\cal{R}$ in a private and reliable way. Constructing secure and efficient SMT protocols against a threshold adversary who can corrupt at most t out of n wires, has been extensively researched. However less is known about SMT problem for a generalized adversary who can corrupt one out of a set of possible subsets. In this paper we focus on 1-round (0,δ)-SMT protocols where privacy is perfect and the chance of protocol failure (receiver outputting NULL ) is bounded by δ. These protocols are especially attractive because of their possible practical applications. We first show an equivalence between secret sharing with cheating and canonical 1-round (0, δ)-SMT against a generalized adversary. This generalizes a similar result known for threshold adversaries. We use this equivalence to obtain a lower bound on the communication complexity of canonical 1-round (0, δ)-SMT against a generalized adversary. We also derive a lower bound on the communication complexity of a general 1-round (0, 0)-SMT against a generalized adversary. We finally give a construction using a linear secret sharing scheme and a special type of hash function. The protocol has almost optimal communication complexity and achieves this efficiency for a single message (does not require block of message to be sent).