nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Cryptography in a Quantum World

verfasst von : Gilles Brassard

Erschienen in: SOFSEM 2016: Theory and Practice of Computer Science

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Although practised as an art and science for ages, cryptography had to wait until the mid-twentieth century before Claude Shannon gave it a strong mathematical foundation. However, Shannon’s approach was rooted is his own information theory, itself inspired by the classical physics of Newton and Einstein. But our world is ruled by the laws of quantum mechanics. When quantum-mechanical phenomena are taken into account, new vistas open up both for codemakers and codebreakers. Is quantum mechanics a blessing or a curse for the protection of privacy? As we shall see, the jury is still out!

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

Nächstes Kapitel Relating Sublinear Space Computability Among Graph Connectivity and Related Problems

Kahn, D.: The Codebreakers: the Comprehensive History of Secret Communication from Ancient Times to the Internet, 2nd revised edn. Scribner, New York (1996)

Singh, S.: The Code Book: the Science of Secrecy from Ancient Egypt to Quantum Cryptography. Anchor Books, New York (2000)

http://tumblr.radarq.net/post/16344039232/big-brother-is-watching-you-in-the-plaza-de-george. Accessed 8 October 2015

Hodges, A.: Alan Turing: the Enigma. Random House, London (2012)CrossRef

Rejewski, M.: How Polish mathematicians broke the Enigma cipher. Ann. Hist. Comput. 3(3), 213–234 (1981)CrossRef

Tyldum, M., Moore, G.: The imitation game (2014)

https://en.wikipedia.org/wiki/W._T._Tutte. Accessed 8 October 2015

Tutte, W.T.: FISH and I. http://www.usna.edu/Users/math/wdj/_files/documents/papers/cryptoday/tutte_fish.pdf. Transcript of a lecture given at the University of Waterloo, 19 June 1998

QCrypt2015. http://2015.qcrypt.net. Accessed 8 October 2015

10.

Poe, E.A.: A few words on secret writing. Graham’s Lady’s Gentleman’s Mag. XIX(1), 33–38 (1841)

11.

Poe, E.A.: The Gold-Bug. Philadelphia Dollar Newspaper, Philadelphia (1843)

12.

Rosenheim, S.J.: The Cryptographic Imagination: Secret Writing from Edgar Poe to the Internet. Johns Hopkins University Press, Baltimore (1997)

13.

Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27(3), 379–423 (1948)MATHMathSciNetCrossRef

14.

Shannon, C.E.: Communication theory of secrecy systems. Bell Syst. Tech. J. 28(4), 656–715 (1949)MATHMathSciNetCrossRef

15.

Colossus Computer. https://en.wikipedia.org/wiki/Colossus_computer. Accessed 8 October 2015

16.

Vernam, G.: Secret signaling system, U.S. Patent 1,310,719 (1919)

17.

Bellovin, S.M.: Frank Miller: inventor of the one-time pad. Cryptologia 35(3), 203–222 (2011)MATHCrossRef

18.

Moscow-Washington Hotline. https://en.wikipedia.org/wiki/Moscow-Washington_hotline. Accessed 8 October 2015

19.

James, D.: Ché Guevara: a Biography. Rowman & Littlefield, Lanham (1970)

20.

Merkle, R.C.: C.S. 244 project proposal. http://www.merkle.com/1974 (1974). Accessed 8 October 2015

21.

Merkle, R.C.: Secure communications over insecure channels. Commun. ACM 21(4), 294–299 (1978)CrossRef

22.

Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644–654 (1976)MATHMathSciNetCrossRef

23.

Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)MATHMathSciNetCrossRef

24.

Wayner, P.: British document outlines early encryption discovery. http://www.nytimes.com/library/cyber/week/122497encrypt.html (1997). Accessed 8 October 2015

25.

McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep. 42(44), 114–116 (1978)

26.

Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48(177), 203–209 (1987)MATHMathSciNetCrossRef

27.

Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)

28.

Feynman, R.P.: Simulating physics with computers. Int. J. Theor. Phys. 21(6/7), 467–488 (1982)MathSciNetCrossRef

29.

Feynman, R.P.: Quantum mechanical computers. Opt. News 11(2), 11–20 (1985)CrossRef

30.

Deutsch, D.: Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. London A 400, 97–117 (1985)MATHMathSciNetCrossRef

31.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MATHMathSciNetCrossRef

32.

Kitaev, A.Y.: Quantum measurements and the Abelian stabilizer problem. arXiv preprint quant-ph/9511026 (1995)

33.

Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.): Post-Quantum Cryptography. Springer Science & Business Media, Berlin (2009)MATH

34.

Bernstein, D.J., Lange, T.: Post-quantum cryptography. http://pqcrypto.org/. Accessed 8 October 2015

35.

Micciancio, D., Regev, O.: Lattice-based cryptography, pp. 147–191. In: [33] (2009)

36.

Wolchover, N.: A tricky path to quantum-safe encryption. Quanta Magazine. https://www.quantamagazine.org/20150908-quantum-safe-encryption/. Accessed 8 October 2015

37.

Campbell, P., Groves, M., Shepherd, D.: Soliloquy: a cautionary tale. https://docbox.etsi.org/Workshop/2014/201410_CRYPTO/S07_Systems_and_Attacks/S07_Groves_Annex.pdf. Accessed 8 October 2015

38.

Biasse, J.F., Song, F.: A note on the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in \(\mathbb{Q}(\zeta _{p^n})\). http://cacr.uwaterloo.ca/techreports/2015/cacr2015-12.pdf. Accessed 8 October 2015

39.

National Security Agency: Cryptography Today. https://www.nsa.gov/ia/programs/suiteb_cryptography/. Accessed 8 October 2015

