Dagmar Bruss
Skip Abstract Section
Abstract
We survey some results in quantum cryptography. After a brief introduction to classical cryptography, we provide the quantum-mechanical background needed to present some fundamental protocols from quantum cryptography. In particular, we review quantum key distribution via the BB84 protocol and its security proof, as well as the related quantum bit commitment protocol and its proof of insecurity.
- Ajtai, M. and Dwork, C. 1997. A public-key cryptosystem with worst-case/average-case equivalence. In Proceedings of the 29th ACM Symposium on Theory of Computing. ACM, New York, 284--293. Google Scholar
Digital Library
- Allender, E. and Rubinstein, R. 1988. P-printable sets. SIAM J. Comput. 17, 6, 1193--1202. Google ScholarDigital Library
- Bechmann-Pasquinucci, H., and Gisin, N. 1999. Incoherent and coherent eavesdropping in the six-state protocol of quantum cryptography. Phys. Rev. A 59, 4238--4248.Google ScholarCross Ref
- Ben-Or, M., Horodecki, M., Leung, D., Mayers, D., and Oppenheim, J. 2005. The universal composable security of quantum key distribution. In Proceedings of the 2nd Theory of Cryptography Conference, J. Kilian, Ed. Lecture Notes in Computer Science, vol. 3378, Springer-Verlag, 386--406. Also available at http://arxiv.org/abs/quant-ph/0409078. Google ScholarDigital Library
- Bennett, C. 1992. Quantum cryptography using any two nonorthogonal states. Phys. Rev. Lett. 68, 3121--3124.Google ScholarCross Ref
- Bennett, C. and Brassard, G. 1984. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing. IEEE Computer Society Press, Los Alamitos, CA, 175--179.Google Scholar
- Bennett, C., Brassard, G., Crépeau, C., and Maurer, U. 1995. Generalized privacy amplification. IEEE Trans. Inf. Theory 41, 1915--1923.Google ScholarCross Ref
- Bennett, C., Brassard, G., and Mermin, D. 1992. Quantum cryptography without Bell's theorem. Phys. Rev. Lett. 68, 557--559.Google ScholarCross Ref
- Berman, L. 1977. Polynomial reducibilities and complete sets. Ph.D. dissertation, Cornell University, Ithaca, NY. Google ScholarDigital Library
- Beygelzimer, A., Hemaspaandra, L., Homan, C., and Rothe, J. 1999. One-way functions in worst-case cryptography: Algebraic and security properties are on the house. SIGACT News 30, 4 (Dec.), 25--40. Google ScholarDigital Library
- Bouwmeester, D., Ekert, A., and Zeilinger, A. 2000. The Physics of Quantum Information. Springer-Verlag, New York.Google Scholar
- Brassard, G. 1979. A note on the complexity of cryptography. IEEE Trans. Inf. Theory 25, 2, 232--233.Google ScholarDigital Library
- Brassard, G., Crépeau, C., Jozsa, R., and Langlois, D. 1993. A quantum bit commitment scheme provably unbreakable by both parties. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 362--371.Google Scholar
- Brassard, G., Fortune, S., and Hopcroft, J. 1978. A note on cryptography and NP ∩ coNP - P. Tech. Rep. TR-338, Department of Computer Science, Cornell University, Ithaca, NY. Apr. Google ScholarDigital Library
- Bruss, D. 1998. Optimal eavesdropping in quantum cryptography with six states. Phys. Rev. Lett. 81, 3018--3021.Google ScholarCross Ref
- Bruss, D. and Macchiavello, C. 2002. Optimal eavesdropping in cryptography with three-dimensional quantum states. Phys. Rev. Lett. 88, 127901(1)--127901(4).Google ScholarCross Ref
- Damgård, I., Fehr, S., Salvail, L., and Schaffner, C. 2005. Cryptography in the bounded quantum-storage model. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 449--458. Google ScholarDigital Library
- Diffie, W. and Hellman, M. 1976. New directions in cryptography. IEEE Trans. Inf. Theory IT-22, 6, 644--654.Google ScholarDigital Library
- Ekert, A. 1991. Quantum cryptography based on Bell's theorem. Phys. Rev. Lett. 67, 661--663.Google ScholarCross Ref
- ElGamal, T. 1985. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory IT-31, 4, 469--472.Google ScholarDigital Library
- Fellows, M. and Koblitz, N. 1992. Self-witnessing polynomial-time complexity and prime factorization. Des. Codes Crypt. 2, 3, 231--235. Google ScholarDigital Library
- Fenner, S., Fortnow, L., Naik, A., and Rogers, J. 2003. Inverting onto functions. Inf. Comput. 186, 1, 90--103. Google ScholarDigital Library
- Gisin, N., Ribordy, G., Tittel, W., and Zbinden, H. 2002. Quantum cryptography. Rev. Modern Phys. 74, 145--195.Google ScholarCross Ref
- Goldreich, O. 1997. Note on Levin's theory of average-case complexity. Tech. Rep. TR97-058, Electronic Colloquium on Computational Complexity. Nov.Google Scholar
- Grollmann, J. and Selman, A. 1988. Complexity measures for public-key cryptosystems. SIAM J. Comput. 17, 2, 309--335. Google ScholarDigital Library
- Hartmanis, J. and Hemachandra, L. 1991. One-way functions and the nonisomorphism of NP-complete sets. Theoret. Comput. Sci. 81, 1, 155--163. Google ScholarDigital Library
- Håstad, J., Impagliazzo, R., Levin, L., and Luby, M. 1999. A pseudorandom generator from any one-way function. SIAM J. Comput. 28, 4 (Aug.), 1364--1396. Google ScholarDigital Library
- Hemaspaandra, L., Pasanen, K., and Rothe, J. 2006. If P ≠ NP then some strongly noninvertible functions are invertible. Theoret. Comput. Sci. 362, 1--3, 54--62. Google ScholarDigital Library
- Hemaspaandra, L. and Rothe, J. 1999. Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory. J. Comput. Syst. Sci. 58, 3, 648--659. Google ScholarDigital Library
- Hemaspaandra, L. and Rothe, J. 2000. Characterizing the existence of one-way permutations. Theoret. Comput. Sci. 244, 1--2 (Aug.), 257--261. Google ScholarDigital Library
- Hemaspaandra, L., Rothe, J., and Saxena, A. 2005. Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for one-way functions in complexity theory. In Proceedings of the 9th Italian Conference on Theoretical Computer Science. Lecture Notes in Computer Science, vol. 3701. Springer-Verlag, New York, 265--279. Google ScholarDigital Library
- Hemaspaandra, L., Rothe, J., and Wechsung, G. 1997a. Easy sets and hard certificate schemes. Acta Inf. 34, 11 (Nov.), 859--879.Google ScholarCross Ref
- Hemaspaandra, L., Rothe, J., and Wechsung, G. 1997b. On sets with easy certificates and the existence of one-way permutations. In Proceedings of the 3rd Italian Conference on Algorithms and Complexity. Lecture Notes in Computer Science, vol. 1203. Springer-Verlag, New York, 264--275. Google ScholarDigital Library
- Homan, C. 2004. Tight lower bounds on the ambiguity of strong, total, associative, one-way functions. J. Comput. Syst. Sci. 68, 3, 657--674. Google ScholarDigital Library
- Homan, C. and Thakur, M. 2003. One-way permutations and self-witnessing languages. J. Comput. Syst. Sci. 67, 3, 608--622. Google ScholarDigital Library
- Huffman, W., and Pless, V. 2003. Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge, MA.Google Scholar
- Hwang, W. 2003. Quantum key distribution with high loss: Toward global secure communication. Phys. Rev. Lett. 91, 057901.Google ScholarCross Ref
- Inamori, H., Lütkenhaus, N., and Mayers, D. 2001. Unconditional security of practical quantum key distribution. Tech. Rep. quant-ph/0107017, Computing Research Repository (CoRR). Available on-line at http://arxiv.org/abs/quant-ph/0107017.Google Scholar
- Kawachi, A., Kobayashi, H., Koshiba, T., and Putra, R. 2005. Universal test for quantum one-way permutations. Theoret. Comput. Sci. 345, 370--385. Google ScholarDigital Library
- Kent, A. 1999. Unconditionally secure bit commitment. Phys. Rev. Lett. 83, 1447--1450.Google ScholarCross Ref
- Ko, K. 1985. On some natural complete operators. Theoret. Comput. Sci. 37, 1, 1--30.Google ScholarCross Ref
- König, R., Renner, R., Bariska, A., and Maurer, U. 2006. Locking of accessible information and implications for the security of quantum cryptography. Tech. Rep. quant-ph/0512021v2, Computing Research Repository (CoRR). Available on-line at http://arxiv.org/abs/quant-ph/0512021.Google Scholar
- Kurtsiefer, C., Zarda, P., Halder, M., Weinfurter, H., Gorman, P., Tapster, P., and Rarity, J. 2002. A step towards global key distribution. Nature 419, 450.Google ScholarCross Ref
- Levin, L. 1986. Average case complete problems. SIAM J. Comput. 15, 1, 285--286. Google ScholarDigital Library
- Lo, H. and Chau, H. 1997. Is quantum bit commitment really possible? Phys. Rev. Lett. 78, 3410--3413.Google ScholarCross Ref
- Lo, H. and Chau, H. 1999. Unconditional security of quantum key distribution over arbitrarily long distances. Science 283, 2050--2056.Google ScholarCross Ref
- Maurer, U. 1993. Secret key agreement by public discussion from common information. IEEE Trans. Inf. Theory 39, 733--742.Google ScholarDigital Library
- Maurer, U. and Wolf, S. 1999. The relationship between breaking the Diffie-Hellman protocol and computing discrete logarithms. SIAM J. Comput. 28, 5, 1689--1721. Google ScholarDigital Library
- May, A. 2004. Computing the RSA secret key is deterministic polynomial time equivalent to factoring. In Advances in Cryptology---CRYPTO '04. Lecture Notes in Computer Science, vol. 3152. Springer-Verlag, New York, 213--219.Google Scholar
- Mayers, D. 1995. The trouble with quantum bit commitment. Tech. Rep. quant-ph/9603015v3, Computing Research Repository (CoRR). Available on-line at http://arxiv.org/abs/quant-ph/9603015.Google Scholar
- Mayers, D. 1997. Unconditionally secure quantum bit commitment is impossible. Phys. Rev. Lett. 78, 3414--3417.Google ScholarCross Ref
- Nguyen, P. and Stern, J. 1998. Cryptanalysis of the Ajtai-Dwork cryptosystem. In Advances in Cryptology---CRYPTO '98. Lecture Notes in Computer Science, vol. 1462. Springer-Verlag, New York, 223--242. Google ScholarDigital Library
- Nielsen, M. and Chuang, I. 2000. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, MA. Google ScholarDigital Library
- Rabi, M. and Sherman, A. 1997. An observation on associative one-way functions in complexity theory. Inf. Proc. Lett. 64, 5, 239--244. Google ScholarDigital Library
- Rivest, R., Shamir, A., and Adleman, L. 1978. A method for obtaining digital signature and public-key cryptosystems. Commun. ACM 21, 2, 120--126. Google ScholarDigital Library
- Rothe, J. 2005. Complexity Theory and Cryptology. An Introduction to Cryptocomplexity. EATCS Texts in Theoret. Comput. Sci. Springer-Verlag, Berlin, Heidelberg, New York. Google ScholarDigital Library
- Rothe, J. and Hemaspaandra, L. 2002. On characterizing the existence of partial one-way permutations. Inf. Proc. Lett. 82, 3 (May), 165--171.Google ScholarCross Ref
- Scarani, V., Acín, A., Ribordy, G., and Gisin, N. 2004. Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulse implementations. Phys. Rev. Lett. 92, 057901(1)--057901(4).Google ScholarCross Ref
- Schrödinger, E. 1935. Die gegenwärtige Situation in der Quantenmechanik. Die Naturwissenschaften 23, 807--812, 823--828, 844--849.Google ScholarCross Ref
- Selman, A. 1992. A survey of one-way functions in complexity theory. Math. Syst. Theory 25, 3, 203--221.Google ScholarCross Ref
- Shannon, C. 1949. Communication theory of secrecy systems. Bell Syst. Tech. J. 28, 4, 657--715.Google ScholarCross Ref
- Shor, P. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 5, 1484--1509. Google ScholarDigital Library
- Shor, P. and Preskill, J. 2000. Simple proof of security of the BB84 quantum key distribution protocol. Phys. Rev. Lett. 85, 441--444.Google ScholarCross Ref
- Singh, S. 1999. The Code Book. The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Fourth Estate, London, England.Google Scholar
- Stinson, D. 2005. Cryptography: Theory and Practice, Third ed. CRC Press, Boca Raton, FL. Google ScholarCross Ref
- Wang, J. 1997. Average-case computational complexity theory. In Complexity Theory Retrospective II, L. Hemaspaandra and A. Selman, Eds. Springer-Verlag, New York, 295--328. Google ScholarDigital Library
- Watanabe, O. 1988. On hardness of one-way functions. Inf. Proc. Lett. 27, 3, 151--157. Google ScholarDigital Library
- Werner, R. 1989. Quantum states with Einstein--Podolsky--Rosen correlations admitting a hidden-variable model. Phys. Rev. A 40, 8 (Oct.), 4277--4281.Google ScholarCross Ref
- Wiesner, S. 1983. Conjugate coding. SIGACT News 15, 78--88. Google ScholarDigital Library
- Wootters, W. K., and Zurek, W. H. 1982. A single quantum cannot be cloned. Nature 299, 802--803.Google ScholarCross Ref
- Yao, A. 1995. Security of quantum protocols against coherent measurements. In Proceedings of the 27th ACM Symposium on Theory of Computing. ACM, New York, 67--75. Google ScholarDigital Library
Index Terms
- Quantum cryptography: A survey
Recommendations
Simplified quantum bit commitment using single photon nonlocality
We simplified our previously proposed quantum bit commitment (QBC) protocol based on the Mach---Zehnder interferometer, by replacing symmetric beam splitters with asymmetric ones. It eliminates the need for random sending time of the photons; thus, the ...
Coherent state quantum key distribution based on entanglement sudden death
A method for quantum key distribution (QKD) using entangled coherent states is discussed which is designed to provide key distribution rates and transmission distances surpassing those of traditional entangled photon pair QKD by exploiting entanglement ...
Quantum bit commitment on IBM QX
AbstractQuantum bit commitment (QBC) is a quantum version of the classical bit commitment security primitive. As other quantum security primitives and protocols, QBC improves on cheating detection over its classical counterpart. The implementation of the ...
Reviews
Adrian Constantin Atanasiu
Despite its title, this survey develops only two applications of cryptographic protocols in quantum computing: key distribution and bit commitment protocol, both of which relate to the BB84 protocol proposed in 1984 by Bennett and Brassard [1]. The first section is an introduction. Section 2 describes the fundamentals of classical cryptography, including easy examples. Section 3 provides some background on quantum mechanics. In section 4, the BB84 quantum key distribution protocol is presented and its security is discussed; in particular, the authors describe an entanglement-based version of BB84 (akin to Ekert’s protocol), providing a proof of its security (devised by Shor and Preskill) and showing that it is equivalent to the prepare-and-measure version of the classical BB84 protocol. Section 5 presents the BB84 quantum bit commitment protocol, based on the ideas of Bennett and Brassard, and shows that the security of unconditional quantum bit commitment is impossible. A brief outlook and some conclusions are provided in section 6. The first two sections have many unnecessary details like the scytale encryption method and a definition of cryptosystems, and ignore some notions related to coding theory that are used later in the paper. However, the two main sections of the paper, 4 and 5, are interesting and offer fine information about some of the stages of such quantum cryptographic protocols. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments