Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1301.5069 · journal of Groups complexity cryptology

Secrecy without one-way functions

Dima Yu. Grigoriev, Vladimir Shpilrain

Published Jan 1, 2013• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1515/gcc-2013-0002

Related papers

MULTI-PARTY SECURE COMPUTATION IN THE PROBLEM OF COLLISIONS PREVENTION

Oleg V. Kazarin

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.

Vestnik komp iuternykh i informatsionnykh tekhnologii•Jun 1, 2017•1 citation

Cryptography without one-way functions

Dima Yu. Grigoriev, Vladimir Shpilrain

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

•Jan 1, 2011•0 citations

Protocols for secure computations

Andrew Chi-Chih Yao

Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth. How can they carry out such a conversation? This is a special case of the following general problem. Suppose m people wish to compute the value of a function f(x1, x2, x3, . . . , xm), which is an integer-valued function of m integer variables xi of bounded range. Assume initially person Pi knows the value of xi and no other x’s. Is it possible for them to compute the value of f , by communicating among themselves, without unduly giving away any information about the values of their own variables? The millionaires’ problem corresponds to the case when m = 2 and f(x1, x2) = 1 if x1 < x2, and 0 otherwise. In this paper, we will give precise formulation of this general problem and describe three ways of solving it by use of one-way functions (i.e., functions which are easy to evaluate but hard to invert). These results have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc. We will also discuss the complexity question “How many bits need to be exchanged for the computation”, and describe methods to prevent participants from cheating. Finally, we study the question “What cannot be accomplished with one-way functions”. Before describing these results, we would like to put this work in perspective by first considering a unified view of secure computation in the next section.

•Nov 3, 1982•2,685 citations

On computational intractability assumptions in cryptography

Chandra Chekuri, Manoj Prabhakaran, Hemanta K. Maji

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.

•Jan 1, 2011•3 citations

Computationally secure quantum cryptography without one-way functions

Luowen Qian

Most interesting cryptography happens in the computational realm where all parties can only perform efficient computations. On one hand, without this constraint many practically relevant cryptographic tasks are infeasible; on the other, this constraint still captures the power of any physical attacker with limited resources. Classically, if the task of attacking almost any interesting computational cryptography is provably hard, then we would also derive from it the existence of one-way functions, and thus P ≠ NP as well. Quantum mechanics offers a more complete model of physical information in the real world. Recent works have proved oracle separations (Kretschmer’21; Kretschmer, Qian, Sinha, Tal’23; Lombardi, Ma, Wright’23) suggesting that computationally secure quantum cryptography could exist even if P = NP, or in other words, that classical cryptography is infeasible. This hints at the possibility of constructing a quantum cryptosystem and establishing its security without unproven assumptions, liberating cryptographers from the perpetual cat-and-mousegame. In this dissertation, we make initial progress towards this goal by developing a theory of quantum computational cryptography without assuming the existence ofone-way functions. More specifically, we establish the following results: • We introduce a simple and natural quantum cryptographic primitive called EFI pairs, and prove its existential equivalence to various other quantum cryptographic primitives, including commitment schemes, oblivious transfer, and zero knowledge.• We establish the “minimality” of EFI pairs by showing that their existence is implied by many natural cryptographic primitives. EFI pairs thus appear easier to construct than other primitives. • We show that the existence of EFI pairs (and the existentially equivalent primitives) is robust by showing how to upgrade various notions of “weak” security to standard security without any additional assumption. • We finally construct commitment schemes, oblivious transfer, and zero knowledge unconditionally if a piece of quantum advice is allowed. In contrast, classical analogues of these are impossible without first settling P ≠ NP even if we allow randomized advice.

•Jan 1, 2024•0 citations

Insecurity of quantum secure computations

Hoi‐Kwong Lo

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.

arXiv:quant-ph/9611031•Physical Review A•Aug 1, 1997•474 citations
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.
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
Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth. How can they carry out such a conversation? This is a special case of the following general problem. Suppose m people wish to compute the value of a function f(x1, x2, x3, . . . , xm), which is an integer-valued function of m integer variables xi of bounded range. Assume initially person Pi knows the value of xi and no other x’s. Is it possible for them to compute the value of f , by communicating among themselves, without unduly giving away any information about the values of their own variables? The millionaires’ problem corresponds to the case when m = 2 and f(x1, x2) = 1 if x1 < x2, and 0 otherwise. In this paper, we will give precise formulation of this general problem and describe three ways of solving it by use of one-way functions (i.e., functions which are easy to evaluate but hard to invert). These results have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc. We will also discuss the complexity question “How many bits need to be exchanged for the computation”, and describe methods to prevent participants from cheating. Finally, we study the question “What cannot be accomplished with one-way functions”. Before describing these results, we would like to put this work in perspective by first considering a unified view of secure computation in the next section.
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.
Most interesting cryptography happens in the computational realm where all parties can only perform efficient computations. On one hand, without this constraint many practically relevant cryptographic tasks are infeasible; on the other, this constraint still captures the power of any physical attacker with limited resources. Classically, if the task of attacking almost any interesting computational cryptography is provably hard, then we would also derive from it the existence of one-way functions, and thus P ≠ NP as well. Quantum mechanics offers a more complete model of physical information in the real world. Recent works have proved oracle separations (Kretschmer’21; Kretschmer, Qian, Sinha, Tal’23; Lombardi, Ma, Wright’23) suggesting that computationally secure quantum cryptography could exist even if P = NP, or in other words, that classical cryptography is infeasible. This hints at the possibility of constructing a quantum cryptosystem and establishing its security without unproven assumptions, liberating cryptographers from the perpetual cat-and-mousegame. In this dissertation, we make initial progress towards this goal by developing a theory of quantum computational cryptography without assuming the existence ofone-way functions. More specifically, we establish the following results: • We introduce a simple and natural quantum cryptographic primitive called EFI pairs, and prove its existential equivalence to various other quantum cryptographic primitives, including commitment schemes, oblivious transfer, and zero knowledge.• We establish the “minimality” of EFI pairs by showing that their existence is implied by many natural cryptographic primitives. EFI pairs thus appear easier to construct than other primitives. • We show that the existence of EFI pairs (and the existentially equivalent primitives) is robust by showing how to upgrade various notions of “weak” security to standard security without any additional assumption. • We finally construct commitment schemes, oblivious transfer, and zero knowledge unconditionally if a piece of quantum advice is allowed. In contrast, classical analogues of these are impossible without first settling P ≠ NP even if we allow randomized advice.
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.