We show that some problems in cryptography can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious “P ̸ = NP ” conjecture. This is why cryptographic primitives that do not employ one-way functions are often called “unconditionally secure”. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions of two or more elements of an arbitrary constructible ring, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal “intermediate results ” of a computation. For example, when we compute the sum of k numbers, only the final result is known to (one of) the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of the “two millionaires problem”. While it is fairly obvious that a secure (bit) commitment between two parties is
We show that some problems in cryptography can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious “P ̸ = NP ” conjecture. This is why cryptographic primitives that do not employ one-way functions are often called “unconditionally secure”. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions of two or more elements of an arbitrary constructible ring, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal “intermediate results ” of a computation. For example, when we compute the sum of k numbers, only the final result is known to (one of) the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of the “two millionaires problem”. While it is fairly obvious that a secure (bit) commitment between two parties is
We show that some problems in information security can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious “” conjecture. This is why cryptographic primitives that do not employ one-way functions are often called “unconditionally secure”. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions of two or more elements of an arbitrary constructible ring, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal “intermediate results” of a computation. For example, when we compute the sum of k numbers, only the final result is known to the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of the “two millionaires problem”. Then, while it is fairly obvious that a secure (bit) commitment between two parties is impossible without a one-way function, we show that it is possible if the number of parties is at least 3. We also show how our unconditionally secure (bit) commitment scheme for three parties can be used to arrange an unconditionally secure (bit) commitment between just two parties if they use a “dummy” (e.g., a computer) as the third party. We explain how our concept of a “dummy” is different from the well-known concept of a “trusted third party”. Based on a similar idea, we also offer an unconditionally secure k - n oblivious transfer protocol between two parties who use a “dummy”. We also suggest a protocol, without using a one-way function, for the so-called “mental poker”, i.e., a fair card dealing (and playing) over distance. Finally, we propose a secret sharing scheme where an advantage over Shamir's and other known secret sharing schemes is that nobody, including the dealer, ends up knowing the shares (of the secret) owned by any particular player. It should be mentioned that computational cost of our protocols is negligible to the point that all of them can be executed without a computer.
We show that some problems in information security can be solved without using one-way functions.The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious "P = N P " conjecture.This is why cryptographic primitives that do not employ one-way functions are often called "unconditionally secure".In this paper, we suggest protocols for secure computation of the sum, product, and some other functions of two or more elements of an arbitrary constructible ring, without using any one-way functions.A new input that we offer here is that, in contrast with other proposals, we conceal "intermediate results" of a computation.For example, when we compute the sum of k numbers, only the final result is known to the parties; partial sums are not known to anybody.Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of the "two millionaires problem".Then, while it is fairly obvious that a secure (bit) commitment between two parties is impossible without a one-way function, we show that it is possible if the number of parties is at least 3.We also show how our unconditionally secure (bit) commitment scheme for 3 parties can be used to arrange an unconditionally secure (bit) commitment between just two parties if they use a "dummy" (e.g., a computer) as the third party.We explain how our concept of a "dummy" is different from a wellknown concept of a "trusted third party".Based on a similar idea, we also offer an unconditionally secure k-n oblivious transfer protocol between two parties who use a "dummy".We also suggest a protocol, without using a one-way function, for the so-called "mental poker", i.e., a fair card dealing (and playing) over distance.Finally, we propose a secret sharing scheme where an advantage over Shamir's and other known secret sharing schemes is that nobody, including the dealer, ends up knowing the shares (of the secret) owned by any particular player.It should be mentioned that computational cost of our protocols is negligible to the point that all of them can be executed without a computer.
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.
Cryptography is the science and practice of designing computing and communication systems that are secure in the presence of adversaries.Among the central topics in cryptographic research, public-key encryption enables secure communication between two parties, while digital signatures provide guarantees on the authenticity of information.To prove the security of cryptographic schemes, we use reductions.Reduction is a fundamental concept in computer science.When problem A is reduced to problem B, it implies that B is at least as hard as A. To show such a relationship, we usually build a reduction algorithm that solves A efficiently using an algorithm that solves B as a subroutine.Such reductions not only establish the security of the cryptographic primitives, but also give a computational complexity perspective.For example, one can identify the minimal assumption on which cryptographic systems can be based.The existence of one-way functions is considered a minimal assumption in cryptography.In other words, the existence of one-way functions is essential for the existence of any cryptographic primitive.A function f is said to be one-way if, given f (x), it is computationally infeasible to efficiently recover a corresponding preimage.While one-wayness is a minimal assumption, it is also known to suffice for deriving important cryptographic primitives such as symmetric-key encryption and digital signatures.Cryptographic primitives can thus be divided into those that can be derived from one-way functions and those that cannot.Cryptographic primitives that can be derived from one-way functions are referred to as Minicrypt.In this way, one-way functions play a central role in providing a hierarchical understanding of modern cryptographic theory.When quantum communication and computation are incorporated into cryptographic protocols, it becomes possible to derive a broader class of cryptographic primitives from one-way functions.For example, while there is evidence that public-key encryption cannot be constructed from one-way functions alone in the classical setting, recent works have shown that quantum public-key encryption can be constructed from one-way functions when quantum communication channels are available.Thus, even without altering the classical boundaries, incorporating quantum communication and computation leaves ample room for phenomena that differ from those observed in the classical setting.The class of cryptographic primitives that can be constructed from one-way functions, assuming quantum computation and communication, is referred to as MiniQCrypt.As quantum technologies continue to advance and the realization of quantum communication and quantum computers becomes increasingly plausible, the study of one-way functions must be revisited and discussed within these quantum frameworks.We identify two main challenges in this area.The first challenge is to generalize the quantum reduction from one-wayness to unpredictability.The classical reduction from onewayness to unpredictability, known as the Goldreich-Levin theorem, is not only fundamental in cryptography but also plays an important role in computational complexity theory.A quantum analogue of this theorem was established by Adcock and Cleve.However, whether the quantum Goldreich-Levin theorem holds not only in the binary setting but also over more general domains such as Z q remains a nontrivial open problem.The second challenge i
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
It had been widely claimed that quantum mechanics can protect private information during public decision in, for example, the so-called two-party secure computation. If this were the case, quantum smart-cards, storing confidential information accessible only to a proper reader, could prevent fake teller machines from learning the PIN (personal identification number) from the customers' input. Although such optimism has been challenged by the recent surprising discovery of the insecurity of the so-called quantum bit commitment, the security of quantum two-party computation itself remains unaddressed. Here I answer this question directly by showing that all one-sided two-party computations (which allow only one of the two parties to learn the result) are necessarily insecure. As corollaries to my results, quantum one-way oblivious password identification and the so-called quantum one-out-of-two oblivious transfer are impossible. I also construct a class of functions that cannot be computed securely in any two-sided two-party computation. Nevertheless, quantum cryptography remains useful in key distribution and can still provide partial security in ``quantum money'' proposed by Wiesner.