Transcript Awesome PowerPoint Background Template

Slide 1
Introduction to
Quantum Cryptography
Nick Papanikolaou
[email protected]
Slide 2
The Art of Concealment

To exchange sensitive information, encryption
is used

Encryption schemes in use today are under
serious threat by quantum computers

The study of Quantum Computing and Quantum
Information has yielded:
– ways of breaking codes
– ways of making better codes
Slide 3
This Talk
1.
About Cryptography
2.
Making Quantum Codes
3.
Breaking Classical Codes
Announcement:
Nick’s office hours (Rm 327):
Tuesdays 3-4pm
Thursdays 2-3pm
Slide 4
Cryptography

Cryptography is the science of encoding
and decoding secret messages.

Most common form: Symmetric
Cryptography

Message M, Key K

Encryption: enc(M,K) = c

Decryption: M = dec(c,K)
Slide 5
Classical Cryptography [2]

We assume that the key has been already
secretly shared between sender/receiver.
Sender
Receiver
enc(M,K) = c
M = dec(c,K)
Eavesdropper
dec(c,???)
Slide 6
Perfect Cryptosystems

In order to decipher the message M, the
eavesdropper needs to know the key K.

Assuming K is completely secret, a
perfect cryptosystem can be used.
– Perfect cryptosystem: H(C|K)=H(C)

Example: One-Time Pad
– Use a different key each time, equal in length
to the message
Slide 7
Key Distribution

How do you exchange the key securely in
the first place?
Sender
Receiver
K
K
Eavesdropper
K
Slide 8
QKD

Quantum mechanics gives us a way of
ensuring that an eavesdropper, if present,
is always detected.

This is called Quantum Key Distribution.

Main Idea:
– Encode each bit of the key as a qubit.
Slide 9
Photons as Qubits

A qubit holds a single quantum state.
– Can be in any mixture of basis states.
– The polarization of a single photon can be
used as a qubit.

Rectilinear Basis

0 
or 

 cos
 sin

   1
  0
where ,  C and |  |2  |  |2  1
1 
or 
Slide 10
The Diagonal Basis

We can also encode a qubit as a
photon in the diagonal basis:
Diagonal Basis 

0 
1
or

or


 cos
 sin

   1
  0
where ,  C and |  |2  |  |2  1
Slide 11
Quantum Measurement

Observing a photon changes its state.
with probability cos2 
Calcite Crystal
with probability sin2 
   0 1
0, with probability |  |2

2
1
,
with
probabilit
y
|

|

Slide 12
Measurement [2]

If a photon is measured using the wrong
polarization angle for the crystal, then the
result will be
– Correct with probability 50%
– Incorrect with probability 50%

Therefore, if an eavesdropper made a
measurement in the wrong basis, his result
would be random and he would be detected.
Slide 13
Review of QKD

The basic idea is that each bit in the key is
mapped to a photon with a specific
polarization.

e.g.:
0 1 0 1 0 1 1

Bases:
    

Photons:
   
Slide 14
Eavesdropping

An eavesdropper can choose a basis for
decoding at random. For previous example:

Photons received:
   

Bases chosen:
  

Result:
? ? 0 1 ? ? ?

To get all of n bits correctly, probability is only
n
0.5

So for 64 bits, eavesdropper only has chance
5.410-20 of getting the right answer.
Slide 15
Breaking Classical Codes
Peter Shor, ATT Labs
If computers that you build are quantum,
Then spies of all factions will want 'em.
Our codes will all fail,
And they'll read our email,
Till we've crypto that's quantum, and daunt 'em.

Invented a quantum algorithm for efficiently finding
the prime factors of large numbers.

Classical factoring algorithms: O((log N) )

Shor’s algorithm: O(log N)
k
Slide 16
Afterword
Einstein was a giant.
“
His
head
But his
was in the
feet
clouds,
were on the
ground.
But for those of us who are not that tall,
We have to choose somewhere inbetween.”
- Richard Feynman, on
quantum mechanics