Quantum Cryptography: Quantum Cryptography CIS 5371 Cryptography Fall 2005 John Russell Ross Kim


Overview: Overview


Overview (cont.): Overview (cont.) Problems Conventional Cryptography Quantum Cryptography Mechanism BB84 Protocol Quantum Cryptography History Questions


Background & Related Work: Background & Related Work Lomonaco, Samuel J. Jr., “A Talk on Quantum Cryptography or How Alice Outwits Eve”, AMS PSAPM, vol 58, (2002), 237 - 264. Mullins, Justin, "Making Unbreakable Code", IEEE Spectrum, May 2002. Lo, Hoi-Kwong and Tamaki, Kiyoshi, "Quantum Key Distribution: Beyond No-Cloning Theorem", University of Toronto, Toronto, Ontario, M5S 3G4, CANADA.


Problems: Problems Secure means of communicating key Authentication Intrusion Detection


Conventional Cryptography: Conventional Cryptography Classical Cryptographic Practical Secrecy Caesar Cipher German Enigma Machine Digital Encryption Standard (DES) Advanced Encryption Standard (AES)


Conventional Cryptography: Conventional Cryptography WW2 German Enigma Machine 10 million billion possible combinations! Allied code-breaking machine bombe Enigma Broken!


Conventional Cryptography (cont.): Conventional Cryptography (cont.) Perfect Secrecy Prob[C|P] = Prob[P] Vernam Cipher as known as One-Time-Pad C1 = b1 XOR k1 + b2 XOR k2 + … + bn XOR kn C2 = b1 XOR k1 + b2 XOR k2 + … + bn XOR kn C1 XOR C2 = P1 XOR P2


Conventional Cryptography (cont.): Conventional Cryptography (cont.) Problems: Brute Force Attack Secure means of communicating key - NO Authentication - NO Intrusion Detection - NO


Conventional Cryptography (cont.): Conventional Cryptography (cont.) Computationally Security Diffie Hellman (RSA / PGP) if( #_of_bits_require > #_of_atoms_in_unverse ) else if( computational_time > age_of_unverse )


Conventional Cryptography (cont.): Conventional Cryptography (cont.) Problems: Man-In-The-Middle Attack Secure means of communicating key - MAYBE Authentication - YES Intrusion Detection - NO


Quantum Cryptography Mechanism: Quantum Cryptography Mechanism Quantum Bit (Qubit) 1 or 0 Quantum Basis vertical polarized state | = 1 horizontal polarized state = 0 Or forward slash polarized state / = 1 backward slash polarized state \ = 0


Quantum Cryptography Mechanism (cont.): Quantum Cryptography Mechanism (cont.) Heisenberg Uncertainty Principle (Young's two slit experiment) only 1 slit open both slits open intrusion


BB84 Protocol: BB84 Protocol Quantum Key Distribution Quantum Error Corrections


BB84 Protocol: BB84 Protocol A protocol for Quantum Key Distribution Developed by Brassard and Bennett in 1984 Alice wants to send a key to Bob She begins with a random sequence of bits Bits are encoded with a random basis, then sent to Bob


BB84 Protocol (cont.): BB84 Protocol (cont.) Quantum Key Distribution Bob receives the photons and must decode them using a random basis Only some of his measurements are correct What does this accomplish?


BB84 Protocol (cont.): BB84 Protocol (cont.) Quantum Key Distribution Alice and Bob can communicate over a public channel. Bob tells Alice which basis he used to decode the same bits. Where the same basis was used, Alice tells Bob what bits he should have gotten


BB84 Protocol (cont.): BB84 Protocol (cont.) Raw Key = 0 011


BB84 Protocol (cont.): BB84 Protocol (cont.) Test bits allow Alice and Bob to determine whether the channel is secure. Test bits


BB84 Protocol (cont.): BB84 Protocol (cont.) Quantum Key Distribution As long as no errors and/or eavesdropping have occurred, the test bits should agree. Alice and Bob have now made sure that the channel is secure. The test bits are removed. Alice tells Bob the basis she used for the other bits, and they both have a common set of bits: the final key!


BB84 Protocol (cont.): BB84 Protocol (cont.) Final Key = 0 1 Test bits discarded


BB84 Protocol (cont.): BB84 Protocol (cont.) Eavesdropping If an eavesdropper Eve tries to tap the channel, this will automatically show up in Bob’s measurements. In those cases where Alice and Bob have used the same basis, Bob is likely to obtain an incorrect measurement: Eve’s measurements are bound to affect the states of the photons.


BB84 Protocol (cont.): BB84 Protocol (cont.) Eavesdropping As Eve intercepts Alice’s photons, she has to measure them with a random basis and send new photons to Bob. The photon states cannot be cloned (non-cloneability). Eve’s presence is always detected: measuring a quantum system alters its state.


Quantum Cryptography History: Quantum Cryptography History Late 1960s- Quantum Money Stephen Wiesner (grad student at Columbia) 1984- First workable quantum crypto scheme Charles Bennett (IBM) and Gilles Brassard (U of Montreal) BB84 Protocol Early 1990s- First demo IBM 30 cm distance (atmosphere) January 2001- 2 km distance (atmosphere) John Rarity (UK Defense Evaluation and Research Agency)


Quantum Cryptography History (cont.): Quantum Cryptography History (cont.) Today- Testing 45 km distance (atmosphere) Richard Hughes (Los Alamos National Lab) Portable Today- Testing 60 km distance (fiber) Nicolas Gisin (University of Geneva) Future - Satellite distances (atmosphere)


Questions?: Questions?