Abstract:
Suppose $A$ and $B$ are parties in a network and want to communicate with each other privately. This problem is trivial if $A$ and $B$ have a private communication link between them. What if there is no such link? This is the problem of secure message transmission (SMT). We consider the characterization of networks in which SMT is possible when the adversary is semi-honest or malicious and when security required is perfect or statistical etc. Some of the protocols are interesting in their own right and some of the techniques used for proving the impossibilities are useful for proving impossibility results generally in secure multi party computing.