Secure Message Transmission (SMT) is a two-party cryptographic protocol by which the sender can securely and reliably transmit messages to the receiver using multiple channels. An adversary can corrupt a subset of the channels and commit eavesdropping and tampering attacks over the channels. In this work, we introduce a game-theoretic security model for SMT in which adversaries have some preferences for protocol execution. We define rational “timid” adversaries who prefer to violate security requirements but do not prefer the tampering to be detected. First, we consider the basic setting where a single adversary attacks the protocol. We construct perfect SMT protocols against any rational adversary corrupting all but one of the channels. Since minority corruption is required in the traditional setting, our results demonstrate a way of circumventing the cryptographic impossibility results by a game-theoretic approach. Next, we study the setting in which all the channels can be corrupted by multiple adversaries who do not cooperate. Since we cannot hope for any security if a single adversary corrupts all the channels or multiple adversaries cooperate maliciously, the scenario can arise from a game-theoretic model. We also study the scenario in which both malicious and rational adversaries exist.
Secure Message Transmission (SMT) is a two-party cryptographic protocol by which the sender can securely and reliably transmit messages to the receiver using multiple channels. An adversary can corrupt a subset of the channels and commit eavesdropping and tampering attacks over the channels. In this work, we introduce a game-theoretic security model for SMT in which adversaries have some preferences for protocol execution. We define rational “timid” adversaries who prefer to violate security requirements but do not prefer the tampering to be detected. First, we consider the basic setting where a single adversary attacks the protocol. We construct perfect SMT protocols against any rational adversary corrupting all but one of the channels. Since minority corruption is required in the traditional setting, our results demonstrate a way of circumventing the cryptographic impossibility results by a game-theoretic approach. Next, we study the setting in which all the channels can be corrupted by multiple adversaries who do not cooperate. Since we cannot hope for any security if a single adversary corrupts all the channels or multiple adversaries cooperate maliciously, the scenario can arise from a game-theoretic model. We also study the scenario in which both malicious and rational adversaries exist.
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.
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) 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.
Existing work on "rational cryptographic protocols" treats each party (or coalition of parties) running the protocol as a selfish agent trying to maximize its utility. In this work we propose a fundamentally different approach that is better suited to modeling a protocol under attack from an external entity. Specifically, we consider a two-party game between an protocol designer and an external attacker. The goal of the attacker is to break security properties such as correctness or privacy, possibly by corrupting protocol participants; the goal of the protocol designer is to prevent the attacker from succeeding. We lay the theoretical groundwork for a study of cryptographic protocol design in this setting by providing a methodology for defining the problem within the traditional simulation paradigm. Our framework provides ways of reasoning about important cryptographic concepts (e.g., adaptive corruptions or attacks on communication resources) not handled by previous game-theoretic treatments of cryptography. We also prove composition theorems that-for the first time-provide a sound way to design rational protocols assuming "ideal communication resources" (such as broadcast or authenticated channels) and then instantiate these resources using standard cryptographic tools. Finally, we investigate the problem of secure function evaluation in our framework, where the attacker has to pay for each party it corrupts. Our results demonstrate how knowledge of the attacker's incentives can be used to circumvent known impossibility results in this setting.
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 the problem of secure message transmission in the public discussion model (SMT-PD), a sender wants to send a messageMS∈{0,1}ℓto a receiver privately and reliably. Sender and receiver are connected bynchannels, also known as simple wires, up tot<nof 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 multiparty 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. In this paper, we present the first SMT-PD protocol with sublinear (i.e., logarithmic inℓ, the message length) communication on the public channel. In addition, the protocol incurs a simple-wire communication complexity ofO(ℓn/n−t), which, as we also show, is optimal. By contrast, the best known bounds in both public and simple 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 the best possible.)