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:quant-ph/0108095

A quantum Goldreich-Levin theorem with cryptographic applications

Mark Adcock, Richard Cleve

Published Aug 22, 2001• 2 citations
arXivHTMLPDF

Abstract

We investigate the Goldreich-Levin Theorem in the context of quantum information. This result is a reduction from the computational problem of inverting a one-way function to the problem of predicting a particular bit associated with that function. We show that the quantum version of the reduction -- between quantum one-way functions and quantum hard-predicates -- is quantitatively more efficient than the known classical version. Roughly speaking, if the one-way function acts on n-bit strings then the overhead in the reduction is by a factor of O(n/epsilon^2) in the classical case but only by a factor of O(1/epsilon) in the quantum case, where 1/2 + epsilon is the probability of predicting the hard-predicate. Moreover, we prove via a lower bound that, in a black-box framework, the classical version of the reduction cannot have overhead less than order n/epsilon^2. We also show that, using this reduction, a quantum bit commitment scheme that is perfectly binding and computationally concealing can be obtained from any quantum one-way permutation. This complements a recent result by Dumais, Mayers and Salvail, where the bit commitment scheme is perfectly concealing and computationally binding. We also show how to perform qubit commitment by a similar approach.

DOI
10.48550/arxiv.quant-ph/0108095

Related papers

A Quantum Goldreich-Levin Theorem with Cryptographic Applications

Mark Adcock, Richard Cleve

We investigate the Goldreich-Levin Theorem in the context of quantum information. This result is a reduction from the problem of inverting a one-way function to the problem of predicting a particular bit associated with that function. We show that the quantum version of the reduction is quantitatively more ecient than the known classical version. If the one-way function acts on n-bit strings then the overhead in the reduction is by a factor of O(n=" ) in the classical case but only by a factor of O(1=") in the quantum case, where 2 + " is the probability of predicting the hard-predicate. We also show that, using the GoldreichLevin Theorem, a quantum bit (or qubit) commitment scheme that is perfectly binding and computationally concealing can be obtained from any quantum one-way permutation.

•Jan 1, 2001•0 citations

The classical and quantum complexity of the Goldreich-Levin problem with applications to bit commitment

Mark Adcock

The classical Goldreich-Levin (G-L) theorem is presented as a block-box query prob­lem, referred to herein as the G-L problem. The query complexity of this problem is bounded in both classical and quantum settings. The well-known upper bound of the classical G-L problem is analyzed in a pedagogical manner. A proof of the lower bound of the classical G-L problem is given using the techniques of classical information theory. This classical analysis is then extended to the realm of quantum computin g by noting the similarity of the noiseless G-L problem to the inner-product query problem solved by the quantum circuit defined by Bernstein and Vazirani (B-V) . An upper bound of the query complexity of the quantum G-L problem is proven by extension of the B-V circuit to incorporate noisy inner-product queries. The lower bound of the query complexity of the quantum G-L problem is proven by adapting the proof of the optimaliy of the quantum search algorithm to include modified inner-product queries. Both the classical and quantum versions of the Goldreich-Levi n theorem have cryptographic applications in the area of bit commitment. A discussion of the im­possibility of unconditional quantum bit commitment is followed by the presentation of both classical and quantum bit commitment protocols that are based on the as­sumption of the existence of classical and quantum one-way permutations. The relative security of the classical and quant m protocols are compared where it is shown that the quantum version is quantitatively more secure.

•Jan 1, 2004•1 citation

Non-Interactive Statistically-Hiding Quantum Bit Commitment from Any Quantum One-Way Function

Takeshi Koshiba, Takanori Odaira

We provide a non-interactive quantum bit commitment scheme which has statistically-hiding and computationally-binding properties from any quantum one-way function. Our protocol is basically a parallel composition of the previous non-interactive quantum bit commitment schemes (based on quantum one-way permutations, due to Dumais, Mayers and Salvail (EUROCRYPT 2000)) with pairwise independent hash functions. To construct our non-interactive quantum bit commitment scheme from any quantum one-way function, we follow the procedure below: (i) from Dumais-Mayers-Salvail scheme to a weakly-hiding and 1-out-of-2 binding commitment (of a parallel variant); (ii) from the weakly-hiding and 1-out-of-2 binding commitment to a strongly-hiding and 1-out-of-2 binding commitment; (iii) from the strongly-hiding and 1-out-of-2 binding commitment to a normal statistically-hiding commitment. In the classical case, statistically-hiding bit commitment scheme (by Haitner, Nguyen, Ong, Reingold and Vadhan (SIAM J. Comput., Vol.39, 2009)) is also constructible from any one-way function. While the classical statistically-hiding bit commitment has large round complexity, our quantum scheme is non-interactive, which is advantageous over the classical schemes. A main technical contribution is to provide a quantum analogue of the new interactive hashing theorem, due to Haitner and Reingold (CCC 2007). Moreover, the parallel composition enables us to simplify the security analysis drastically.

