Abstract. We consider the problem of securely computing the Greater Than (GT) predicate and its generalization – securely determining membership in a union of intervals. We approach these problems from the point of view of Q-Conditional Oblivious Transfer (Q-COT), introduced by Di Crescenzo, Ostrovsky and Rajagopalan [4]. Q-COT is an oblivious transfer that occurs iff predicate Q evaluates to true on the parties’ inputs. We are working in the semi-honest model with computationally unbounded receiver. In this paper, we propose: (i) a stronger, simple and intuitive definition of COT, which we call strong COT, or Q-SCOT. (ii) A simpler and more efficient one-round protocol for securely computing GT and GT-SCOT. (iii) A simple and efficient modular construction reducing SCOT based on membership in a union of intervals (UI-SCOT) to GT-SCOT, producing an efficient one-round UI-SCOT. 1
Abstract. We consider the problem of securely computing the Greater Than (GT) predicate and its generalization – securely determining membership in a union of intervals. We approach these problems from the point of view of Q-Conditional Oblivious Transfer (Q-COT), introduced by Di Crescenzo, Ostrovsky and Rajagopalan [4]. Q-COT is an oblivious transfer that occurs iff predicate Q evaluates to true on the parties’ inputs. We are working in the semi-honest model with computationally unbounded receiver. In this paper, we propose: (i) a stronger, simple and intuitive definition of COT, which we call strong COT, or Q-SCOT. (ii) A simpler and more efficient one-round protocol for securely computing GT and GT-SCOT. (iii) A simple and efficient modular construction reducing SCOT based on membership in a union of intervals (UI-SCOT) to GT-SCOT, producing an efficient one-round UI-SCOT. 1
Abstract We consider the problem of securely evaluating the Greater Than (GT) predicate and its extension – transferring one of two secrets, depending on the result of comparison. We generalize our solutions and show how to securely decide membership in the union of a set of intervals. We then consider the related problem of comparing two encrypted numbers. We show how to efficiently apply our solutions to practical settings, such as auctions with the semi-honest auctioneer, proxy selling, etc. All of our protocols are one round. We propose new primitives, Strong Conditional Oblivious Transfer (SCOT) and Conditional Encrypted Mapping (CEM), which capture common security properties of one round protocols in a variety of settings, which may be of independent interest.
Committed Oblivious Transfer (COT) is a two-party primitive that combines one-out-of-two oblivious transfer with bit commitment. In the beginning of COT, a sender is committed to bits b0, b1 and a receiver to a choice bit c. In the end, the receiver is committed to bc without learning anything about b1-c, while the sender learns nothing about c. This primitive implies secure multi-party computation assuming that a broadcast channel is available. In this paper, we introduce the first universally composable unconditionally secure committed oblivious transfer protocol based on a Trusted Initializer (TI), which pre-distributes data to the parties. Our protocol builds on simple bit commitment and oblivious transfer protocols, using XOR commitments to prove simple relations in zero-knowledge. Besides providing very high security guarantees, our protocols are significantly simpler and more efficient than previous results, since they rely on pre-computed operations distributed by the TI.
Oblivious transfer is a fundamental tool in modern cryptography. It plays an important role in the research of security protocols. In recent years, many oblivious transfer variants with more powerful functionalities are proposed, so as to be fit in different kinds of requirements and scenarios. In this paper, a new oblivious transfer variant, called cut-and-choose bilateral oblivious transfer, is proposed. Based on homomorphic encryption, an efficient one-round protocol of this primitive is constructed, accompanied with rigorous security proof in semi-honest model. When applied in security protocols based on cut-and-choose technique (especially in secure two-party computation), cut-and-choose bilateral oblivious transfer enables a more modular high-level description of the protocol framework, as well as reduces the round complexity of the protocols. Besides, as a basic tool in the information security area, this primitive itself is of independent research interest.
Abstract. We consider the following problem: Assuming that Alice and Bob have an integer interval [a, e] and an integer b respectively, for a commitment c to b, Alice and Bob jointly check whether b is within [a, e] without revealing their inputs, where either party may behave malicious-ly. A special case of the problem is the secure integer comparison in the malicious model. This problem mainly arises from location-based access control systems where one party needs to assure to the other party that its location is within some definite area. Our main result is a constant-round protocol that exhibit the square of log e communication and the square of log e exponentiations with simulation-based security. At the heart of the construction is perfec-t k-ary index and corresponding zero-knowledge proof techniques. We consider a more general case of the problem where the interval is substi-tuted by a union of intervals.
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.
We present unconditionally perfectly secure protocols in the semi-honest setting for several functionalities: (1) private elementwise equality; (2) private bitwise integer comparison; and (3) bit-decomposition. These protocols are built upon a new concept called Shared Oblivious Transfer (Shared OT). Shared OT extends the one-out-of-N String OT by replacing strings with integers modulo M and allowing additive secret-sharing of all inputs and outputs. These extensions can be implemented by simple local computations without incurring additional OT invocations. We believe our Shared OT may be of independent interest. Our protocols demonstrate the best round, communication, and computational complexities compared to all other protocols secure in a similar setting. Moreover, all of our protocols involve either 2 or 3 rounds.