dorsal/arxiv
View SchemaStatistical Zero Knowledge and quantum one-way functions
| Authors | Elham Kashefi, Iordanis Kerenidis |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0511266 |
| URL | https://arxiv.org/abs/quant-ph/0511266 |
| Journal | Journal of Theoretical Computer Sience, March 2007 |
Abstract
One-way functions are a very important notion in the field of classical cryptography. Most examples of such functions, including factoring, discrete log or the RSA function, can be, however, inverted with the help of a quantum computer. In this paper, we study one-way functions that are hard to invert even by a quantum adversary and describe a set of problems which are good such candidates. These problems include Graph Non-Isomorphism, approximate Closest Lattice Vector and Group Non-Membership. More generally, we show that any hard instance of Circuit Quantum Sampling gives rise to a quantum one-way function. By the work of Aharonov and Ta-Shma, this implies that any language in Statistical Zero Knowledge which is hard-on-average for quantum computers, leads to a quantum one-way function. Moreover, extending the result of Impagliazzo and Luby to the quantum setting, we prove that quantum distributionally one-way functions are equivalent to quantum one-way functions. Last, we explore the connections between quantum one-way functions and the complexity class QMA and show that, similarly to the classical case, if any of the above candidate problems is QMA-complete then the existence of quantum one-way functions leads to the separation of QMA and AvgBQP.
{
"annotation_id": "a76ad61c-84ce-4f10-a489-1c7c1d22d9c7",
"date_created": "2026-03-02T18:02:23.727000Z",
"date_modified": "2026-03-02T18:02:23.727000Z",
"file_hash": "7792664e05f5791afc273a26f74bc4f13415158f042258911eeeb71ecf27c8a6",
"private": false,
"record": {
"abstract": "One-way functions are a very important notion in the field of classical\ncryptography. Most examples of such functions, including factoring, discrete\nlog or the RSA function, can be, however, inverted with the help of a quantum\ncomputer. In this paper, we study one-way functions that are hard to invert\neven by a quantum adversary and describe a set of problems which are good such\ncandidates. These problems include Graph Non-Isomorphism, approximate Closest\nLattice Vector and Group Non-Membership. More generally, we show that any hard\ninstance of Circuit Quantum Sampling gives rise to a quantum one-way function.\nBy the work of Aharonov and Ta-Shma, this implies that any language in\nStatistical Zero Knowledge which is hard-on-average for quantum computers,\nleads to a quantum one-way function. Moreover, extending the result of\nImpagliazzo and Luby to the quantum setting, we prove that quantum\ndistributionally one-way functions are equivalent to quantum one-way functions.\nLast, we explore the connections between quantum one-way functions and the\ncomplexity class QMA and show that, similarly to the classical case, if any of\nthe above candidate problems is QMA-complete then the existence of quantum\none-way functions leads to the separation of QMA and AvgBQP.",
"arxiv_id": "quant-ph/0511266",
"authors": [
"Elham Kashefi",
"Iordanis Kerenidis"
],
"categories": [
"quant-ph"
],
"journal_ref": "Journal of Theoretical Computer Sience, March 2007",
"title": "Statistical Zero Knowledge and quantum one-way functions",
"url": "https://arxiv.org/abs/quant-ph/0511266"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "3a70cc7a-ea1f-496d-80d0-bbfc299c0faa",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}