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.
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.
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 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.
Abstract. In Secure Message Transmission (SMT) problem, a sender S is connected to a receiver R through N node disjoint bidirectional paths in the network, t of which are controlled by an adversary with unlimited computational power. S wants to send a message m to R in a reliable and private way. It is proved that SMT is possible if and only if N ≥ 2t+1. In Reliable Message Transmission (RMT) problem, the network setting is the same and the goal is to provide reliability for communication, only. In this paper we focus on 1-round δ-RMT and (0, δ)-SMT where the chance of protocol failure (receiver cannot decode the sent message) is at most δ, and in the case of SMT, privacy is perfect. We propose a new approach to the construction of 1-round δ-RMT and (0, δ)-SMT for all connectivities N ≥ 2t + 1, using list decodable codes and message authentication codes. Our concrete constructions use folded Reed-Solomon codes and multireceiver message authentication codes. The protocols have optimal transmission rates and provide the highest reliability among all known comparable protocols. Important advantages of these constructions are, (i) they can be adapted to all connectivities, and (ii) have simple and direct security (privacy and reliability) proofs using properties of the underlying codes, and δ can be calculated from parameters of the underlying codes. We discuss our results in relation to previous work in this area and propose directions for future research. 1
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 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 this thesis we focus on various aspects of secure message transmission protocols. Such protocols achieve the secure transmission of a message from a sender to a receiver - where the term “secure” encapsulates the notion of privacy and reliability of message transmission. These two parties are connected using an underlying network in which a static computationally unlimited active adversary able to corrupt up to t network nodes is assumed to be present. Such protocols are important to study as they are used extensively in various cryptographic protocols and are of interest to other research areas such as ad-hoc networks, military networks amongst others. Optimal bounds for the number of phases (communication from sender to receiver or vice versa), connectivity requirements (number of node disjoint network paths connecting sender and receiver - denoted by n), communication complexity (complexity of the number of field elements sent - where F is the finite field used and jFj = q) and transmission complexity (proportion of communication complexity to complexity of secrets transmitted) for secure message transmission protocols have been proven in previous work. In the one-phase model it has been shown that n 3t+1 node disjoint paths are required to achieve perfect communication. In the two phase model only n 2t + 1 node disjoint paths are necessary. This connectivity is also the required bound for almost perfectly secure one-phase protocols - protocols which achieve perfect privacy but with a negligible probability may fail to achieve reliability. In such cases the receiver accepts a different message to that transmitted by the sender or does not accept any message. The main focus of recent research in secure message transmission protocols has been to present new protocols which achieve optimal transmission complexity. This has been achieved through the transmission of multiple messages. If a protocol has a communication complexity of O(n3) field elements, to achieve optimal transmission complexity O(n2) secrets will have to be communicated. This has somewhat ignored the simplification and improvement of protocols which securely transmit a single secret. Such improvements include constructing more efficient protocols with regards to communication complexity, computational complexity and the number of field elements sent throughout the whole protocol. In the thesis we first consider one-phase almost perfectly secure message transmission and present two new protocols which improve on previous work. We present a polynomial time protocol of O(n2) communication complexity which at the time of writing this thesis, is computationally more efficient than any other protocol of similar communication complexity for the almost perfectly secure transmission of a single message. Even though our first almost perfectly secure transmission protocol is of polynomial time, it is important to study other protocols also and improve previous work presented by other researchers. This is the idea behind the second one-phase almost perfectly secure message transmission protocol we present which requires an exponential complexity of field operations but lower (O(n)) communication complexity. This protocol also improves on previous protocols of similar communication complexity, requiring in the order of O(log q) less computation to complete - where q denotes the size of the finite field used. Even though this protocol is of exponential time, for small values of n (e.g. when t = 1, t = 2 or t = 3) it may be beneficial to use this protocol for almost perfectly secure communication as opposed to using the polynomial time protocol. This is because less field elements need to be transmitted over the whole network which connects a sender and a receiver. Furthermore, an optimal almost perfectly secure transmission protocol will be one with O(n) communication complexity and with polynomial computational complexity. We hope that in the future, other researchers will be inspired by our proposed protocol, improve on our work and ideally achieve these optimal results. We also consider multi-phase protocols. By combining various cryptographic schemes, we present a new two-phase perfectly secure single message transmission protocol. At the time of writing this thesis, the protocol is the most efficient protocol when considering communication complexity. Our protocol has a communication complexity of O(n2) compared to O(n3) of previous work thus improving on the communication complexity by an order of O(n) for the perfectly secure message transmission of a single message. This protocol is then extended to a three phase protocol where a multi-recipient broadcast end channel network setting is considered. As opposed to point to point networks where a path from a sender reaches a single receiver, this network model is new in the field of message transmission protocols. In this model each path from a sender reaches multiple receivers, with all receivers receiving the same information from their common network communication channel. We show how the use of this protocol upon such a network can lead to great savings in the transmission and computation carried out by a single sender. We also discuss the importance and relevance of such a multi-recipient setting to practical applications. The first protocols in the field of perfectly secure message transmission with a human receiver are also presented. This is a topic proposed by my supervisor Professor Yvo Desmedt for which I constructed solutions. In such protocols, one of the communicating parties is considered to be a human who does not have access to a computational device. Because of this, solutions for such protocols need to be computationally efficient and computationally simple so that they can be executed by the human party. Experiments with human participants were carried out to assess how easily and accurately human parties used the proposed protocols. The experimental results are presented and these identify how well human participants used the protocols. In addition to the security of messages, we also consider how one can achieve anonymity of message transmission protocols. For such protocols, considering a single-receiver multi-sender scenario, the presence of a t-threshold bounded adversary and the transmission of multiple secrets (as many as the number of sender), once the protocols ends one should not be able to identify the sender of a received message. Considering a passive and active adversary new protocols are presented which achieve the secure and anonymous transmission of messages in the information-theoretic security model. Our proposed solutions can also be applied (with minor alterations) to the dual problem when a single-sender multi-recipient communication setting is considered. The contributions of the thesis are primarily theoretical - thus no implementation of the proposed protocols was carried out. Despite this, we reflect on practical aspects of secure message transmission protocols. We review the feasibility of implementing secure message transmission protocols in general upon various networks - focusing on the Internet which can be considered as the most important communication network at this time. We also describe in theory how concepts of secure message transmission protocols could possibly be used in practical implementations for secure communication on various existing communication networks. Open problems that remain unsolved in the research area of the proposed protocols are also discussed and we hope that these inspire research and future solutions for the design (and implementation) of better and more efficient secure message transmission protocols.