Abstract
The concept of zero-knowledge (ZK) has become of fundamental importance in cryptography. However, in a setting where entities are modeled by quantum computers, classical arguments for proving ZK fail to hold since, in the quantum setting, the concept of rewinding is not generally applicable. Moreover, known classical techniques that avoid rewinding have various shortcomings in the quantum setting.
We propose new techniques for building quantum zero-knowledge (QZK) protocols, which remain secure even under (active) quantum attacks. We obtain computational QZK proofs and perfect QZK arguments for any NP language in the common reference string model. This is based on a general method converting an important class of classical honest-verifier ZK (HVZK) proofs into QZK proofs. This leads to quite practical protocols if the underlying HVZK proof is efficient. These are the first proof protocols enjoying these properties, in particular the first to achieve perfect QZK.
As part of our construction, we propose a general framework for building unconditionally hiding (trapdoor) string commitment schemes, secure against quantum attacks, as well as concrete instantiations based on specific (believed to be) hard problems. This is of independent interest, as these are the first unconditionally hiding string commitment schemes withstanding quantum attacks.
Finally, we give a partial answer to the question whether QZK is possible in the plain model. We propose a new notion of QZK, non-oblivious verifier QZK, which is strictly stronger than honest-verifier QZK but weaker than full QZK, and we show that this notion can be achieved by means of efficient (quantum) protocols.
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
Barak, B.: How to Go Beyond the Black-box Simulation Barrier. In: 42th Annual Symposium on Foundations of Computer Science (FOCS) (2001)
Brassard, G., Crépeau, C.: Zero-Knowledge Simulation for Boolean Circuits. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 223–233. Springer, Heidelberg (1987)
Brassard, G., Chaum, D., Crépeau, C.: Minimum Disclosure Proofs of Knowledge. JCSS 37(2) (1988)
Blum, M., Feldman, P., Micali, S.: Non-Interactive Zero-Knowledge and Its Applications. In: 20th Annual Symposium on Theory Of Computing (STOC) (1988)
Canetti, R.: Universally Composable Security: A New Paradigm for Cryptographic Protocols. In: 42th Annual Symposium on Foundations of Computer Science (FOCS) (2001)
Canetti, R., Fischlin, M.: Universally Composable Commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 19. Springer, Heidelberg (2001)
Cramer, R., Damgård, I., Schoenmakers, B.: Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174–187. Springer, Heidelberg (1994)
Crépeau, C., Dumais, P., Mayers, D., Salvail, L.: Computational Collapse of Quantum State with Application to Oblivious Transfer. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 374–393. Springer, Heidelberg (2004)
Damgård, I.: Efficient Concurrent Zero-Knowledge in the Auxiliary String Model. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, p. 418. Springer, Heidelberg (2000)
Damgård, I., Fehr, S., Salvail, L.: Zero-Knowledge Proofs and String Commitments Withstanding Quantum Attacks, full version of this paper, BRICS report nr. RS-04-9 (2004), available at http://www.brics.dk/RS/04/9
Damgård, I., Nielsen, J.: Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, p. 581. Springer, Heidelberg (2002)
Dumais, P., Mayers, D., Salvail, L.: Perfectly Concealing Quantum Bit Commitment From Any Quantum One-Way Permutation. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, p. 300. Springer, Heidelberg (2000)
Dwork, C., Naor, M., Sahai, A.: Concurrent Zero-Knowledge, in 30th Annual Symposium on Theory Of Computing (STOC) (1998)
Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive Proof Systems, in 17th Annual Symposium on Theory Of Computing (STOC) (1985)
Goldreich, O., Micali, S., Wigderson, A.: Proofs that Yield Nothing but their Validity, or All Languages in NP Have Zero-Knowledge Proof Systems. J. ACM., 38(3) (1991)
Fiat, A., Shamir, A.: How to Prove Yourself: Practical Solutions to the Identification and Signature Problem. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Kitaev, A., Watrous, J.: Parallelization, Amplification, and Exponential Time Simulation of Quantum Interactive Proof Systems. In: 32nd Annual Symposium on Theory of Computing (STOC) (2000)
Maassen, H., Uffink, J.B.M.: Generalized Entropic Uncertainty Relations. Phys. Rev. Letters 60 (1988)
Micciancio, D., Vadhan, S.P.: Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 282–298. Springer, Heidelberg (2003)
Naor, M.: Bit Commitment Using Pseudorandomness. Journal of Cryptology 4(2) (1991)
Pfitzmann, B., Waidner, M.: Composition and Integrity Preservation of Secure Reactive Systems. In: 7th ACM Conference on Computer and Communications Security (2000)
Richardson, R., Kilian, J.: On the Concurrent Composition of Zero- Knowledge Proofs. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 415. Springer, Heidelberg (1999)
Shor, P.: Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In: 35th Annual Symposium on Foundations of Computer Science (FOCS) (1994)
Watrous, J.: PSPACE has Constant-Round Quantum Interactive Proof Systems. In: 40th Annual Symposium on Foundations of Computer Science (FOCS) (1999)
Watrous, J.: Succinct Quantum Proofs for Properties of Finite Groups. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science (2000)
Watrous, J.: Limits on the Power of Quantum Statistical Zero-Knowledge. In: 43rd Annual Symposium on the Foundations of Computer Science (FOCS) (2002)
van de Graaf, J.: Towards a Formal Definition of Security for Quantum Protocols, Ph.D. thesis, Computer Science and Operational Research Department, Université de Montréal (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Damgård, I., Fehr, S., Salvail, L. (2004). Zero-Knowledge Proofs and String Commitments Withstanding Quantum Attacks. In: Franklin, M. (eds) Advances in Cryptology – CRYPTO 2004. CRYPTO 2004. Lecture Notes in Computer Science, vol 3152. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28628-8_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-28628-8_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22668-0
Online ISBN: 978-3-540-28628-8
eBook Packages: Springer Book Archive