arXiv:1102.3441•Feb 16, 2011•6 citations

How to Convert a Flavor of Quantum Bit Commitment

Claude Crépeau, Frédéric Légaré, Louis Salvail

In this paper we show how to convert a statistically binding but computationally concealing quantum bit commitment scheme into a computationally binding but statistically concealing scheme. For a security parameter n, the construction of the statistically concealing scheme requires O(n^2) executions of the statistically binding scheme. As a consequence, statistically concealing but computationally binding quantum bit commitments can be based upon any family of quantum one-way functions. Such a construction is not known to exist in the classical world.

BRICS Report Series•Jun 22, 2000•5 citations

The Breakdown of Classical Minicrypt Equivalences in the Quantum-Computation Classical-Communication Model

Boyang Chen, Yiming Wang, Ziyi Xie

Classically, it is well-known that several fundamental cryptographic primitives, including one-way functions, pseudorandom number generators, commitments, and signatures, characterize the same cryptographic world, which is known as "Minicrypt". In this paper, we investigate to what extent this picture persists in the quantum-computation classical-communication (QCCC) setting, where parties may perform quantum local computation, but communicate through only classical messages. We demonstrate that the classical Minicrypt landscape breaks down in the QCCC model by oracle separations. We construct two oracle worlds where efficiently verifiable one-way puzzles (EV-OWPuzz) exist. By a known equivalence, QCCC one-time signatures also exist in both worlds. In the first, one-way functions do not exist, even if we allow quantum pseudodeterministic evaluation. In the second, QCCC bit commitments do not exist. Thus, the classical Minicrypt reductions from signatures to one-way functions and bit commitments have no fully black-box counterparts in the QCCC setting. Our proofs develop techniques for analyzing the random phase states, including a concentration theorem and an LOCC decoupling theorem. As a separate result, we establish quantum sum-binding for the NOVY protocol, settling the question of its post-quantum security. We also generalize it to a fully black-box construction of a QCCC commitment from EV-OWPuzz with nearly uniform puzzle distribution, complementing our oracle separation results.

quant-pharXiv:2609.33098•Sep 29, 2026•0 citations

A Non-Interactive Quantum Bit Commitment Scheme that Exploits the Computational Hardness of Quantum State Distinction

Tomoyuki Yamakami

We propose an efficient quantum protocol performing quantum bit commitment, which is a simple cryptographic primitive involved with two parties, called a committer and a verifier. Our protocol is non-interactive, uses no supplemental shared information, and achieves computational concealing and statistical binding under a natural complexity-theoretical assumption. An earlier protocol in the literature relies on the existence of an efficient quantum one-way function. Our protocol, on the contrary, exploits a seemingly weaker assumption on computational difficulty of distinguishing two specific ensembles of reduced quantum states. This assumption is guaranteed by, for example, computational hardness of solving the graph automorphism problem efficiently on a quantum computer.

