Secure Message Transmission by Public Discussion: A Brief Survey
Juan Garay, Clint Givens, 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 receiver privately and reliably. Sender and receiver are connected by n channels, up 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.
In this short survey paper, after formally defining the SMT-PD problem, we overview the basic constructions starting with first, rather communication-inefficient solutions to the problem, and ending with the most efficient solutions known to date-optimal private communication and sublinear public communication. We show a near-optimal streaming approximation algorithm for K-means in high -dimensional Euclidean space with sublinear memory and single pass, under the same data separability assumption. Our algorithm offers significant improvements in both space and running time over previous work while yielding asymptotically best-possible performance (assuming that the running time must fully polynomial and P=/ NP)
These complexities refer to resource use for a single execution of an SMT-PD protocol. We also review the "amortized Complexity of the problem, which would arise in natural use-case scenarios where S and R must send several messages back and forth, where later messages depend on earlier ones.
comment: Preliminary version appeared in IWCC 2011:126-141 IEEE Trans. Full version appeared in Information Theory 60(4): 2373-2390 (2014)
Fetch PDF file of the paper
| Back to Publications List |