There is a large body of work on using noisy communication channels for realizing different crypto-graphic tasks. In particular, it is known that secure message transmission can be achieved uncondition-ally using only one-way communication from the sender to the receiver. In contrast, known solutions for more general secure computation tasks inherently require interaction, even when the entire input originates from the sender. We initiate a general study of cryptographic protocols over noisy channels in a setting where only one party speaks. In this setting, we show that the landscape of what a channel is useful for is much richer. Concretely, we obtain the following results. • Relationships between channels. The binary erasure channel (BEC) and the binary symmetric channel (BSC), which are known to be securely reducible to each other in the interactive setting, turn out to be qualitatively different in the setting of one-way communication. In particular, a BEC cannot be implemented from a BSC, and while the erasure probability of a BEC can be manipulated in both directions, the crossover probability of a BSC can only be manipulated in one direction. • Zero-knowledge proofs and secure computation of deterministic functions. One-way commu-nication over BEC or BSC is sufficient for securely realizing any deterministic (possibly reactive) functionality which takes its inputs from a sender and delivers its outputs to a receiver. This pro-vides the first truly non-interactive solutions to the problem of zero-knowledge proofs. • Secure computation of randomized functions. One-way communication over BEC or BSC can-not be used for realizing general randomized functionalities which take input from a sender and deliver output to a receiver. On the other hand, one-way communication over other natural chan-nels, such as bursty erasure channels, can be used to realize such functionalities. This type of protocols can be used for distributing certified cryptographic keys without revealing the keys to the certification authority.
There is a large body of work on using noisy communication channels for realizing different crypto-graphic tasks. In particular, it is known that secure message transmission can be achieved uncondition-ally using only one-way communication from the sender to the receiver. In contrast, known solutions for more general secure computation tasks inherently require interaction, even when the entire input originates from the sender. We initiate a general study of cryptographic protocols over noisy channels in a setting where only one party speaks. In this setting, we show that the landscape of what a channel is useful for is much richer. Concretely, we obtain the following results. • Relationships between channels. The binary erasure channel (BEC) and the binary symmetric channel (BSC), which are known to be securely reducible to each other in the interactive setting, turn out to be qualitatively different in the setting of one-way communication. In particular, a BEC cannot be implemented from a BSC, and while the erasure probability of a BEC can be manipulated in both directions, the crossover probability of a BSC can only be manipulated in one direction. • Zero-knowledge proofs and secure computation of deterministic functions. One-way commu-nication over BEC or BSC is sufficient for securely realizing any deterministic (possibly reactive) functionality which takes its inputs from a sender and delivers its outputs to a receiver. This pro-vides the first truly non-interactive solutions to the problem of zero-knowledge proofs. • Secure computation of randomized functions. One-way communication over BEC or BSC can-not be used for realizing general randomized functionalities which take input from a sender and deliver output to a receiver. On the other hand, one-way communication over other natural chan-nels, such as bursty erasure channels, can be used to realize such functionalities. This type of protocols can be used for distributing certified cryptographic keys without revealing the keys to the certification authority.
Historically, cryptography was created and used to deliver messages between people in such a way that only the intended receiver would be able to read them. The two persons communicating trusted each other, but not the rest of the world - for instance, not the message bearer. But what happens if we assume instead that even the receiver of a message may not be trusted by the sender, while both still have an interest in communicating? This problem is addressed by secure multi-party computation, that studies communication and shared computation between mutually distrusting parties. In a world where most of the communication happens over the Internet, and where an ever-increasing amount of computation is outsourced, for example to the cloud, multi-party computation is a subject of crucial importance. However, unconditionally secure multi-party protocols have never found practical application: the lack of realistic noisy channel models, that are required to achieve security against computationally unbounded adversaries, prevents implementation over real-world, standard communication protocols.\n\nIn this thesis, we study the properties and characteristics of noisy channels, and we introduce new models based on real-world error sources that have never been studied in this context, such as delays. On the contrary, previous works mostly focused on theoretical noisy channels that have little in common with the reality of network communication. We show that the models we propose are suitable for multi-party computation by building on each of them a protocol for oblivious transfer, a fundamental cryptographic primitive that implies any secure computation. Thanks to the realism of our noisy channels, we are able to provide the first working implementation of unconditionally secure oblivious transfer over both wired and wireless networks and different Internet protocols, which we test thoroughly in an extensive set of experiments. Our constructions are not only more realistic, but also more flexible, as they allow larger ranges of error probabilities. This will eventually open the way for the widespread use of unconditionally secure multi-party computation.
The question of how to construct optimally efficient secure protocols is a central question in cryptography and in the computer security world at large. We focus in this work on several facets of this question, with a particular view towards the role of randomness in secure computation.
The use of random inputs is ubiquitous in cryptographic primitives. However, the ability to consistently draw from large random sources may be a barrier in practice. We examine the existence of optimally strong pseudorandom sources with particularly efficient implementations; namely, we construct exponentially hard pseudorandom generators that can be computed by circuits that have size linear in the generator output.
Conversely, we also examine efficient protocols that rely only minimally on their random inputs. In the resettable security model, parties may be forced to use the same random input across polynomially many interactions with other parties. We examine this security model in the case of zero knowledge proofs, which are a primitive frequently required in secure computation protocols when one party must prove that they have executed the protocol correctly to another party without revealing secret inputs and compromising security.
Finally, we examine the secure and efficient implementation of a specific functionality, including its various required cryptographic primitives (such as zero knowledge arguments of knowledge). In particular, we construct a protocol that securely realizes pattern matching, including single character wildcards and substring matching.
In the commitment problem, two mutually distrustful parties Alice and Bob interact in a two-phase protocol, viz., commit and reveal phase, to achieve commitment over a bit string that Alice possesses. The protocol successfully achieves commitment if, firstly, Alice can commit to sharing a string with Bob, with the guarantee that this string remains hidden from Bob until she chooses to reveal it to him. Secondly, when Alice does reveal a string, Bob is able to detect precisely whether the revealed string is different from the one Alice committed to sharing. Information-theoretically secure commitment is impossible if Alice and Bob communicate only noiselessly; however, communication using a noisy channel can be a resource to realize commitment. Even though a noisy channel may be available, it is possible that the corresponding channel law is imprecisely known or poorly characterized. We define and study a compound-binary symmetric channel (compound-BSC) which models such a scenario. A compound-BSC is a BSC whose transition probability is fixed but unknown to either party; the set of potential values which this transition probability can take, though, is known to both parties a priori. In this work, we completely characterize the maximum commitment throughput or commitment capacity of a compound-BSC. We provide an optimal, computationally-efficient scheme for our achievability, and we derive a converse for general alphabet compound DMCs, which is then specialized for compound-BSCs.
. The Wire-Tap Channel of Wyner [19] shows that a Binary Symmetric Channel may be used as a basis for exchanging a secret key, in a cryptographic scenario of two honest people facing an eavesdropper. Later Cr'epeau and Kilian [9] showed how a BSC may be used to implement Oblivious Transfer in a cryptographic scenario of two possibly dishonest people facing each other. Unfortunately this result is rather impractical as it requires\\Omega (n 11 ) bits to be transmitted through the BSC to accomplish a single OT. The current paper provides efficient protocols to achieve the cryptographic primitives of Bit Commitment and Oblivious Transfer based on the existence of a Binary Symmetric Channel. Our protocols respectively require sending O(n) and O(n 3 ) bits through the BSC. These results are based on a technique known as Generalized Privacy Amplification [1] that allow two people to extract secret information from partially compromised data. 1 Introduction The cryptographic power of a no...
A number of works have investigated using tamper-proof hardware tokens as tools to achieve a variety of cryptographic tasks. In particular, Goldreich and Ostrovsky considered the goal of software protection via oblivious RAM. Goldwasser, Kalai, and Rothblum introduced the concept of one-time programs: in a one-time program, an honest sender sends a set of simple hardware tokens to a (potentially malicious) receiver. The hardware tokens allow the receiver to execute a secret program specified by the sender’s tokens exactly once (or, more generally, up to a fixed t times). A recent line of work initiated by Katz examined the problem of achieving UC-secure computation using hardware tokens. Motivated by the goal of unifying and strengthening these previous notions, we consider the general question of basing secure computation on hardware tokens. We show that the following tasks, which cannot be realized in the “plain ” model, become feasible if the parties are allowed to generate and exchange tamper-proof hardware tokens. • Unconditional non-interactive secure computation. We show that by exchanging simple stateful hardware tokens, any functionality can be realized with unconditional security against malicious parties. In the case of two-party functionalities f(x, y) which take their inputs from a sender and a receiver and deliver
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.