 Abstract:
 Oneway functions are a 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 oneway 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 oneway functions. These problems include Graph NonIsomorphism, Approximate Closest Lattice Vector and Group NonMembership. More generally, we show that any hard instance of Circuit Quantum Sampling gives rise to a quantum oneway function. By the work of Aharanov and TaShma [D. Aharanov, A. TaShma, 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 hardonaverage for quantum computers leads to a quantum oneway function. Moreover, extending the result of Impagliazzo and Luby [R. Impagliazzo, M. Luby, Oneway 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 oneway functions are equivalent to quantum oneway functions.
 Links To Paper
 No links available
 Bibtex format
 @Article{EDIINFRR1166,
 author = {
Elham Kashefi
and I Kerenidis
},
 title = {Statistical Zero Knowledge and quantum oneway functions},
 journal = {Journal of Theoretical Computer Science},
 publisher = {Elsevier},
 year = 2007,
 month = {Jun},
 volume = {378 (1)},
 pages = {101116},
 doi = {10.1016/j.tcs.2007.03.013},
 }
