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 Bohr
1799 Thomas Young
ripples from two ducks
light through two slits
Undulatory Theory of Light
light: particle or wave ?
E = nhf, then E = mc2
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
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 .5k
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