today, cryptographers seem stronger than cryptanalysts

true (?) in theory, also in practice ?

much traffic poorly (or not) encrypted

peripheral attacks

keystroke recording

viruses (e.g. attach to email)

Trojan horse (e.g. looks like pgp)

intentional backdoors (governments want this)

Crypto AG, Snowden

cracking RSA

each year, minimum secure keysize increases (now 2000 bits)

faster factoring ?

without factoring ?

beyond RSA

elliptic curve public key crypto

*Anyone who can comptemplate quantum mechanics without getting dizzy hasn't understood it*. Niels Bohr1799 Thomas Young

ripples from two ducks

light through two slits

*Undulatory Theory of Light*

light: particle or wave ?

E = nhf, then E = mc

^{2}superposition: light splits into two states simultaneously

SchrÃ¶dinger's cat

many worlds (multiverse): light can be in one of two possible (interfering) universes

wave/particle duality: matter behaves sometimes like a wave, sometimes like a particle, but not like both at the same time

1984 David Deutsch: computer based on quantum mechanics

essentially, use quantum mechanics to build massively parallel machine

machine asks different question in each universe simultaneously

find x : x2, x3 use digits 0, …, 9

classical computer: try x=0, x=1, …, serially

parallel computer: try x=0, x=1, …, simultaneously

quantum computer: based on particle spins (e.g. east/west)

build quantum computer using qbits

quantum mechanics 2016?

in the years since Singh wrote his book, how has the construction of quantum computers progressed?

Google's D-wave: hype but few results yet

a tested 5qbit machine qc w photons

1994 Peter Shor ATT/Bell: quantum factoring algorithm

1996 Lov Grover: quantum list search algorithm

Wiesner 1960s: photon vibration has polarisation

Heisenberg uncertainty principle: can't know both complementary parts (e.g. position-momentum)

observer effect: measuring changes state

measure photon polarisation with filter

simplifying assumption: polarisation states | - / \

photon hits | filter ? *: absorbed

| photon => | (probability 1)

- photon => * (probability 1)

/ photon => * (probability .5) | (probability .5)

\ photon => * (probability .5) | (probability .5)

photon hits / filter ? similar ...

photon hits \ filter ? similar ...

photon hits - filter ? similar ...

idea: embed photon traps in each bill

bank records serial number and photon polarisation sequence

bank checks validity of bill

confirm each photon polarisation correct

reset each photon

forger tries to copy bill, by measuring each photon

pick filter, e.g. |

absorbed => guess polarisation: - .5 / .25 \ .25

not absorbed => guess polarisation: | .5 / .25 \ .25

prob. forger guesses polarisation correctly ?

at most .5

prob. forger guesses all k polarisations correctly ?

at most .5

^{k}

Bennett ugrad w Weisner @ Columbia, TJ Watson research fellow

Brassard - cs, U de MontrÃ©al

rectilinear scheme

send either { - | }, ie. { 0 1 }

receiver uses any of { - | + }?

interpret correctly w prob 1

receiver uses any of { \ / x } filter ?

interpret correctly w prob .5, alter photon

diagonal scheme

send either { \ / }, ie. { 0 1 }

receiver uses any of { - | + } filter ?

interpret correctly w prob .5, alter photon

receiver uses any of { \ / x } filter ?

interpret correctly w prob 1

Alice select random (+ or x) filter sequence select random (0 or 1) message sequence send resulting photon sequence filter + + x + x + + x + x x x + x message 1 1 0 0 1 1 0 1 0 1 0 1 1 1 photon | | \ - / | - / - / \ / | / Bob select random (+ or x) filter sequence interpret Alice photon sequence filter + x x + x x + + + + x x x + photon | | \ - / | - / - / \ / | / interpret 1 ? 0 0 1 ? 0 ? 0 ? 0 1 ? ? after Bob receives message, Alice phones Bob Alice/Bob exchange filter sequences message on matching filters becomes key Alice filter + + x + x + + x + x x x + x Bob filter + x x + x x + + + + x x x + matched + x + x + + x x key 1 0 0 1 0 0 0 1

Eve guess random filter sequence eavesdrop A/B phone call intercept and measure A/B quantum transmission correctly guess about .5 A/B key bits but ... Eve filter x x + + + x x + + x + x + x Alice/Bob matched + x + x + + x x key bits 0 0 1 Eve's measuring altered about .5 photons original photon | | \ - / | - / - / \ / | / Eve filter x x + + + x x + + x + x + x altered photon ? ? ? - ? ? ? ? - / ? / | / eg. \ / | - - / / - - / | / | / this changes Bob's reception ... about .25 his bits now wrong altered photon \ / | - - / / - - / | / | / Alice-Bob matched + x + x + + x x key ? ? 0 ? ? 0 ? ? eg. 1 0 0 0 1 0 1 0 so, over phone Alice and Bob agree on small random fraction of test bits compare values if enough are wrong, they suspect Eve Alice-Bob matched + x + x + + x x test bits . . . Alice 1 1 0 Bob 1 0 1

1988 Charles Bennett and John Smolin 30 cm

1995 U Geneva 23 km

Los Alamos 1 km through space

qc for Swiss election

d-wave