Article

General properties of quantum zero-knowledge proofs

Author:

Hirotada KobayashiAuthors Info & Claims

TCC'08: Proceedings of the 5th conference on Theory of cryptography

Pages 107 - 124

Published: 19 March 2008 Publication History

Abstract

This paper studies general properties of quantum zeroknowledge 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 zeroknowledge. - 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 zeroknowledge proofs. The corresponding properties are not known to hold in the classical perfect zero-knowledge case.

References

[1]

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).

Digital Library

[2]

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).

Digital Library

[3]

Ben-Aroya, A., Ta-Shma, A.: Quantum expanders and the quantum entropy difference problem. arXiv.org e-Print archive, quant-ph/0702129 (2007).

[4]

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).

[5]

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).

Digital Library

[6]

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).

Digital Library

[7]

Goldreich, O.: Foundations of Cryptography - Volume 1 Basic Tools. Cambridge University Press, Cambridge (2001).

Digital Library

[8]

Goldreich, O.: Zero-knowledge twenty years after its invention. Electronic Colloquium on Computational Complexity, Report No. 63 (2002).

Digital Library

[9]

Goldreich, O., Goldwasser, S.: On the limits of nonapproximability of lattice problems. Journal of Computer and System Sciences 60(3), 540-563 (2000).

Digital Library

[10]

Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM 38(3), 691-729 (1991).

Digital Library

[11]

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).

Digital Library

[12]

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).

Digital Library

[13]

Goldwasser, S., Micali, S., Rackoff, C.W.: The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18(1), 186-208 (1989).

Digital Library

[14]

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).

Digital Library

[15]

Kitaev, A.Yu., Shen, A.H., Vyalyi, M.N.: Classical and Quantum Computation. Graduate Studies in Mathematics, vol. 47. American Mathematical Society (2002).

Digital Library

[16]

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).

Digital Library

[17]

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).

[18]

Kobayashi, H.: General properties of quantum zero-knowledge proofs. arXiv.org e-Print archive, arXiv:0705.1129 {quant-ph} (2007).

[19]

Marriott, C., Watrous, J.H.: Quantum Arthur-Merlin games. Computational Complexity 14(2), 122-152 (2005).

Digital Library

[20]

Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000).

Digital Library

[21]

Okamoto, T.: On relationships between statistical zero-knowledge proofs. Journal of Computer and System Sciences 60(1), 47-108 (2000).

Digital Library

[22]

Sahai, A., Vadhan, S.P.: A complete problem for statistical zero knowledge. Journal of the ACM 50(2), 196-249 (2003).

Digital Library

[23]

Shor, P.W.: Fault-tolerant quantum computation. In: 37th Annual Symposium on Foundations of Computer Science, pp. 56-65 (1996).

Digital Library

[24]

Vadhan, S.P.: An unconditional study of computational zero-knowledge. SIAM Journal on Computing 36(4), 1160-1214 (2006).

Digital Library

[25]

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).

Digital Library

[26]

Watrous, J.H.: PSPACE has constant-round quantum interactive proof systems. Theoretical Computer Science 292(3), 575-588 (2003).

Digital Library

[27]

Watrous, J.H.: Zero-knowledge against quantum attacks. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 296-305 (2006).

Digital Library

Cited By

Chiesa AForbes MGur TSpooner N(2022)Spatial Isolation Implies Zero Knowledge Even in a Quantum WorldJournal of the ACM10.1145/351110069:2(1-44)Online publication date: 31-Jan-2022
https://dl.acm.org/doi/10.1145/3511100
Shang TChen RLiu J(2019)On the obfuscatability of quantum point functionsQuantum Information Processing10.1007/s11128-019-2172-218:2(1-16)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s11128-019-2172-2
Yan J(2012)Complete problem for perfect zero-knowledge quantum proofProceedings of the 38th international conference on Current Trends in Theory and Practice of Computer Science10.1007/978-3-642-27660-6_34(419-430)Online publication date: 21-Jan-2012
https://dl.acm.org/doi/10.1007/978-3-642-27660-6_34
Show More Cited By

General properties of quantum zero-knowledge proofs
1. Theory of computation
  1. Computational complexity and cryptography
  2. Logic

Recommendations

On Relationships between Statistical Zero-Knowledge Proofs

This paper solves several fundamental open problems about statistical zero-knowledge interactive proofs (SZKIPs). The following two theorems are proven: If language L has a statistical zero-knowledge interactive proof against an honest verifier, then L ...
Quantum protocols for zero-knowledge systems

Zero-knowledge proof system is an important protocol that can be used as a basic block for construction of other more complex cryptographic protocols. An intrinsic characteristic of a zero-knowledge systems is the assumption that is impossible for the ...
Oblivious Transfer from Zero-Knowledge Proofs: Or How to Achieve Round-Optimal Quantum Oblivious Transfer and Zero-Knowledge Proofs on Quantum States
Advances in Cryptology – ASIACRYPT 2023
Abstract
We provide a generic construction to turn any classical Zero-Knowledge (ZK) protocol into a composable (quantum) oblivious transfer (OT) protocol, mostly lifting the round-complexity properties and security guarantees (plain-model/statistical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

TCC'08: Proceedings of the 5th conference on Theory of cryptography

March 2008

644 pages

ISBN:354078523X

Editor:
Ran Canetti
IBM T.J. Watson Research Center, NY

Sponsors

Microsoft Inc.
IBM Inc.
The D. E. Shaw group
IACR: International Association for Cryptologic Research

In-Cooperation

New York University
Courant Institute for Mathematical Sciences

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 19 March 2008

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
2
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chiesa AForbes MGur TSpooner N(2022)Spatial Isolation Implies Zero Knowledge Even in a Quantum WorldJournal of the ACM10.1145/351110069:2(1-44)Online publication date: 31-Jan-2022
https://dl.acm.org/doi/10.1145/3511100
Shang TChen RLiu J(2019)On the obfuscatability of quantum point functionsQuantum Information Processing10.1007/s11128-019-2172-218:2(1-16)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s11128-019-2172-2
Yan J(2012)Complete problem for perfect zero-knowledge quantum proofProceedings of the 38th international conference on Current Trends in Theory and Practice of Computer Science10.1007/978-3-642-27660-6_34(419-430)Online publication date: 21-Jan-2012
https://dl.acm.org/doi/10.1007/978-3-642-27660-6_34
Jain RJi ZUpadhyay SWatrous J(2011)QIP = PSPACEJournal of the ACM10.1145/2049697.204970458:6(1-27)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1145/2049697.2049704
Jain RJi ZUpadhyay SWatrous JMitzenmacher MSchulman L(2010)QIP = PSPACEProceedings of the forty-second ACM symposium on Theory of computing10.1145/1806689.1806768(573-582)Online publication date: 5-Jun-2010
https://dl.acm.org/doi/10.1145/1806689.1806768
Hallgren SKolla ASen PZhang S(2008)Making Classical Honest Verifier Zero Knowledge Protocols Secure against Quantum AttacksProceedings of the 35th international colloquium on Automata, Languages and Programming, Part II10.1007/978-3-540-70583-3_48(592-603)Online publication date: 7-Jul-2008
https://dl.acm.org/doi/10.1007/978-3-540-70583-3_48

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents