Cryptology ePrint Archive: Report 2009/519

Secure Message Transmission with Small Public Discussion

Juan Garay and Clint Givens and Rafail Ostrovsky

Abstract: In the problem of Secure Message Transmission in the public discussion model (SMT-PD), a Sender wants to send a message to a Receiver privately and reliably. Sender and Receiver are connected by $n$ channels, up to $t<n$ of which may be maliciously controlled by a computationally unbounded adversary, as well as one public channel, which is reliable but not private.

The SMT-PD abstraction has been shown instrumental in achieving secure multi-party computation on sparse networks, where a subset of the nodes are able to realize a broadcast functionality, which plays the role of the public channel. However, the {\em implementation} of such public channel in point-to-point networks is highly costly and non-trivial, which makes minimizing the use of this resource an intrinsically compelling issue.

In this paper, we present the first SMT-PD protocol with {\em sublinear} (i.e., logarithmic in $m$, the message size) communication on the public channel. In addition, the protocol incurs a private communication complexity of $O(\frac{mn}{n-t})$, which, as we also show, is {\em optimal}. By contrast, the best known bounds in both public and private channels were linear. Furthermore, our protocol has an optimal round complexity of $(3,2)$, meaning three rounds, two of which must invoke the public channel.

Finally, we ask the question whether some of the lower bounds on resource use for a single execution of SMT-PD can be beaten \emph{on average} through amortization. In other words, if Sender and Receiver must send several messages back and forth (where later messages depend on earlier ones), can they do better than the na\"{i}ve solution of repeating an SMT-PD protocol each time? We show that amortization can indeed drastically reduce the use of the public channel: it is possible to limit the total number of uses of the public channel to {\em two}, no matter how many messages are ultimately sent between two nodes. (Since two uses of the public channel are required to send any reliable communication whatsoever, this is best possible.)

Category / Keywords: Secure message transmission, information-theoretic security, almost-everywhere secure computation, randomness extractors

Date: received 26 Oct 2009, last revised 2 Nov 2009

Contact author: cgivens at math ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20091103:030019 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]