40.

Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79(2), 325–328 (1997)CrossRef

41.

Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510–1523 (1997)MATHMathSciNetCrossRef

42.

Brassard, G., Salvail, L.: Quantum Merkle puzzles. In: Second International Conference on Quantum, Nano and Micro Technologies, pp. 76–79 (2008)

43.

Brassard, G., Høyer, P., Kalach, K., Kaplan, M., Laplante, S., Salvail, L.: Merkle puzzles in a quantum world. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 391–410. Springer, Heidelberg (2011)CrossRef

44.

Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschr. Phys. 46(4&5), 493–505 (1998)CrossRef

45.

Wootters, W.K., Żurek, W.H.: A single quantum cannot be cloned. Nature 299(5886), 802–803 (1982)CrossRef

46.

Wiesner, S.: Conjugate coding. ACM Sigact News 15(1), 78–88 (1983). Original manuscript written in 1968CrossRef

47.

Bennett, C.H., Brassard, G., Breidbart, S.: Quantum cryptography II: how to re-use a one-time pad safely even if P=NP. Nat. Comput. 13(4), 453–458 (2014). Original manuscript written in 1982MathSciNetCrossRef

48.

Bennett, C.H., Brassard, G.: Quantum cryptography and its application to provably secure key expansion, public-key distribution, and coin-tossing. In: Proceedings of IEEE International Symposium on Information Theory, p. 91, September 1983

49.

Bennett, C.H., Brassard, G.: Quantum cryptography: public key distribution and coin tossing. In: Proceedings of International Conference on Computers, Systems and Signal Processing, pp. 175–179, December 1984

50.

Bennett, C.H., Brassard, G.: Quantum cryptography: public key distribution and coin tossing. Theor. Comput. Sci. 560(Part 1), 7–11 (2014)MATHMathSciNetCrossRef

51.

Brassard, G.: Brief history of quantum cryptography: a personal perspective. In: Proceedings of IEEE Information Theory Workshop on Theory and Practice in Information Theoretic Security, pp. 19–23, October 2005. arxiv.org/abs/quant-ph/0604072

52.

Bennett, C.H., Bessette, F., Brassard, G., Salvail, L., Smolin, J.: Experimental quantum cryptography. J. Cryptology 5(1), 3–28 (1992)MATHCrossRef

53.

Mayers, D.: On the security of the quantum oblivious transfer and key distribution protocols. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 124–135. Springer, Heidelberg (1995)

54.

Renner, R., König, R.: Universally composable privacy amplification against quantum adversaries. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 407–425. Springer, Heidelberg (2005)CrossRef

55.

König, R., Renner, R., Bariska, A., Maurer, U.: Small accessible quantum information does not imply security. Phys. Rev. Lett. 98(14), 140502 (2007)CrossRef

56.

Renner, R., Gisin, N., Kraus, B.: Information-theoretic security proof for quantum-key-distribution protocols. Phys. Rev. A 72(1), 012332 (2005)CrossRef

57.

Bennett, C.H., Brassard, G., Ekert, A.K.: Quantum cryptography. Sci. Am. 267(4), 50–57 (1992)CrossRef

58.

ID Quantique. http://www.idquantique.com

59.

Fadilpašić, S.: China’s quantum communications network almost ready. http://www.itproportal.com/2015/08/31/chinas-quantum-communications-network-almost-ready/. Accessed 9 October 2015

60.

Gerhardt, I., Liu, Q., Lamas-Linares, A., Skaar, J., Kurtsiefer, C., Makarov, V.: Full-field implementation of a perfect eavesdropper on a quantum cryptography system. Nat. Commun. 2, 349 (2011)CrossRef

61.

Unruh, D.: Everlasting multi-party computation. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 380–397. Springer, Heidelberg (2013)CrossRef

62.

Ekert, A.K.: Quantum cryptography based on Bell’s theorem. Phys. Rev. Lett. 67(6), 661–663 (1991)MATHMathSciNetCrossRef

63.

Bennett, C.H., Brassard, G., Mermin, N.D.: Quantum cryptography without Bell’s theorem. Phys. Rev. Lett. 68(5), 557–559 (1992)MATHMathSciNetCrossRef

64.

Bell, J.S.: On the Einstein-Podolsky-Rosen paradox. Physics 1(3), 195–200 (1964)

65.

Einstein, A., Podolsky, B., Rosen, N.: Can quantum-mechanical description of physical reality be considered complete? Phys. Rev. 47(10), 777–780 (1935)MATHCrossRef

66.

Ekert, A., Renner, R.: The ultimate physical limits of privacy. Nature 507(7493), 443–447 (2014)CrossRef

67.

Hensen, B., Bernien, H., Dréau, A.E., Reiserer, A., Kalb, N., Blok, M.S., Ruitenberg, J., Vermeulen, R.F.L., Schouten, R.N., Abellán, C., Amaya, W., Pruneri, V., Mitchell, M.W., Markham, M., Twitchen, D.J., Elkouss, D., Wehner, S., Taminiau, T.H., Hanson, R.: Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres. Nature 526(7575), 682–686 (2015)CrossRef

68.

Johnston, H.: Physicists claim ‘loophole-free’ Bell-violation experiment. Physics World (2015). http://physicsworld.com/cws/article/news/2015/sep/02/physicists-claim-loophole-free-bell-violation-experiment

Titel: Cryptography in a Quantum World
verfasst von: Gilles Brassard
Verlag: Springer Berlin Heidelberg
Buch: SOFSEM 2016: Theory and Practice of Computer Science
Print ISBN: 978-3-662-49191-1

Electronic ISBN: 978-3-662-49192-8

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-49192-8_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"