Statistical zero knowledge and quantum one-way functions

One-way functions area fundamental notion in cryptography, since they are the necessary condition for the existence of secure encryption schemes. Most examples of such functions, including Factoring, Discrete Logarithm or the RSA function, however, can be inverted with the help of a quantum computer. Hence, it is very important to study the possibility of quantum one-way functions, i.e. functions which are easily computable by a classical algorithm but are hard to invert even by a quantum adversary. In this paper, we provide a set of problems that are good candidates for quantum one-way functions. 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 [D. Aharonov, A. Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, in: Proceedings of STOC02 - Symposium on the Theory of Computing, 2001], 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 [R. Impagliazzo, M. Luby, One-way functions are essential for complexity based cryptography, in: Proceedings of FOCS89 Symposium on Foundations of Computer Science, 1989] to the quantum setting, we prove that quantum distributionally one-way functions are equivalent to quantum one-way functions. (c) 2007 Elsevier B.V. All rights reserved.