A General Construction of Hard-Core Predicates for Any Quantum One-Way Function

Shujiao Cao, Rui Xue

Abstract One-way quantum state generators (), which serve as the quantum analog of one-way functions (), have attracted significant interest due to their potential applications and the reduced assumption requirements compared to . This paper explores the applications of structured and presents several results: We construct efficiently samplable, statistically far but computationally indistinguishable pairs of distributions ( pairs) from secretly-verifiable with somewhat injectivity, which has implications for quantum commitment schemes; We demonstrate that somewhat injective can be derived from almost regular ; We also focus on a specific type of , termed , and prove that the existence of a single-copy-secure hard-core predicate for these is both necessary and sufficient for constructing pairs; Moreover, we propose a simple quantum commitment scheme based on the decisional assumption, offering improved parameter choices and flexibility over classical schemes. These findings contribute to the understanding and potential applications of in quantum cryptography.

Yao Tang, Tao Shang, Jianwei Liu

Mark Adcock, Richard Cleve

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.

Manas K. Patra

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.

Peter Mittelstaedt