arXiv:1309.0436•Sep 2, 2013•0 citations
We investigate the Goldreich-Levin Theorem in the context of quantum information. This result is a reduction from the computational problem of inverting a one-way function to the problem of predicting a particular bit associated with that function. We show that the quantum version of the reduction -- between quantum one-way functions and quantum hard-predicates -- is quantitatively more efficient than the known classical version. Roughly speaking, if the one-way function acts on n-bit strings then the overhead in the reduction is by a factor of O(n/epsilon^2) in the classical case but only by a factor of O(1/epsilon) in the quantum case, where 1/2 + epsilon is the probability of predicting the hard-predicate. Moreover, we prove via a lower bound that, in a black-box framework, the classical version of the reduction cannot have overhead less than order n/epsilon^2. We also show that, using this reduction, a quantum bit commitment scheme that is perfectly binding and computationally concealing can be obtained from any quantum one-way permutation. This complements a recent result by Dumais, Mayers and Salvail, where the bit commitment scheme is perfectly concealing and computationally binding. We also show how to perform qubit commitment by a similar approach.
We investigate the Goldreich-Levin Theorem in the context of quantum information. This result is a reduction from the problem of inverting a one-way function to the problem of predicting a particular bit associated with that function. We show that the quantum version of the reduction is quantitatively more ecient than the known classical version. If the one-way function acts on n-bit strings then the overhead in the reduction is by a factor of O(n=" ) in the classical case but only by a factor of O(1=") in the quantum case, where 2 + " is the probability of predicting the hard-predicate. We also show that, using the GoldreichLevin Theorem, a quantum bit (or qubit) commitment scheme that is perfectly binding and computationally concealing can be obtained from any quantum one-way permutation.
The classical Goldreich-Levin (G-L) theorem is presented as a block-box query prob­lem, referred to herein as the G-L problem. The query complexity of this problem is bounded in both classical and quantum settings. The well-known upper bound of the classical G-L problem is analyzed in a pedagogical manner. A proof of the lower bound of the classical G-L problem is given using the techniques of classical information theory. This classical analysis is then extended to the realm of quantum computin g by noting the similarity of the noiseless G-L problem to the inner-product query problem solved by the quantum circuit defined by Bernstein and Vazirani (B-V) . An upper bound of the query complexity of the quantum G-L problem is proven by extension of the B-V circuit to incorporate noisy inner-product queries. The lower bound of the query complexity of the quantum G-L problem is proven by adapting the proof of the optimaliy of the quantum search algorithm to include modified inner-product queries. Both the classical and quantum versions of the Goldreich-Levi n theorem have cryptographic applications in the area of bit commitment. A discussion of the im­possibility of unconditional quantum bit commitment is followed by the presentation of both classical and quantum bit commitment protocols that are based on the as­sumption of the existence of classical and quantum one-way permutations. The relative security of the classical and quant m protocols are compared where it is shown that the quantum version is quantitatively more secure.
We provide a non-interactive quantum bit commitment scheme which has statistically-hiding and computationally-binding properties from any quantum one-way function. Our protocol is basically a parallel composition of the previous non-interactive quantum bit commitment schemes (based on quantum one-way permutations, due to Dumais, Mayers and Salvail (EUROCRYPT 2000)) with pairwise independent hash functions. To construct our non-interactive quantum bit commitment scheme from any quantum one-way function, we follow the procedure below: (i) from Dumais-Mayers-Salvail scheme to a weakly-hiding and 1-out-of-2 binding commitment (of a parallel variant); (ii) from the weakly-hiding and 1-out-of-2 binding commitment to a strongly-hiding and 1-out-of-2 binding commitment; (iii) from the strongly-hiding and 1-out-of-2 binding commitment to a normal statistically-hiding commitment. In the classical case, statistically-hiding bit commitment scheme (by Haitner, Nguyen, Ong, Reingold and Vadhan (SIAM J. Comput., Vol.39, 2009)) is also constructible from any one-way function. While the classical statistically-hiding bit commitment has large round complexity, our quantum scheme is non-interactive, which is advantageous over the classical schemes. A main technical contribution is to provide a quantum analogue of the new interactive hashing theorem, due to Haitner and Reingold (CCC 2007). Moreover, the parallel composition enables us to simplify the security analysis drastically.
In this paper we show how to convert a statistically binding but computationally concealing quantum bit commitment scheme into a computationally binding but statistically concealing scheme. For a security parameter n, the construction of the statistically concealing scheme requires O(n^2) executions of the statistically binding scheme. As a consequence, statistically concealing but computationally binding quantum bit commitments can be based upon any family of quantum one-way functions. Such a construction is not known to exist in the classical world.
Classically, it is well-known that several fundamental cryptographic primitives, including one-way functions, pseudorandom number generators, commitments, and signatures, characterize the same cryptographic world, which is known as "Minicrypt". In this paper, we investigate to what extent this picture persists in the quantum-computation classical-communication (QCCC) setting, where parties may perform quantum local computation, but communicate through only classical messages. We demonstrate that the classical Minicrypt landscape breaks down in the QCCC model by oracle separations. We construct two oracle worlds where efficiently verifiable one-way puzzles (EV-OWPuzz) exist. By a known equivalence, QCCC one-time signatures also exist in both worlds. In the first, one-way functions do not exist, even if we allow quantum pseudodeterministic evaluation. In the second, QCCC bit commitments do not exist. Thus, the classical Minicrypt reductions from signatures to one-way functions and bit commitments have no fully black-box counterparts in the QCCC setting. Our proofs develop techniques for analyzing the random phase states, including a concentration theorem and an LOCC decoupling theorem. As a separate result, we establish quantum sum-binding for the NOVY protocol, settling the question of its post-quantum security. We also generalize it to a fully black-box construction of a QCCC commitment from EV-OWPuzz with nearly uniform puzzle distribution, complementing our oracle separation results.
We propose an efficient quantum protocol performing quantum bit commitment, which is a simple cryptographic primitive involved with two parties, called a committer and a verifier. Our protocol is non-interactive, uses no supplemental shared information, and achieves computational concealing and statistical binding under a natural complexity-theoretical assumption. An earlier protocol in the literature relies on the existence of an efficient quantum one-way function. Our protocol, on the contrary, exploits a seemingly weaker assumption on computational difficulty of distinguishing two specific ensembles of reduced quantum states. This assumption is guaranteed by, for example, computational hardness of solving the graph automorphism problem efficiently on a quantum computer.