Secure message transmission assumes n channels between a sender and a receiver such that up to t channels are under the control of a computationally unlimited adversary. In secure message transmission by public discussion protocol, sender and receiver have access to a public authenticated channel. In this paper we show that if n ¿ t + 1, a secure protocol requires at least 3 rounds of communication and 2 rounds invocation of the public channel. This gives a complete answer to a question raised by Garay and Ostrovsky in Eurocrypt 2008. We also describe a round optimal protocol that has constant transmission rate over the public channel.
Secure message transmission assumes n channels between a sender and a receiver such that up to t channels are under the control of a computationally unlimited adversary. In secure message transmission by public discussion protocol, sender and receiver have access to a public authenticated channel. In this paper we show that if n ¿ t + 1, a secure protocol requires at least 3 rounds of communication and 2 rounds invocation of the public channel. This gives a complete answer to a question raised by Garay and Ostrovsky in Eurocrypt 2008. We also describe a round optimal protocol that has constant transmission rate over the public channel.
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 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 vertex disjoint paths, referred to as 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 3 rounds of communication and 2 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 \emph{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 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 implementation of such public channel in point-topoint 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 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 ( mn n−t), which, as we also show, is 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 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ï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 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.) Key words: Secure message transmission, information-theoretic security, almost-everywhere secure computation, randomness extractors.
In the model that has become known as "Perfectly Secure Message Transmission"(PSMT), a sender Alice is connected to a receiver Bob through n parallel two-way channels. A computationally unbounded adversary Eve controls t of these channels, meaning she can acquire and alter any data that is transmitted over these channels. The sender Alice wishes to communicate a secret message to Bob privately and reliably, i.e. in such a way that Eve will not get any information about the message while Bob will be able to recover it completely. In this paper, we focus on protocols that work in two transmission rounds for n= 2t+1. We break from previous work by following a conceptually simpler blueprint for achieving a PSMT protocol. We reduce the previously best-known communication complexity, i.e. the number of transmitted bits necessary to communicate a 1-bit secret, from O(n^3 log n) to O(n^2 log n). Our protocol also answers a question raised by Kurosawa and Suzuki and hitherto left open: their protocol reaches optimal transmission rate for a secret of size O(n^2 log n) bits, and the authors raised the problem of lowering this threshold. The present solution does this for a secret of O(n log n) bits. Additionally, we show how our protocol can be adapted to a Network Coding context.
In the model that has become known as “Perfectly Secure Message Transmission” (PSMT), a sender Alice is connected to a receiver Bob through n parallel two-way channels. A computationally unbounded adversary Eve controls t of these channels, meaning she can acquire and alter any data that is transmitted over these channels. The sender Alice wishes to communicate a secret message to Bob privately and reliably, i.e. in such a way that Eve gains no information about the message while Bob is able to recover it completely. We focus on PSMT protocols that work in two transmission rounds for n = 2t + 1. We break from previous work by following a conceptually simpler blueprint. This has two consequences: first, we obtain improved efficiency, namely, we reduce the previously best-known communication complexity, i.e. the number of transmitted bits necessary to communicate a 1-bit secret, from O(n3log n) to O(n2log n). Our solution also reaches optimal transmission rate for a secret of size O(n log n), thus answering the hitherto open question of attaining a threshold below O(n2log n) bits. Second, our construction can be adapted to more general scenarios relevant to Network Coding, where the adversary is given more power.
In the model of Perfectly Secure Message Transmission (PSMT), a sender Alice is connected to a receiver Bob via n parallel two-way channels, and Alice holds an 𝓁 symbol secret that she wishes to communicate to Bob. There is an unbounded adversary Eve that controls t of the channels, where n = 2t+1. Eve is able to corrupt any symbol sent through the channels she controls, and furthermore may attempt to infer Alice’s secret by observing the symbols sent through the channels she controls. The transmission is required to be (a) reliable, i.e., Bob must always be able to recover Alice’s secret, regardless of Eve’s corruptions; and (b) private, i.e., Eve may not learn anything about Alice’s secret. We focus on the two-round model, where Bob is permitted to first transmit to Alice, and then Alice responds to Bob. In this work we provide upper and lower bounds for the PSMT model when the length of the communicated secret 𝓁 is asymptotically large. Specifically, we first construct a protocol that allows Alice to communicate an 𝓁 symbol secret to Bob by transmitting at most 2(1+o_{𝓁→∞}(1))n𝓁 symbols. Under a reasonable assumption (which is satisfied by all known efficient two-round PSMT protocols), we complement this with a lower bound showing that 2n𝓁 symbols are necessary for Alice to privately and reliably communicate her secret. This provides strong evidence that our construction is optimal (even up to the leading constant).