Wyner's elegant model of wiretap channel exploits noise in the communication channel to provide perfect secrecy against a computationally unlimited eavesdropper without requiring a shared key. We consider an adversarial model of wiretap channel proposed in [18,19] where the adversary is active: it selects a fraction @math of the transmitted codeword to eavesdrop and a fraction @math of the codeword to corrupt by "adding" adversarial error. It was shown that this model also captures network adversaries in the setting of 1-round Secure Message Transmission [8]. It was proved that secure communication (1-round) is possible if and only if @math . In this paper we show that by allowing communicants to have access to a public discussion channel (authentic communication without secrecy) secure communication becomes possible even if @math . We formalize the model of protocol and for two efficiency measures, information rate and message round complexity derive tight bounds. We also construct a rate optimal protocol family with minimum number of message rounds. We show application of these results to Secure Message Transmission with Public Discussion (SMT-PD), and in particular show a new lower bound on transmission rate of these protocols together with a new construction of an optimal SMT-PD protocol.
SMT-PD was introduced in @cite_19 as a building block in almost-everywhere secure multiparty computation. Bounds on the required number of rounds were derived in @cite_15 . In @cite_8 a bound on transmission rate over wires (not including communication over the ) was derived. The paper presents two constructions: protocol I is optimal in the sense that the transmission rate is of the order of the bound as the number of wire increases , and protocol II in which the goal is to minimize communication over the . This reduction is however at the expense of lower rate on the wires. I Table compares the information rate of these constructions for large @math .
@cite_19 @cite_15 @cite_8
2139127819 2010825791
In a secure message transmission (SMT) scenario, a sender wants to send a message in a private and reliable way to a receiver. Sender and receiver are connected by n wires, t of which can be controlled by an adaptive adversary with unlimited computational resources. In Eurocrypt 2008, Garay and Ostrovsky considered an SMT scenario where sender and receiver have access to a public discussion channel and showed that secure and reliable communication is possible when n ≥ t + 1. In this paper, we will show that a secure protocol requires at least three rounds of communication and two rounds invocation of the public channel and hence give a complete answer to the open question raised by Garay and Ostrovsky. We also describe a round optimal protocol that has constant transmission rate over the public channel. In the problem of secure message transmission in the public discussion model (SMT-PD), a sender wants to send a message MS ∈ 0,1 l to a receiver privately and reliably. Sender and receiver are connected by n channels, also known as simple wires, up to 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 multiparty 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 paper, we present the first SMT-PD protocol with sublinear (i.e., logarithmic in l, the message length) communication on the public channel. In addition, the protocol incurs a simple-wire communication complexity of O(ln n-t), which, as we also show, is optimal. By contrast, the best known bounds in both public and simple 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 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 naive 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 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 the best possible.).