dorsal/arxiv
View SchemaA quantum Goldreich-Levin theorem with cryptographic applications
| Authors | Mark Adcock, Richard Cleve |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0108095 |
| URL | https://arxiv.org/abs/quant-ph/0108095 |
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.
{
"annotation_id": "bd2fd2f9-9806-4ae8-866b-a8aefcc95499",
"date_created": "2026-03-02T18:01:45.395000Z",
"date_modified": "2026-03-02T18:01:45.395000Z",
"file_hash": "a53db64fccc280961a182ea3e710e4e1ec9265eb32ad95479d14d14804b2b1a3",
"private": false,
"record": {
"abstract": "We investigate the Goldreich-Levin Theorem in the context of quantum\ninformation. This result is a reduction from the computational problem of\ninverting a one-way function to the problem of predicting a particular bit\nassociated with that function. We show that the quantum version of the\nreduction -- between quantum one-way functions and quantum hard-predicates --\nis quantitatively more efficient than the known classical version. Roughly\nspeaking, if the one-way function acts on n-bit strings then the overhead in\nthe reduction is by a factor of O(n/epsilon^2) in the classical case but only\nby a factor of O(1/epsilon) in the quantum case, where 1/2 + epsilon is the\nprobability of predicting the hard-predicate. Moreover, we prove via a lower\nbound that, in a black-box framework, the classical version of the reduction\ncannot have overhead less than order n/epsilon^2.\n We also show that, using this reduction, a quantum bit commitment scheme that\nis perfectly binding and computationally concealing can be obtained from any\nquantum one-way permutation. This complements a recent result by Dumais, Mayers\nand Salvail, where the bit commitment scheme is perfectly concealing and\ncomputationally binding. We also show how to perform qubit commitment by a\nsimilar approach.",
"arxiv_id": "quant-ph/0108095",
"authors": [
"Mark Adcock",
"Richard Cleve"
],
"categories": [
"quant-ph"
],
"title": "A quantum Goldreich-Levin theorem with cryptographic applications",
"url": "https://arxiv.org/abs/quant-ph/0108095"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "0f86eaf6-d39f-4367-90d5-0515c1271425",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}