ch8: quantum leap

today   qmech   qmoney   qcrypto   qcprot   qcsec   qcmptr  

crypto today/tomorrow

  • 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

quantum mechanics

  • 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 ?

  • 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?

quantum money

  • Scientific American articles

  • 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

quantum cryptography

  • 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

BB qcrypto protocol

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

BB qcrypto security

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

quantum computers