We study the problem of secure message transmission among a group of parties in an insecure asynchronous network, where an adversary may repeatedly break into some parties for transient periods of time. A solution for this task is needed in order to use proactive cryptosystems in wide-area networks with loose synchronization. Parties have access to a secure hardware device that stores some cryptographic keys, but can carry out only a very limited set of operations. We provide a formal model of the system, using the framework for asynchronous reactive systems proposed by Pfitzmann and Waidner (Symposium on Security & Privacy, 2001), present a protocol for proactive message transmission, and prove it secure using the composability property of the framework.
We study the problem of secure message transmission among a group of parties in an insecure asynchronous network, where an adversary may repeatedly break into some parties for transient periods of time. A solution for this task is needed in order to use proactive cryptosystems in wide-area networks with loose synchronization. Parties have access to a secure hardware device that stores some cryptographic keys, but can carry out only a very limited set of operations. We provide a formal model of the system, using the framework for asynchronous reactive systems proposed by Pfitzmann and Waidner (Symposium on Security & Privacy, 2001), present a protocol for proactive message transmission, and prove it secure using the composability property of the framework.
This work develops a composable notion of security in a synchronous communication network to analyze cryptographic primitives and protocols in a reliable network with guaranteed delivery. In such a synchronous model the abort of protocols must be handled explicitly. It is shown that a version of global bit commitment which allows to identify parties that did not give proper input cannot be securely realized with the primitives oblivious transfer and broadcast. This proves that the primitives oblivious transfer and broadcast are not complete in our synchronous model of security. In the synchronous model presented ideal functionalities as well as parties can be equipped with a “shell” which can delay communication until the adversary allows delivery or the number of rounds since the shell received the message exceeds a specified threshold. This additionally allows asynchronous specification of ideal functionalities and allows to model a network where messages are not necessarily delivered in the right order. If these latency times are chosen to be infinite the network is no more reliable and becomes completely asynchronous. In the full version [HMQ04] of this paper, it is shown that a large class of protocols which are secure in the asynchronous settings [Can01, CLOS02] can be transformed into secure realizations in the new model by choosing infinite latency times.
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.
We consider the problem of perfect (information-theoretically) secure message transmission (PSMT) from a sender S to a receiver R in asynchronous directed networks tolerating dual adversary. The adversary can control at most tp nodes in a passive fashion and at most tf nodes in a fail-stop fashion. We achieve PSMT in this setting with a new class of message transmission protocols called the quiescent protocols. Quiescent protocols ensure that the players eventually stop sending messages but in contrast to the usual terminating protocols, these protocols do not require the players to go into the halt state, from which they cannot take any further action. To show the significance of quiescent protocols, we first identify conditions in which it is impossible for any terminating protocol to achieve PSMT. To circumvent this impossibility, we transform the existing synchronous PSMT protocol into a quiescent protocol which accomplishes PSMT. By focusing on designing quiescent protocols rather than terminating protocols, we show that asynchrony in the network does not demand any extra connectivity over its state-of-the-art synchronous counterpart. This shows that quiescent protocols are befitted to solve PSMT in asynchronous networks with fail-stop faults.
We describe scalable protocols for solving the secure multi-party computation (MPC) problem among a large number of parties. We consider both the synchronous and the asynchronous communication models. In the synchronous setting, our protocol is secure against a static malicious adversary corrupting less than a 1/3 fraction of the parties. In the asynchronous setting, we allow the adversary to corrupt less than a 1/8 fraction of parties. For any deterministic function that can be computed by an arithmetic circuit with m gates, both of our protocols require each party to send a number of field elements and perform an amount of computation that is O~(m/n+n). We also show that our protocols provide perfect and universally-composable security. To achieve our asynchronous MPC result, we define the \emph{threshold counting problem} and present a distributed protocol to solve it in the asynchronous setting. This protocol is load balanced, with computation, communication and latency complexity of O(logn), and can also be used for designing other load-balanced applications in the asynchronous communication model.
We study the problem of information-theoretically secure message transmission (SMT) in asynchronous directed networks. In line with the literature, the distrust and failures of the network is captured via a computationally unbounded Byzantine adversary that may corrupt some subset of nodes. We give a characterization of networks over which SMT from sender S to receiver R is possible in both the well-known settings, namely perfect SMT (PSMT) and unconditional SMT (USMT). We distinguish between two variants of USMT: one in which R can output an incorrect message (with small probability) and another in which R never outputs a wrong message, but may choose to abort (with small probability). We also provide efficient protocols for an important class of networks.
The problem of secure message transmission (SMT), due to its importance in both \npractice and theory, has been studied extensively. Given a communication network in \nwhich a sender S and a receiver R are indirectly connected by unreliable and distrusted \nchannels, the aim of SMT is to enable messages to be transmitted from S to R with a \nreasonably high level of privacy and reliability. SMT must be achieved in the presence \nof a Byzantine adversary who has unlimited computational power and can corrupt the \ntransmission. In the general adversary model, the adversary is characterized by an \nadversary structure. We study two diff�erent measures of security: perfect (PSMT) and \nalmost perfect (APSMT). Moreover, reliable (but not private) message transmission (RMT) are considered as a specifi�c part of SMT. In this thesis, we study RMT, APSMT \nand PSMT in two di�fferent network settings: point-to-point and multicast. \nTo prepare the study of SMT in these two network settings, we present some ideas \nand observations on secret sharing schemes (SSSs), generalized linear codes and critical \npaths. First, we prove that the error-correcting capability of an almost perfect SSS is \nthe same as a perfect SSS. Next, we regard general access structures as linear codes, \nand introduce some new properties that allow us to construct pseudo-basis for efficient \nPSMT protocol design. In addition, we de�fine adversary structures over "critical paths", \nand observe their properties. Having these new developments, the contributions on SMT \nin the aforementioned two network settings can be presented as follows. \nThe results on SMT in point-to-point networks are obtained in three aspects. First, \nwe show a Guessing Attack on some existing PSMT protocols. This attack is critically \nimportant to the design of PSMT protocols in asymmetric networks. Second, we determine necessary and sufficient conditions for di�fferent levels of RMT and APSMT. \nIn particular, by applying the result on almost perfect SSS, we show that relaxing the \nrequirement of privacy does not weaken the minimal network connectivity. Our �final \ncontribution in the point-to-point model is to give the �first ever efficient, constant round \nPSMT protocols in the general adversary model. These protocols are designed using \nlinear codes and critical paths, and they signifi�cantly improve some previous results in \nterms of communication complexity and round complexity. \nRegarding SMT in multicast networks, we solve a problem that has been open for \nover a decade. That is, we show the necessary and sufficient conditions for all levels of \nSMT in di�fferent adversary models. First, we give an Extended Characterization of the \nnetwork graphs based on our observation on the eavesdropping and separating activities \nof the adversary. Next, we determine the necessary and sufficient conditions for SMT \nin the general adversary model with the new Extended Characterization. Finally, we \napply the results to the threshold adversary model to completely solve the problem of \nSMT in general multicast network graphs.