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 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.
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 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 Secure Message Transmission (SMT) problem two nodes in a network want to communicate securely (both privately and reliably), given that some of the nodes in the network are corrupted by an adaptive byzantine adversary with unlimited computational power. A SMT protocol uses multiple paths between the sender S and a receiver R to guarantee privacy and reliability of the message transmission. Privacy means that the adversary learns no information about the transmitted secret, whereas reliability means that the receiver always receives the message sent by the sender. S and R are connected by n disjoint paths where a subset of which (at most t in case of a threshold adversary) can be corrupted by an adversary. Efficiency parameters of a SMT protocol are the number of rounds (number of interactions between S and R ), communication complexity, and computational complexity. An (e, δ)-SMT protocol bounds the adversary's success probability of breaking privacy and reliability to e and δ, respectively. A SMT protocol for a given number of rounds is optimal if its transmission rate (amount of communication per one bit of message) matches the lower bound for that number of rounds. Optimal protocols have been constructed for a restricted set of parameters. It has been proved that secure SMT is possible if and only if n ≥ 2t + 1, where t is the number of paths corrupted by the adversary.
This thesis describes a number of contributions to the study of SMT problem. First, we improve the system parameter of a previously introduced wire virtualization method for constructing optimal protocols using two component protocols. Using the improved wire virtualization method we present the first optimal 1-round (0, δ)-SMT protocol for higher connectivity.
Then we introduce a modular approach for constructing SMT protocols using two or more modules. Using this approach we design an optimal 1-round (0, δ)-SMT protocol for the minimum connectivity, which has higher reliability than any comparable protocol. We also design a similar protocol for higher connectivity improving the reliability of the protocol presented in the first part of this thesis.
Constructing secure and efficient (in communication) SMT protocols against a threshold adversary has been extensively researched. However less is known about SMT problem for a generalized adversary who can corrupt one out of a set of possible subsets. In this part of the thesis, we focus on 1-round (0, δ)-SMT protocols against a generalized adversary. These protocols are especially attractive because of their possible practical applications.
Finally, we introduce a new security definition by presenting an alternative privacy definition, which is based on guessing advantage of the adversary, to construct more efficient (in communication) protocols. Our motivation is that if the received message is long enough and has sufficient entropy, then it can be used as a secret key. We give the relationship between the new security definition and the known one, and revisit bounds on connectivity and transmission rates of SMT protocols under the new definition. We also give constructions for a 1-round and a 3-round protocol, secure under the new definition, that are optimal.
The contributions made in this thesis add to the research on the secure message transmission problem and show new directions for future research.
In Secure Message Transmission (SMT) protocol a sender S can send a message m to a receiver R in a ‘private’ and ‘reliable’ way. S and R are connected by n channels where at most t of them can be fully controlled by an adaptive adversary with unlimited computational power. In this paper, noting the similarity between the privacy goal of SMT and an encryption function, we introduce a new definition for privacy of SMT systems which is inspired by the definition of semantic security in encryption. We show the relationship between this new definition and the previously known one, and propose an efficient 1-round protocol that is secure under the new definition and insecure under the previous one. The protocol has a better transmission rate compared to all known 1-round protocols in the previous model. We discuss our results and show how it relates to known results in this area.
In Secure message transmission (SMT) protocols two nodes in a network want to communicate securely, given that some of the nodes in the network are corrupted by an adversary with unlimited computational power. An SMT protocol uses multiple paths between the sender and a receiver to guarantee privacy and reliability of the message transmission. An (e, δ)-SMT protocol bounds the adversary's success probability of breaking privacy and reliability to e and δ, respectively. Rate optimal SMT protocols have the smallest transmission rate (amount of communication per one bit of message). Rate optimal protocols have been constructed for a restricted set of parameters.In this paper we use wire virtualization method to construct new optimal protocols for a wide range of parameters using previously known optimal protocols. In particular, we design, for the first time, an optimal 1-round (0, δ)-SMT protocol for n = (2 + c)t, c ≥ 1/t, where n is the number of paths between the sender and the receiver, up to t of which are controlled by the adversary. We also design an optimal 2-round (0, 0)-SMT protocol for n = (2 + c)t, c ≥ 1/t, with communication cost better than the known protocols. The wire virtualization method can be used to construct other protocols with provable properties from component protocols.