A Quantum Goldreich-Levin Theorem with Cryptographic Applications

Mark Adcock, Richard Cleve, Kazuo Iwama +2 more

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.

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.

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.

Hoi‐Kwong Lo