Statistical Zero Knowledge and quantum one-way functions
| dc.creator | Kashefi, Elham | |
| dc.creator | Kerenidis, Iordanis | |
| dc.date | 2005-11-30 | |
| dc.date | 2007-03-06 | |
| dc.date.accessioned | 2026-07-07T07:50:18Z | |
| dc.date.available | 2026-07-07T07:50:18Z | |
| dc.description | 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. | |
| dc.description | 20 pages; Computational Complexity, Cryptography and Quantum Physics; Published version, main results unchanged, presentation improved | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0511266 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0511266 | |
| dc.identifier | Journal of Theoretical Computer Sience, March 2007 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/125119 | |
| dc.subject | Quantum Physics | |
| dc.title | Statistical Zero Knowledge and quantum one-way functions | |
| dc.type | text |