) Claude Cr'epeau Department of Computer Science MIT Joe Kilian y Mathematics Department MIT Abstract A useful paradigm in studying cryptographic scenarios is that of protocol minimalism. That is, given a cryptographic model, one wishes to determine the simplest protocols one needs in order to be able to implement secure protocols in general. In the standard cryptographic model, this approach allows one to encapsulate ones cryptographic assumptions. In other, nonstandard scenarios, the approach can greatly simplifying the task of developing protocols without cryptographic assumptions. Oblivious transfer protocols, first introduced by Rabin [R], are conceptually very simple, yet can be used to implement a wide variety of protocols([EGL],[BCR1],[K]). The versatility of these games amply motivates a wider study of the power of simple two-party games. In this paper, we present some general techniques for establishing the cryptographic strength of a wide variety of games. As case studie...
) Claude Cr'epeau Department of Computer Science MIT Joe Kilian y Mathematics Department MIT Abstract A useful paradigm in studying cryptographic scenarios is that of protocol minimalism. That is, given a cryptographic model, one wishes to determine the simplest protocols one needs in order to be able to implement secure protocols in general. In the standard cryptographic model, this approach allows one to encapsulate ones cryptographic assumptions. In other, nonstandard scenarios, the approach can greatly simplifying the task of developing protocols without cryptographic assumptions. Oblivious transfer protocols, first introduced by Rabin [R], are conceptually very simple, yet can be used to implement a wide variety of protocols([EGL],[BCR1],[K]). The versatility of these games amply motivates a wider study of the power of simple two-party games. In this paper, we present some general techniques for establishing the cryptographic strength of a wide variety of games. As case studie...
Oblivious transfer, first introduced by Rabin, is one of the basic building blocks of cryp-tographic protocols. In an oblivious transfer (or more exactly, in its 1-out-of-2 variant), one party known as the sender has a pair of messages and the other party known as the receiver obtains one of them. Somewhat paradoxically, the receiver obtains exactly one of the messages (and learns nothing of the other), and the sender does not know which of the messages the receiver obtained. Due to its importance as a building block for secure protocols, the efficiency of oblivious transfer protocols has been extensively studied. However, to date, there are almost no known oblivious transfer protocols that are secure in the presence of malicious adversaries under the real/ideal model simulation paradigm (without using general zero-knowledge proofs). Thus, efficient protocols that reach this level of security are of great interest. In this paper we present efficient oblivious transfer protocols that are secure according to the ideal/real model simulation paradigm. We achieve constructions under the DDH, Nth residuosity and quadratic residuosity assumptions, as well as under the assumption that homomorphic encryption exists. 1
Reducing the minimum assumptions needed to construct various cryptographic primitives is an important andinteresting task in theoretical cryptography. Oblivious Transfer, one of the most basic cryptographic building blocks, is also studied under this scenario. Reducing the minimum assumptions for Oblivious Transfer seems not an easy task, as there are a few impossibility results under black-box reductions. Until recently, it is widely believed that Oblivious Transfer can be constructed with trapdoor permutations but not trapdoor functions in general. In this paper, we enhance previous results and show one Oblivious Transfer protocol based on a collection of trapdoor functions with some extra properties. We also provide reasons for adding the extra properties and argue that the assumptions in the protocol are nearly minimum.
In cryptographic protocols, honest parties would prefer that their security is assured even in presence of adversarial parties who have unbounded computational power. Information theoretic secure realization of cryptographic primitives provides such guarantees; but for most tasks such strong security guarantees cannot be provided for any reasonable notion of security. The standard technique used in cryptography is to assume the existence of some puzzle, whose hard instances are easy to generate but no efficient algorithm can solve them. Such assumptions, which define intractable problems for efficient algorithms, are called computational intractability assumptions.
In this work, we motivate a study of computational intractability assumptions which is goal driven and lends support to the fundamental nature of some of the traditional assumptions beyond being historical accidents. Secure multi-party computation deals with the study of constructing secure protocols for general cryptographic tasks which conform to various notions of security. Inspired by complexity theory, we use the notion of reduction to further our understanding of computational intractability assumptions. Our framework explores the hardness of natural assumptions of the form: “Task F can be securely computed given an ideally secure facility for computing G ”.
Formally, we characterize the minimal computational intractability assumption which is sufficient to securely realize a functionality using trusted copies of some other functionality. A functionality F reduces to G , similar to the complexity-theoretic notion of reduction, if F can be securely realized when parties can access trusted copies of G . Thus, if F does not reduce to G information-theoretically, we are interested in characterizing the minimal assumption, which is sufficient, to securely realize the reduction of F to G .
In our framework, we explore the relative strengths of these minimal computational assumptions. The fundamental problem, then, is to establish relations, like implication, equivalence and separation, among the assumptions which correspond to various reductions. In this work, we further our understanding of the minimal computational assumptions corresponding to such reductions by showing the following results:
1. We identify a spectrum for the set of assumptions that correspond to reduction between a pair of tasks under different security notions. These reductions are implied by the computational intractability assumption: “semi-honest secure protocol for oblivious transfer exists” (sh-OT assumption). Additionally, the information theoretically impossible reductions considered in this thesis imply the assumption: “one-way functions exist” (OWF assumption). We conjecture that OWF assumption is necessary for these reductions. In fact, the reductions considered in this thesis are either information theoretically true, false, equivalent to OWF assumption or equivalent to sh-OT assumption [MPR10a].
We expand our study to encompass reductions involving randomized functionalities and study the consequences of providing parties with a trusted source of common unbiased coins. For a strong notion of security they turn out to be useless and unless sh-OT assumption holds these randomness sources are not useful [MOPR11, MP11].
2. We [MPS10] seek to lend additional support to the widely believed premise that “non-trivial cryptography entails the existence of one-way functions”. We show that (constant round) weak coin-tossing protocols, imply OWF assumption. For the general problem, i.e. secure weak coin-tossing protocols with polynomial round complexity, we show a slightly weaker implication NP n BPP.
3. Finally, we indicate the possibility of a wide range of intractability assumptions in our spectrum, intermediate to OWF assumption and sh-OT assumption. We show that a class of natural assumptions corresponding to reductions that are relativistically separated from OWF assumption. Similar techniques have been used to show their separation from the assumption that “public-key encryption exists” (PKE assumption) [MMP11]; but these assumptions are not known to imply sh-OT assumption. We conjecture that, in fact, sh-OT assumption is relativistically separated from these assumptions.
Abstract. Various results show that oblivious transfer can be implemented using the assumption of noisy channels. Unfortunately, this assumption is not as weak as one might think, because in a cryptographic setting, these noisy channels must satisfy very strong security requirements. Unfair noisy channels, introduced by Damg˚ard, Kilian and Salvail [Eurocrypt ’99], reduce these limitations: They give the adversary an unfair advantage over the honest player, and therefore weaken the security requirements on the noisy channel. However, this model still has many shortcomings: For example, the adversary’s advantage is only allowed to have a very special form, and no error is allowed in the implementation. In this paper we generalize the idea of unfair noisy channels. We introduce two new models of cryptographic noisy channels that we call the weak erasure channel and the weak binary symmetric channel, and show how they can be used to implement oblivious transfer. Our models are more general and use much weaker assumptions than unfair noisy channels, which makes implementation a more realistic prospect. For example, these are the first models that allows the parameters to come from experimental evidence. 1
Which computational complexity assumptions are inherent to cryptography? We present a broad framework to pose and investigate this question. We first aim to understand the “cryptographic complexity ” of various tasks, independent of any computational assumptions. In our framework the cryptographic tasks are modeled as multi-party computation functionalities. We consider a universally composable secure protocol for one task given access to another task as the most natural complexity reduction between the two tasks. Some of these cryptographic complexity reductions are unconditional, others are unconditionally non-existent, but the vast majority appear to depend on computational assumptions; it is this relationship with computational assumptions that we study. In our detailed investigation of large classes of 2-party functionalities, we find that every reduction we are able to classify turns out to be unconditionally true or false, or else equivalent to the existence of one-way functions (OWF) or of semi-honest (equivalently, standalone-secure) oblivious transfer protocols (sh-OT). This leads us to conjecture that there are only a small finite number of distinct (i.e., black-box separable) computational assump-tions that are inherent among the infinite number of different cryptographic reductions in our framework. On moving to 3-party functionalities, there does exist a natural computational assumption, distinct from the OWF and sh-OT assumptions (namely, the existence of a key agreement protocol) that manifests itself as a cryptographic