Abstract
This paper studies general properties of quantum zero- knowledge proof systems. Among others, the following properties are proved on quantum computational zero-knowledge proofs:
-
Honest-verifier quantum zero-knowledge equals general quantum zero-knowledge.
-
Public-coin quantum zero-knowledge equals general quantum zero-knowledge.
-
Quantum zero-knowledge with perfect completeness equals general quantum zero-knowledge with imperfect completeness.
-
Any quantum zero-knowledge proof system can be transformed into a three-message public-coin quantum zero-knowledge proof system of perfect completeness with polynomially small error in soundness (hence with arbitrarily small constant error in soundness).
All the results proved in this paper are unconditional, i.e., they do not rely any computational assumptions. The proofs for all the statements are direct and do not use complete promise problems, and thus, essentially the same method works well even for quantum statistical and perfect zero-knowledge proofs. In particular, all the four properties above hold also for the statistical zero-knowledge case (the first two were shown previously by Watrous), and the first two properties hold even for the perfect zero-knowledge case. It is also proved that allowing a simulator to output “FAIL” does not change the power of quantum perfect zero-knowledge proofs. The corresponding properties are not known to hold in the classical perfect zero-knowledge case.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aharonov, D., Kitaev, A.Yu., Nisan, N.: Quantum circuits with mixed states. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 20–30 (1998)
Aiello, W., Håstad, J.: Statistical zero-knowledge languages can be recognized in two rounds. Journal of Computer and System Sciences 42(3), 327–345 (1991)
Ben-Aroya, A., Ta-Shma, A.: Quantum expanders and the quantum entropy difference problem. arXiv.org e-Print archive, quant-ph/0702129 (2007)
Damgård, I., Fehr, S., Salvail, L.: Zero-knowledge proofs and string commitments withstanding quantum attacks. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 254–272. Springer, Heidelberg (2004)
Even, S., Selman, A.L., Yacobi, Y.: The complexity of promise problems with applications to public-key cryptography. Information and Control 61(2), 159–173 (1984)
Fortnow, L.J.: The complexity of perfect zero-knowledge. In: Micali, S. (ed.) Randomness and Computation. Advances in Computing Research, vol. 5, pp. 327–343. JAI Press (1989)
Goldreich, O.: Foundations of Cryptography – Volume 1 Basic Tools. Cambridge University Press, Cambridge (2001)
Goldreich, O.: Zero-knowledge twenty years after its invention. Electronic Colloquium on Computational Complexity, Report No. 63 (2002)
Goldreich, O., Goldwasser, S.: On the limits of nonapproximability of lattice problems. Journal of Computer and System Sciences 60(3), 540–563 (2000)
Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in have zero-knowledge proof systems. Journal of the ACM 38(3), 691–729 (1991)
Goldreich, O., Sahai, A., Vadhan, S.P.: Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 399–408 (1998)
Goldreich, O., Vadhan, S.P.: Comparing entropies in statistical zero knowledge with applications to the structure of SZK. In: Fourteenth Annual IEEE Conference on Computational Complexity, pp. 54–73 (1999)
Goldwasser, S., Micali, S., Rackoff, C.W.: The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18(1), 186–208 (1989)
van de Graaf, J.: Towards a formal definition of security for quantum protocols. PhD thesis, Département d’Informatique et de Recherche Opérationnelle, Université de Montréal (December 1997)
Kitaev, A.Yu., Shen, A.H., Vyalyi, M.N.: Classical and Quantum Computation. Graduate Studies in Mathematics, vol. 47. American Mathematical Society (2002)
Kitaev, A.Yu., Watrous, J.H.: Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 608–617 (2000)
Kobayashi, H.: Non-interactive quantum perfect and statistical zero-knowledge. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 178–188. Springer, Heidelberg (2003)
Kobayashi, H.: General properties of quantum zero-knowledge proofs. arXiv.org e-Print archive, arXiv:0705.1129 [quant-ph] (2007)
Marriott, C., Watrous, J.H.: Quantum Arthur-Merlin games. Computational Complexity 14(2), 122–152 (2005)
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Okamoto, T.: On relationships between statistical zero-knowledge proofs. Journal of Computer and System Sciences 60(1), 47–108 (2000)
Sahai, A., Vadhan, S.P.: A complete problem for statistical zero knowledge. Journal of the ACM 50(2), 196–249 (2003)
Shor, P.W.: Fault-tolerant quantum computation. In: 37th Annual Symposium on Foundations of Computer Science, pp. 56–65 (1996)
Vadhan, S.P.: An unconditional study of computational zero-knowledge. SIAM Journal on Computing 36(4), 1160–1214 (2006)
Watrous, J.H.: Limits on the power of quantum statistical zero-knowledge. In: 43rd Annual Symposium on Foundations of Computer Science, pp. 459–468 (2002)
Watrous, J.H.: PSPACE has constant-round quantum interactive proof systems. Theoretical Computer Science 292(3), 575–588 (2003)
Watrous, J.H.: Zero-knowledge against quantum attacks. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 296–305 (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kobayashi, H. (2008). General Properties of Quantum Zero-Knowledge Proofs. In: Canetti, R. (eds) Theory of Cryptography. TCC 2008. Lecture Notes in Computer Science, vol 4948. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78524-8_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-78524-8_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78523-1
Online ISBN: 978-3-540-78524-8
eBook Packages: Computer ScienceComputer Science (R0)