Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Basic Concepts of Cellular Automata Kapitel lesen Erstes Kapitel lesen

2012 | OriginalPaper | Buchkapitel

Quantum Cryptography

verfasst von : Takeshi Koshiba

Erschienen in: Handbook of Natural Computing

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Several results in quantum cryptography will be surveyed in this chapter. After a brief introduction to classical cryptography, we provide some cryptographic primitives from the viewpoint of quantum computational complexity theory, which are helpful to get an idea of quantum cryptographic protocols. We then examine cryptographic protocols of quantum key distribution, quantum bit commitment, quantum oblivious transfer, quantum zero-knowledge, quantum public-key encryption, quantum digital signature, and their security issues.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Physical Implementation of Large-Scale Quantum Computation
Nächstes Kapitel BQP-Complete Problems
Literatur
Adcock M, Cleve R (2002) A quantum Goldreich-Levin theorem with cryptographic applications. In: Proceedings of the 19th annual symposium on theoretical aspects of computer science, Antibes-Juan les Pins, France, March 2002. Lecture notes in computer science, vol 2285. Springer, Berlin, pp 323–334
Aharonov D, Ta-Shma A, Vazirani UV, Yao AC-C (2000) Quantum bit escrow. In: Proceedings of the 32nd ACM symposium on theory of computing, ACM, Portland, OR, May 2000, pp 705–714
Bellare M, Rogaway P (1995) Optimal asymmetric encryption. In: EUROCRYPT '94: Advances in cryptology, Perugia, Italy, May 1994. Lecture notes in computer science, vol 950. Springer, Berlin, pp 92–111
Bennett CH, Brassard G (1984) Quantum cryptography: public key distribution and coin tossing. In: Proceeding of the IEEE international conference on computers, systems, and signal processing, Bangalore, India, December 1984. IEEE, New York, pp 175–179
Brassard G, Chaum D, Crépeau C (1988) Minimum disclosure proofs of knowledge. J Comput Syst Sci 37(2):156–189CrossRefMATH
Brassard G, Crépeau C, Santha M (1996) Oblivious transfers and intersecting codes. IEEE Trans Info Theory 42(6):1769–1780CrossRefMATH
Brassard G, Crépeau C, Wolf S (2003) Oblivious transfers and privacy amplification. J Cryptol 16(4):219–237CrossRefMATH
Buhrman H, Cleve R, Watrous J, de Wolf R (2001) Quantum fingerprinting. Phys Rev Lett 87:167902CrossRef
Buhrman H, Christandl M, Hayden P, Lo H-K, Wehner S (2008) Possibility, impossibility and cheat-sensitivity of quantum bit string commitment. Phys Rev A 78(32):022316CrossRef
Chor B, Rivest RL (1988) A knapsack-type public key cryptosystems based on arithmetic in finite fields. IEEE Trans Info Theory 34:901–909MathSciNetCrossRef
Cramer R, Shoup V (2003) Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J Comput 33(1):167–226MathSciNetCrossRefMATH
Crépeau C (1988) Equivalence between two flavours of oblivious transfer. In: CRYPTO'87: Advances in cryptology, University of California, Santa Barbara, CA, August 1987. Lecture notes in computer science, vol 293. Springer, New York, pp 350–354
Crépeau C, Kilian J (1988) Achieving oblivious transfer using weakened security assumptions. In: Proceedings of the 29th annual IEEE symposium on foundations of computer science, IEEE, White Plains, NY, October 1988, pp 42–52
Crépeau C, Savvides G (2006) Optimal reductions between oblivious transfers using interactive hashing. In: EUROCRYPT 2006: Advances in cryptology, St. Petersburg, Russia, May–June 2006. Lecture notes in computer science vol 4004. Springer, Heidelberg, pp 201–221
Crépeau C, Legare F, Salvail L (2001) How to convert the flavor of a quantum bit commitment. In: EUROCRYPT 2001: Advances in cryptology, Innsbruck, Austria, May 2001. Lecture notes in computer science vol 2045. Springer, Berlin, pp 60–77
Crépeau C, Dumais P, Mayers D, Salvail L (2004) Computational collapse of quantum state with application to oblivious transfer. In: Proceedings of the 1st theory of cryptography conference, Cambridge, MA, February 2004. Lecture notes in computer science, vol 2951. Springer, Berlin, pp 374–393
Damgård I (1988) On the randomness of Legendre and Jacobi sequences. In: CRYPTO'88: Advances in cryptology, Santa Barbara, CA, August 1988. Lecture notes in computer science vol 403. Springer, Berlin, pp 163–172
Damgård I, Fehr S, Salvail L (2004) Zero-knowledge proofs and string commitments withstanding quantum attacks. In: CRYPTO 2004: Advances in cryptology, Santa Barbara, CA, August 2004. Lecture notes in computer science, vol 3152. Springer, Berlin, pp 254–272
Dumais P, Mayers D, Salvail L (2000) Perfectly concealing quantum bit commitment from any quantum one-way permutation. In: EUROCRYPT 2000: Advances in cryptology, Bruges, Belgium, May 2000. Lecture notes in computer science, vol 1807. Springer, Berlin, pp 300–315
Goldreich O, Levin LA (1989) A hard-core predicate for all one-way functions. In: Proceedings of the 21st ACM symposium on theory of computing, ACM, Seattle, WA, May 1989, pp 25–32
Goldreich O, Micali S, Wigderson A (1987) How to play any mental game or a completeness theorem for protocols with honest majority. In: Proceedings of the 19th ACM symposium on theory of computing, ACM, New York, May 1987, pp 218–229
Goldreich O, Micali S, Wigderson A (1991) Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. J Assoc Comput Mach 38(3):691–729MathSciNetCrossRefMATH
Goldwasser S, Micali S, Rackoff C (1989) The knowledge complexity of interactive proof systems. SIAM J Comput 18(1):186–208MathSciNetCrossRefMATH
Goldreich O, Sahai A, Vadhan S (1999) Can statistical zero knowledge be made non-interactive? Or on the relationship of SZK and NISZK. In: CRYPTO 1999: Advances in cryptology, Santa Barbara, CA, August 1999. Lecture notes in computer science, vol 1666. Springer, Berlin, pp 467–484
Gottesman D, Chuang I (2001) Quantum digital signatures. Available via ArXiv:quant-ph/0103032v2
Grigni M, Schulman LJ, Vazirani M, Vazirani UV (2004) Quantum mechanical algorithms for the nonabelian hidden subgroup problem. Combinatorica 24(1):137–154MathSciNetCrossRefMATH
Haitner I, Reingold O (2007) Statistically-hiding commitment from any one-way function. In: Proceedings of the 39th ACM symposiom on theory of computing, San Diego, CA, June 2007, pp 1–10
Haitner I, Horvitz O, Katz J, Koo C-Y, Morselli R, Shaltiel R (2005) Reducing complexity assumptions for statistically-hiding commitment. In: EUROCRYPT 2005: Advances in cryptology, Aarhus, Denmark, May 2005. Lecture notes in computer science, vol 3494. Springer, Berlin, pp 58–77
Hallgren S, Russell A, Ta-Shma A (2003) The hidden subgroup problem and quantum computation using group representations. SIAM J Comput 32(4):916–934MathSciNetCrossRefMATH
Hallgren S, Moore C, Rötteler M, Russell A, Sen P (2006) Limitations of quantum coset states for graph isomorphism. In: Proceedings of the 38th ACM symposium on theory of computing, ACM, Seattle, WA, May 2006, pp 604–617
Hardy L, Kent A (2004) Cheat sensitive quantum bit commitment. Phys Rev Lett 92(15):157901CrossRef
Håstad J, Impagliazzo R, Levin LA, Luby M (1999) A pseudorandom generator from any one-way function. SIAM J Comput 28(4):1364–1396MathSciNetCrossRefMATH
Hayashi M, Kawachi A, Kobayashi H (2008) Quantum measurements for hidden subgroup problems with optimal sample complexity. Quantum Info Comput 8:345–358MathSciNetMATH
Kashefi E, Nishimura H, Vedral V (2002) On quantum one-way permutations. Quantum Info Comput 2(5):379–398MathSciNetMATH
Kawachi A, Yamakami T (2006) Quantum hardcore functions by complexity-theoretical quantum list decoding. In: Proceedings of the 33rd international colloquium on automata, languages and programming, Venice, Italy, July 2006. Lecture notes in computer science, vol 4052. Springer, Berlin, pp 216–227
Kawachi A, Koshiba T, Nishimura H, Yamakami T (2005a) Computational indistinguishability between quantum states and its cryptographic application. In: EUROCRYPT 2005: Advances in cryptology, Aarhus, Denmark, May 2005. Lecture notes in computer science, vol 3494. Springer, Berlin, pp 268–284
Kawachi A, Kobayashi H, Koshiba T, Putra RRH (2005b) Universal test for quantum one-way permutations. Theor Comput Sci 345(2–3):370–385MathSciNetCrossRefMATH
Kempe J, Pyber L, Shalev A (2007) Permutation groups, minimal degrees and quantum computing. Groups Geometry Dyn 1(4):553–584MathSciNetCrossRefMATH
Kent A (2003) Quantum bit string commitment. Phys Rev Lett 90(23):237901CrossRef
Kilian J (1988) Founding cryptography on oblivious transfer. In: Proceedings of the 20th ACM symposium on theory of computing, ACM, Chicago, IL, May 1988, pp 20–31
Koashi M, Preskill J (2003) Secure quantum key distribution with an uncharacterized source. Phys Rev Lett 90:057902CrossRef
Kobayashi H (2003) Non-interactive quantum perfect and statistical zero-knowledge. In: Proceedings of the 14th international symposium on algorithms and computation, Kyoto, Japan, December 2003. Lecture notes in computer science, vol 2906. Springer, Berlin, pp 178–188
Kobayashi H (2008) General properties of quantum zero-knowledge proofs. In: Proceedings of the 5th theory of cryptography conference, New York, March 2008. Lecture notes in computer science, vol 4948. Springer, New York, pp 107–124
Koshiba T, Odaira T (2009) Statistically-hiding quantum bit commitment from approximable-preimage-size quantum one-way function. In: Proceedings of the 4th workshop on theory of quantum computation, communication and cryptography, Waterloo, ON, Canada, May 2009. Lecture notes in computer science, vol 5906. Springer, Berlin, pp 33–46
Lamport L (1979) Constructing digital signatures from a one-way function. Technical Report CSL-98, SRI International
Lo H-K, Chau HF (1997) Is quantum bit commitment really possible? Phys Rev Lett 78(17):3410–3413CrossRef
Marriott C, Watrous J (2004) Quantum Arthur-Merlin games. In: Proceedings of the 19th IEEE conference on computational complexity, IEEE, Amherst, MA, June 2004, pp 275–285
Mayers D (1996) Quantum key distribution and string oblivious transfer in noisy channels. In: CRYPTO'96: Advances in cryptology, Santa Barbara, CA, August 1996. Lecture notes in computer science, vol 1109. Springer, Berlin, pp 343–357
Mayers D (1997) Unconditionally secure quantum bit commitment is impossible. Phys Rev Lett 78(17):3414–3417CrossRef
Mayers D, Salvail L (1994) Quantum oblivious transfer is secure against all individual measurements. In: Proceedings of workshop on physics and computation, IEEE, Dallas, TX, November 1994, pp 69–77
Micciancio D, Regev O (2009) Lattice-based cryptography. In Bernstein DJ, Buchmann J, Dahmen E (eds) Post-quantum cryptography. Springer, Berlin, pp 147–191CrossRef
Naor M, Yung M (1989) Universal one-way hash functions and their cryptographic applications. In: Proceedings of the 21st ACM symposium on theory of computing, ACM, Seattle, WA, May 1989, pp 33–43
Naor M, Ostrovsky R, Venkatesan R, Yung M (1998) Perfect zero-knowledge arguments for NP using any one-way permutation. J Cryptol 11(2):87–108MathSciNetCrossRefMATH
Nguyen M-H, Ong S-J, Vadhan SP (2006) Statistical zero-knowledge arguments for NP from any one-way function. In: Proceedings of the 47th IEEE symposium on foundations of computer science, IEEE, Berkeley, CA, October 2006, pp 3–14
Nguyen PQ, Stern J (2005) Adapting density attacks to low-weight knapsacks. In: ASIACRYPT 2005: Advances in cryptology, Chennai, India, December 2005. Lecture notes in computer science, vol 3788. Springer, Berlin, pp 41–58
Okamoto T, Tanaka K, Uchiyama S (2000) Quantum public-key cryptosystems. In: CRYPTO 2000: Advances in cryptology, Santa Barbara, CA, August 2000. Lecture notes in computer science, vol 1880. Springer, Berlin, pp 147–165
Rabin M (1981) How to exchange secrets by oblivious transfer. Technical Report TR-81, Aiken Computation Laboratory, Harvard University
Rivest RL, Shamir A, Adleman L (1978) A method for obtaining digital signature and public key cryptosystems. Commun ACM 21(2):120–126MathSciNetCrossRefMATH
Shor PW (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput 26(5):1484–1509MathSciNetCrossRefMATH
Shor PW, Preskill J (2000) Simple proof of security of the BB84 quantum key distribution protocol. Phys Rev Lett 85:441–444CrossRef
Sudan M (2000) List decoding: algorithms and applications. SIGACT News 31(1):16–27CrossRef
van de Graaf J (1997) Towards a formal definition of security for quantum protocols. PhD thesis, Université de Montréal
Watrous J (2002) Limits on the power of quantum statistical zero-knowledge. In: Proceedings of the 43rd IEEE symposium on foundations of computer science, IEEE, Vancouver, BC, Canada, November 2002, pp 459–470
Watrous J (2006) Zero-knowledge against quantum attacks. In: Proceedings of the 38th annual ACM symposium on theory of computing, ACM, Seattle, WA, May 2006, pp 296–305
Wegman MN, Carter JL (1981) New hash functions and their use in authentication and set equality. J Comput Syst Sci 22(3):265–279MathSciNetCrossRefMATH
Yao AC-C (1995) Security of quantum protocols against coherent measurements. In: Proceedings of the 27th annual ACM symposium on theory of computing, ACM, Las Vegas, NV, May–June 1995, pp 67–75
Metadaten
Titel
Quantum Cryptography
verfasst von
Takeshi Koshiba
Copyright-Jahr
2012
Verlag
Springer Berlin Heidelberg
Buch
Handbook of Natural Computing

Print ISBN: 978-3-540-92909-3

Electronic ISBN: 978-3-540-92910-9

Copyright-Jahr: 2012

DOI
https://doi.org/10.1007/978-3-540-92910-9_45