Physics – Quantum Physics
Scientific paper
2005-11-30
Journal of Theoretical Computer Sience, March 2007
Physics
Quantum Physics
20 pages; Computational Complexity, Cryptography and Quantum Physics; Published version, main results unchanged, presentation
Scientific paper
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.
Kashefi Elham
Kerenidis Iordanis
No associations
LandOfFree
Statistical Zero Knowledge and quantum one-way functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Statistical Zero Knowledge and quantum one-way functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistical Zero Knowledge and quantum one-way functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-430528