cryptography predates computation by several milennia and has intimate ties with the military.

caesar cipher, A=1, B=2
ask if they know about:
lysistrata and scitale
DRAW

the military has always been the largest funder and user of cryptography and crypto devices.

throughout this talk, we will see the continuing relationship between crypto. military, civil liberties and privacy, democracy, well into the quantum age.

a note about terminology

classical is how quantum people refer to normal, digital computers.

to give it that warm vintage feel, like vaccuum tube amplifiers, vinyl records, etc.

this is a picture of the ENIAC, CIRCA 1930s

Today's talk will be about quantum cryptography, which is secret communication using the new model of quantum computation and quantum communication,

which is the most general model /accurate model of physics at the level of humans and smaller

qcrypto can mean two different things:

first we will talk about using quantum computers to break classical codes, most famously the RSA cryptosystem, connecting the beautiful theoretical problem of factoring with our daily lives

the problem of dividing a number into its prime factors.

15 = 5*3
143 = 11*13

this is unique, it's like a fingerprint for a number.

one of the most beautiful problems in number theory, itself the jewel in the crown that was mathematics, itself the queen of the sciences,

by Carl Friedrich Gauss, who is one of the top five mathematicians of all time, certainly the greatest up to the 19th century.

he felt if you were a self-respecting scientist or mathematician, you shouldn't be able to look yourself in the face each morning unless you were working on factoring.

and he didn't know how to do it.
and no one else did for about 200 years. this is unproven security.

analogy:

locked public mailbox.

public key is like its address/physical location anyone can send.

private key is like the mailman's key.

for RSA, m = e*d

e and d are n-bit numbers, m is an 2n bit number
(m,d) is private key
e is public key

to encrypt an n-bit message

b^e mod m

to decrypt

(b^e mod m) ^ d mod m = b

imperfect analogy because you are not writing to the mailman, and he does have the ability to snoop in your mail (not encrypted!)

so gov't could easily intercept your mail. for ex, scientists working on manhattan project, Richard Feynman's wife was dying of TB during WWII, and he would play puzzle games which looked like encryption, and they stopped his letters.

so, actually pretty close to another example next...

RSA protects nearly all online payments:

paypal transactions for your action figures on ebay
amazon books
online banking
any place that accepts your credit card numbers online

edward snowden, who revealed that the NSA had an extensive online surveillance program on U.S. citizens and fled the country,

used lavabit encrypted e-mail to communicate with privacy activitsts and the press.

vs. gmail, which stores e-mail in plaintext and scrapes it to target advertising.

FBI finally received SSL key of Lavabit in August 2013. they were trying to use this info to identify his team and track down his exact location.

edward snowden recently got a new job as a web developer in russia

quantum physics and computer science were both born in the 1900s leading up to WWII in the 1940s.

quantum physics eventually led to the hydrogen bomb, which ended the war in japan.

computer science was largely developed by Alan Turing, who was also involved in breaking the Enigma cipher used by the Germans to encode their U-boat radio transmissions. These U-boats were sinking massive amounts of allied goods every day. Used to end the war in Europe.

however, they remained separate until 1984 (mostly) when Richard Feynman proposed combining them, and until 1994 when Peter Shor discovered his famous factoring algorithm.

The difference of about 40 years is because of the unintuitive nature of quantum physics.

now that rsa is no longer secure, what should i use instead?

a lattice is a mathematical object, a set of points R^n in Euclidean n-space with a strong periodic property.

first studied by Gauss and Euler (who is probably tied for number one).

now let's turn away from quantum computation and codebreaking, to quantum communication and key distribution.

one-time pad, is the only perfectly secure means of communication, meaning as long as you keep the key secret and it is perfectly random, you have a provably exponentially small chance of guessing the decrypted message.

also called Vernham cipher

this was used, successfully, by Che Guevara, a bolivian revolutionary, in communicating with Fidel Castro.

when he was captured and executed, one-time pads were found in his jacket.

DRAW
message XOR with key

disadvantage: key must be as long as message, you are forever generating new random bits.

this is a SYMMETRIC cryptosystem, where both sides share the same key. faster, often used after RSA online secures key distribution.

separate meta-problem of crypto:
how to make sure the keys are distributed without being intercepted.

like che guevara, we can physically taken at any time, and that would compromise our secure messages.

the task is completely for a classical purpose: sharing classical keys

the method is quantum, and gives us an exponentially-high security privacy against eavesdropping, in that if it happens, the two parties and detect it and start again.

to do this, we need to study the strange properties of quantum bits.

contrast to light switch

bloch sphere
state can be anywhere, but collapses when we measure, depending on our basis

measure in one basis, which is up and down (north pole and south pole), or (east-west), + and -

These two bases are non-orthogonal, that is, classical bits encoded in one basis look completely random in the other.

again:

classical information
quantum encoding/encryption

the most famous protocol
by Charlie Bennett and Giles Brassard

DRAW

Alice wants to send n bits a to bob, and generates n random bits b.

Encodes bit a_ii either in 0-1 basis or +/- basis, depending on b_i.

Transmits to Bob.
(possibly also intercepted by Eve)

Bob generates his own random string b'. Measures to get a'.

Alice publishes string b.

Bob compares and tells Alice where his b' coincides with b.

land record, over

As of March 2007 the longest distance over which quantum key distribution has been demonstrated using optic fibre is 148.7 km, achieved by Los Alamos National Laboratory/NIST using the BB84 protocol.[9]

DARPA[edit]
The DARPA Quantum network,[15] a 10-node quantum key distribution network, has been running since 2004 in Massachusetts, USA. It is being developed by BBN Technologies, Harvard University, Boston University and QinetiQ.
SECOQC[edit]
Main article: Secure Communication based on Quantum Cryptography
The world's first computer network protected by quantum key distribution was implemented in October 2008, at a scientific conference in Vienna. The name of this network is SECOQC (Secure Communication Based on Quantum Cryptography) and EU funded this project. The network used 200 km of standard fibre optic cable to interconnect six locations across Vienna and the town of St Poelten located 69 km to the west.[16]
SwissQuantum[edit]
Id Quantique SA claimed to have successfully completed the longest running project for testing Quantum Key Distribution (QKD) in a field environment. The main goal of the SwissQuantum network,[17] installed in the Geneva metropolitan area in March 2009, was to validate the reliability and robustness of QKD in continuous operation over a long time period in a field environment. The quantum layer operated for nearly 2 years until the project was shut down in January 2011 shortly after a second independently successful attack against Id Quantique's already-commercialized hardware became public.[18]
Tokyo QKD Network[edit]
The Tokyo QKD Network[19] was inaugurated on the first day of the UQCC2010 conference. The network involves an international collaboration between 7 partners; NEC, Mitsubishi Electric, NTT and NICT from Japan, and participation from Europe by Toshiba Research Europe Ltd. (UK), Id Quantique (Switzerland) and All Vienna (Austria). "All Vienna" is represented by researchers from the Austrian Institute of Technology (AIT), the Institute for Quantum Optics and Quantum Information (IQOQI) and the University of Vienna.

we dont' even need fiber.

The distance record for free space QKD is 144 km between two of the Canary Islands, achieved by a European collaboration using entangled photons (the Ekert scheme) in 2006,[10] and using BB84 enhanced with decoy states[11] in 2007.[12]

opens up the possibility of distributing keys all over the earth via satellite, or int outer space.

when i was visiting U Waterloo, there was a laser and a receiver pointed out an office window transmitting across campus.

random physical application (not to privacy):

even wear on a bicycle.