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 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 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 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).
In the model of perfectly secure message transmission (PSMT) schemes, there are n channels between a sender and a receiver. An infinitely powerful adversary A may corrupt (observe and forge) the messages sent through t out of n channels. The sender wishes to send a secret s to the receiver perfectly privately and perfectly reliably without sharing any key with the receiver. In this paper, we show the first 2-round PSMT for n = 2t + 1 such that not only the transmission rate is O(n) but also the computational costs of the sender and the receiver are both polynomial in n. This means that we solve the open problem raised by Agarwal, Cramer, and de Haan at CRYPTO 2006. The main novelty of our approach is to introduce a notion of pseudobasis to the coding theory. It will be an independent interest for coding theory, too.
Abstract. In the model of perfectly secure message transmission schemes (PSMTs), there are n channels between a sender and a receiver. An infinitely powerful adversary A may corrupt (observe and forge) the messages sent through t out of n channels. The sender wishes to send a secret s to the receiver perfectly privately and perfectly reliably without sharing any key with the receiver. In this paper, we show the first 2-round PSMT for n = 2t + 1 such that not only the transmission rate is O(n) but also the computational costs of the sender and the receiver are both polynomial in n. This means that we solve the open problem raised by Agarwal, Cramer and de Haan at CRYPTO 2006. The main novelty of our approach is to introduce a notion of pseudobasis to the coding theory. It will be an independent interest for coding theory, too.
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.
In the model of Perfectly Secure Message Transmission Schemes (PSMTs), there are n channels between a sender and a receiver, and they share no key. An infinitely powerful adversary A can corrupt (observe and forge) the messages sent through some subset of n channels. For non-threshold adversaries called Q 2, Kumar et al. showed a many round PSMT (Ashwin Kumar et al. On perfectly secure communication over arbitrary networks. PODC 2002, pp. 193---202, 2002). In this paper, we show round efficient PSMTs against Q 2-adevrsaries. We first give a 3-round PSMT which runs in polynomial time in the size of the underlying linear secret sharing scheme. We next present a 2-round PSMT which is inefficient in general. (However, it is efficient for some special case.)