COMP2300/6300 Applied Cryptography

COMP2300/6300 Applied Cryptography
Les Bell, les.bell@mq.edu.au
Quantum and Post-Quantum Crypto
Outline
 Basic quantum mechanics
 Quantum computing
 Quantum cryptography
 Quantum Key Distribution (QKD)
 Quantum Cryptanalysis

 	Shor’s Algorithm Grover’s Algorithm

 Post-quantum cryptography

	NTRU
	McEliece cryptosystem

2
Quantum Mechanics
 Quantum mechanics is weird – not just weirder than you
imagine, but weirder than you can imagine
 (paraphrasing J. B. Haldane)
 Action (physical quantity) of subatomic particles always
integral multiples of Planck’s constant
 Electrons in discrete orbits around nucleus of atom

 	“Quantum leap” is the jump between orbits Not really in a single place – expressed as probability function (‘wave function’)

 Particle-wave duality
 Fire particles at a grating – see diffraction on the far side
3
Qubits
 The wave function of a quantum system is described by
Schrodinger’s equation

	This is a linear equation so wave functions can be added (and multiplied by complex numbers)

 Qubits (quantum bits) exist in superposition of states until
observed

	Expressed in bra-ket (Dirac) notation
•	\|0> becomes zero when observed

•	\|1> becomes one when observed
	A qubit corresponds to a unit vector in a two-dimensional Hilbert space

• Probability amplitudes can be positive, negative or even complex
• Interference between amplitudes will tend to cancel out wrong answer

	Observation collapses the wave function
•	So you can’t debug a quantum program!

4
Quantum Computing
 If you thought quantum physics was weird . . .
 A quantum factorization of 143 (using a 4-qubit NMR
quantum computer) was later found to have also factored
several much larger numbers such as 3599, 11663 and
56153, but the experimenters didn’t realize it at the time!
 There is a technique called Counterfactual Computation
in which you get an answer from a quantum computer by
not running it.

	It uses the quantum Zeno effect on the spins of a negatively charged nitrogen-vacancy color center in diamond

• (And yes, I don’t understand it, either.)
5
“The Talk”
6
Quantum Cryptography
Quantum Key Distribution
 Based on transmission of polarized photons





BB84 protocol
Privacy amplification
Developed by Charles H. Bennett (IBM Research) and Giles Brassard
(U. Montreal)

 Or on quantum entanglement (‘spooky action at a
distance’) of a pair of photons

 	One photon kept by Alice One photon sent to Bob

8
Observation of Photons
 Photons can be polarized
 E.g by reflection off glass or snow
 Horizontally-polarized light will not pass through a verticallypolarized filter

 	Principle used by polarized sunglasses to reduce glare If angle between a polarized photon and polarized filter is θ, then the photon will pass with probability cos2(θ) • i.e. if at 45°it will pass with probability 0.5 A photon that passes will emerge with the polarization of the filter


 The only way Eve can detect photon polarization is to pass it
through a filter and see if it emerges
 But the changed polarization means such observation cannot go undetected
• (though she could try re-transmission as a MitM attack)
9
BB84 Quantum Key Distribution
 Alice transmits a random stream of 1’s and 0’s
modulated using a random stream of +’s and x’s

 	+: Alice transmits 0 as –, 1 as \| x: Alice transmits 0 as , 1 as /

 Because the sequence of +’s and x’s is random, Alice will
sometimes transmit using h/v polarization, sometimes
diagonal polarization
 Alice’s transmitting end
10
BB84 Quantum Key Distribution
 Bob has to set up a filter to detect the polarization of each
photon

	But he does not know what to expect • If Alice transmits 0 using v/h polarization, then

• If Bob chooses a horizontal filter, he will definitely detect it
• If Bob chooses a vertical filter, he will definitely not detect
• If he chooses either diagonal filter, there is a 50% chance of
detecting the photon, and it will now be diagonally polarized
• Similar logic applies to diagonal polarization
 Bob does his best, choosing filter polarization randomly,
and records every observation until Alice has sent the
entire keystream
 Bob’s receiving end
11
BB84 Reconciliation Stage
 Alice and Bob now broadcast the polarization they used

	They keep the observations and transmissions where they agree, and discard those observations where they used different polarization About half of the bits will be dropped (because Bob guessed the wrong polarization)


 Was Eve eavesdropping?

	Alice and Bob now compare a sample of half of the remaining bits
•	If they mostly agree, then either Eve was extremely lucky to guess the right polarization and get some of the bits

• Or Eve could not have been intercepting them
• But there still could have been errors due to noise in photon
detectors
• If they disagree wildly, Alice and Bob start over, on some other channel
• Otherwise, they repeatedly compare parity on bisected halves of the
bitstring until they have eliminated errors
12
Reconciliation Example

–

Keep

√

13
Key:
K = key bitstream
A = Alice’s chosen polarization
AS = Alice sends
BG = Bob’s guessed detection
polarization
Keep = matched polarization guesses
Resultant key = 01010010
Privacy Amplification
 Alice and Bob now have identical bitstrings, but Eve
might have some information about them
 Privacy amplification reduces the amount of information
Eve might be able to infer about the key
 Essentially error correction combined with a universal
hash function
14
Quantum Cryptanalysis
Shor’s Algorithm
 Runs in polynomial time

	Partly classical computation, partly quantum
•	Requires a purpose-built quantum circuit to perform a Fourier transform

• Used as a subroutine to find the period of the function f(x) = ax mod N
 Choose a random a < N
 Compute gcd(a,N) – if this is not 1, we already know one
factor, so we’re done
 Use the quantum subroutine to find r, the period of ax mod N
 If r is odd, or

The post COMP2300/6300 Applied Cryptography appeared first on My Assignment Online.

Get Instant Help on WhatsApp