Informatics Report Series


Report   

EDI-INF-RR-1166


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Statistical Zero Knowledge and quantum one-way functions
Authors: Elham Kashefi ; I Kerenidis
Date:Jun 2007
Publication Title:Journal of Theoretical Computer Science
Publisher:Elsevier
Publication Type:Journal Article Publication Status:Published
Volume No:378 (1) Page Nos:101-116
DOI:10.1016/j.tcs.2007.03.013 ISBN/ISSN:0304-3975
Abstract:
One-way 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 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 Aharanov and Ta-Shma [D. Aharanov, 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.
Links To Paper
No links available
Bibtex format
@Article{EDI-INF-RR-1166,
author = { Elham Kashefi and I Kerenidis },
title = {Statistical Zero Knowledge and quantum one-way functions},
journal = {Journal of Theoretical Computer Science},
publisher = {Elsevier},
year = 2007,
month = {Jun},
volume = {378 (1)},
pages = {101-116},
doi = {10.1016/j.tcs.2007.03.013},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh