MULT20015 Elements of Quantum Computing Lecture 14
Subject outline
Lecture topics (by week)
1 – Introduction to quantum computing and maths basics 2 – Single qubit representations and logic operations
3 – Two qubit states and logic gates
4 – Multi-qubit states and quantum arithmetic
5 – Basic quantum algorithms
6 – Period finding, cryptography and quantum factoring
7 – Shor’s algorithm, post-quantum crypto, quantum key distribution 8 – Quantum search algorithms
9 – Grover search applications, optimisation problems
10 – Solving optimisation problems on quantum computers
11 – Applications in quantum machine learning
12 – Real quantum computer devices
Assignment schedule:
#1: Hand out in Week 2
#2: Hand out in Week 8
MULT20015 Elements of Quantum Computing Lecture 14
Week 7
Lecture 13
13.1 Shor’s algorithm
13.2 The Fourier transform
13.3 Measurement and post-processing 13.4 Summary
Lecture 14
14.1 Post-quantum cryptography 14.2 Quantum Key Distribution (QKD)
Practice class 7 Shor and QKD
MULT20015 Elements of Quantum Computing Lecture 14
Recap: Shor’s algorithm
• Efficientquantumalgorithmsforfactoringsemiprimenumbers
• Bestknownclassicalalgorithmisnumberfieldsieve(exponentialinbit-length). • UnderpinstheRSAcryptosystem
• HiddenSubgroupProblems(eg.Discretelogarithm)similar.
Shor, Proc 35th Ann Symp of Comp Sci, 26, (1995)
Peter Shor
MULT20015 Elements of Quantum Computing Lecture 14
14.1 Post-quantum cryptography
This section is for Information only- not examinable
References:
NISTIR 8105: Report on Post-Quantum Cryptography, available from
https://csrc.nist.gov/publications/nistir NIST: National Institute of Standards and Technology
MULT20015 Elements of Quantum Computing
Lecture 14
Need for Post-Quantum Cryptography
Public key Cryptography is ubiquitous- it is a backbone of network based modern communication infrastructure.
Main tools are Encryption, Signature and key exchange protocols.
Most of these modern public key algorithms depend on Integer Factorization and discrete logarithm problems.
Shor’s algorithm solves the above problems efficiently on a quantum computer.
However, quantum computing capability is currently limited.
But it is only a matter of time before we have a large quantum computer capable of solving the problems that are currently used in cryptography.
Let’s now examine the impact in more detail.
MULT20015 Elements of Quantum Computing
Lecture 14
Impact of Quantum Computing: NIST
We only looked at RSA in last week’s lecture. Other schemes mentioned above are equally important in practice;
Some even predict that the development of a large scale Quantum Computer is merely
a significant engineering challenge; Thus it is important to find algorithms that are secure against both Quantum and Classical adversaries
Table 1: Taken from NIST report NISTIR 8105 from
https://csrc.nist.gov/publications/nistir
MULT20015 Elements of Quantum Computing Lecture 14
Complexity Classes P and NP
Class P: We say that an algorithm solves a problem in polynomial time if its worst case complexity is O(p(n)), where p(n) is a polynomial of the input size n. Class P is a set of all algorithms that has polynomial time complexity.
Example: Multiplication, addition and GCD between any two numbers,
Nondeterministic algorithms: Algorithms that have two stages; a guessing (oracle) stage giving a solution and a subsequent verification stage that verifies the guessed results.
If the verification stage of the Nondeterministic algorithm has polynomial time complexity then the algorithm belongs to Class NP.
Example: Factoring a large integer n; this problem is in 𝑁𝑁𝑃𝑃, because once the factors are determined, they are the correct result if the multiplication of all the factors lead to n.
Clearly, 𝑃𝑃 ⊂ 𝑁𝑁𝑃𝑃 But, P ?= NP An important open problem
The concept can be extended to randomized algorithms; Class BPP is the class of all problems which can be solved by randomized polynomial time algorithms with bounded error. This is a rough definition.
Similarly we can define Class BQP for problems solvable by a quantum computer
in polynomial time
Next we will consider more general classes and their relations to post quantum cryptography.
MULT20015 Elements of Quantum Computing Lecture 14
Complexity Classes
Where to look for candidates for post quantum cryptography?
PSPACE
NP
BQP BPP
3-Coloring, SAT, etc
Integer Factorization Discrete Logarithm etc
Multiplication, Sorting, GCD etc
P: Polynomial Time BPP: Bounded-Error Probabilistic P Time BQP: Bounded-Error Quantum P Time
NP: Nondeterministic P time
BQP is Tractable on Quantum computers
P
Fig: The known relationships between some of the most important complexity classes. Need hard problems above BQP Class in order to resist quantum attacks
Big challenge for quantum computing: find new problems in BQP but that are not in BPP. If you find one you will be famous!
Figure taken from: An Introduction to Quantum computing by P. Kaye et.al., OXFORD Press
MULT20015 Elements of Quantum Computing
Lecture 14
NIST Suite of Public Key Post-Quantum Algorithms
There is a need to look for public key algorithms which are believed to be resistant against both classical and quantum computers.
This is a big area of research currently followed in cryptographic circles.
Some important class of algorithms currently considered by NIST are: 1. Lattice-based cryptography
2. Code-based cryptography
3. Multivariate polynomial cryptography
4. Hash-based signatures
5. Other methods based on variants of curves defined over finite fields.
See more details from: https://csrc.nist.gov/Projects/post-quantum- cryptography/
Symmetric key algorithms also affected by the developments in quantum computing, but the effect is relatively less compared to their public key counterparts; A general remedy is to double the key size. Grover’s algorithm will be discussed later in the course.
MULT20015 Elements of Quantum Computing Lecture 14
Comparison of key sizes
This is a very active area in Cryptography currently, please follow the research from the NIST resources.
Table from: https://blog.trailofbits.com/2018/10/22/a-guide-to-post-quantum-cryptography/
This comparison is only for schemes submitted to NIST
MULT20015 Elements of Quantum Computing Lecture 14
14.2 Quantum Key Distribution
Back to material that are examinable
MULT20015 Elements of Quantum Computing Lecture 14
Key Distribution
Alice would like to establish a secret key with Bob.
Alice
Bob
Secret key
0111011000111
Alice and Bob would like to establish a secret key. If they had such a key they could use it to communicate securely. The problem is Alice and Bob are both stuck at home due to COVID-19 so they can’t get together to establish a secret key in private.
MULT20015 Elements of Quantum Computing Lecture 14
Eve, the eavesdropper
Alice
Bob
Eve
But if Alice tries to send Bob a key (or vice-versa) when their communication is not secure, then an eavesdropper (called Eve) can listen in an learn their key.
MULT20015 Elements of Quantum Computing Lecture 14
Story so far
• Last lecture we demonstrated how a Quantum algorithm breaks RSA, a popular public key cryptography scheme. Note that RSA is the first efficient public key scheme where two users who have not met before is able to arrive at a common secret on a public communication link by using only public information.
• Here we will see how quantum protocol provides a similar result, i.e., concrete secret key exchange scheme between two communication entities.
• So, what was taken away Quantum gives back in another form.
MULT20015 Elements of Quantum Computing Lecture 14
Quantum Key Distribution
Alice
Bob
Eve
Quantum Key Distribution is a way that Alice and Bob can establish a secret key, and know that an eavesdropper, Eve, has not listened in as they do that.
MULT20015 Elements of Quantum Computing
Lecture 14
Stages of BB84 Quantum Key Distribution
Quantum Key distribution follows several steps.
1) Alice chooses to encode a qubit in a random basis
2) Alice sends qubits to Bob
3) Bob chooses to measure in a random basis
4) Alice and Bob announce their basis. They throw out qubits where their
bases differ.
5) On a subset of qubits, Alice and Bob compare results
• If they disagree on these qubits, there might be an eavesdropper
• If they agree, they use the state of the remaining qubits as the key.
Let’s now examine each step in more detail.
MULT20015 Elements of Quantum Computing
Lecture 14
Alice encodes in a random basis
What do we mean by a random basis? Alice either encodes using the z-basis or the x-basis:
Binary Data
z-basis
x-basis
0
1
where
MULT20015 Elements of Quantum Computing
Lecture 14
Sending and receiving in the x- basis
To change between x- and z- bases, just add a Hadamard gate:
Sends qubit
Alice sending in x-basis
Bob receiving in x-basis
MULT20015 Elements of Quantum Computing
Lecture 14
Sending and receiving in the z- basis
To change between x- and z- bases, just add a Hadamard gate:
Sends qubit
Alice sending in z-basis
Bob receiving in z-basis
MULT20015 Elements of Quantum Computing
Lecture 14
If they don’t agree on the basis…
Measurement results: 50/50%
Sends qubit
Alice sending in x-basis
Bob receiving in z-basis
Sends qubit
Measurement results: 50/50%
Alice sending in z-basis
Bob receiving in x-basis
MULT20015 Elements of Quantum Computing
Lecture 14
Measurement of |+> and |-> states
Measure “0” and state collapses to:
Measure “1” and state collapses to:
MULT20015 Elements of Quantum Computing
Lecture 14
Measurement of |+> and |-> states
If Bob measures in the “wrong” basis, then his result is 50/50%.
Measure “0” and state collapses to:
Measure “1” and state collapses to:
In quantum mechanics measurement disturbs the state.
MULT20015 Elements of Quantum Computing Lecture 14
Discard when bases disagree.
If Alice and Bob use the same basis (for transmission and measurement), then the bit Alice transmitted is what Bob received.
These bits can be used as part of the key.
If Alice and Bob use different bases (transmit in one basis, and measure in the other) then what is received is random.
These bits should be discarded.
After qubits have been distributed and measured
Alice announces what basis she used to transmit each qubit.
Discard if they disagree
Keep if they agree
Bob announces what basis she used to measure each qubit.
MULT20015 Elements of Quantum Computing Lecture 14
Example of first few qubits sent
Alice Sends
Alice Basis
State Alice Sends
Bob’s Basis
Bob Measures
Keep this bit?
Bit for secret key
0
x
|+>
x
0
✓
0
1
z
|1>
x
0
✗
–
1
x
|->
z
1
✗
–
0
z
|0>
z
0
✓
0
MULT20015 Elements of Quantum Computing Lecture 14
What about the eavesdropper?
Eve, the eavesdropper, can listen in but has a problem:
•
• •
She doesn’t know which basis to measure in, so she has to guess, randomly choosing a basis to measure in.
If she chooses correctly, she can send on the state unchanged. If she chooses wrongly, she gets a random result, and sends on the state in the wrong basis. She cannot send on the original state, because it has collapsed when she measured it.
•
Alice and Bob can detect the presence of Eve, they choose a subset of their qubits where they used the same basis, and check the bits really are the same:
• Without an eavesdropper, their bits be the same. • With an eavesdropper, 1/4 will be different.
In quantum mechanics measurement disturbs (by collapsing) the state you are trying to measure.
MULT20015 Elements of Quantum Computing Lecture 14
Detecting an Eavesdropper
0
x
|+>
x
0
|+>
x
0
✓
✓
1
z
|1>
z
1
|1>
x
0
✗
–
1
x
|->
z
1
|1>
z
1
✗
–
0
z
|0>
x
0
|+>
z
1
✓
✗
There is an eavesdropper on the line!
Only some qubits are used to detect an eavesdropper. The remaining qubits are used to construct the shared secret key.
Alice Sends
Alice Basis
Alice Sends
Eve’s Basis
Eve measures
Eve sends
Bob’s Basis
Bob measures
A/B Same basis?
Do their bits match
MULT20015 Elements of Quantum Computing
Lecture 14
Stages of BB84 Quantum Key Distribution
Quantum Key distribution follows several steps.
1) Alice chooses to encode a qubit in a random basis
2) Alice sends qubits to Bob
3) Bob chooses to measure in a random basis
4) Alice and Bob announce their basis. They throw out qubits where their
bases differ.
5) On a subset of qubits, Alice and Bob compare results
• If they disagree on these qubits, there might be an eavesdropper
• If they agree, they use the state of the remaining qubits as the key.
MULT20015 Elements of Quantum Computing Lecture 14
Security of QKD Systems
• QKD systems have inherent information-theoretic security based on quantum mechanical principles.
• A typical cryptographic scenario: Alice and Bob can use QKD systems to obtain string of key bits (r) by BB84 protocol. Any eavesdropper naturally introduces noise to the transmission, the end users can estimate maximum amount of information gained by the eavesdropper. Another process called privacy amplification (not discussed in this lecture) can be applied to compress (r) to a final secret key (k) which is completely oblivious to the eavesdropper.
Usual PA processes are based on applying hash functions
MULT20015 Elements of Quantum Computing
Lecture 14
Quantum Hacking and other attacks
• Are there any other attacks on QKD systems?
• Any attack must base it on the quantum implementation’s deviations with its ideal model. If the gap is less than threshold, the size of the key is related to the amount of potentially leaked information which helps to determine the parameters of compression in the PA techniques. If the gap is greater than a threshold, end users may not realize a secure key.
• There is this familiar denial of service (DoS) attack. Counter strategy is to introduce alternative channels for acquiring keys.
MULT20015 Elements of Quantum Computing Lecture 14
QKD is fast becoming a reality
QKD distribution network built over 4600km in China connecting Shanghai and Beijing.*
* Ren, JG., Xu, P., Yong, HL. et al. Ground-to-satellite quantum teleportation. Nature 549, 70–73 (2017). https://doi.org/10.1038/nature23675
Next steps: satellite based QKD, with existing technology demonstrating free-space quantum communication over the atmospheric distances required.**
** Liao, SK., Cai, WQ., Liu, WY. et al. Satellite-to-ground quantum key distribution. Nature 549, 43–47 (2017). https://doi.org/10.1038/nature23655
MULT20015 Elements of Quantum Computing Lecture 14
Week 7
Lecture 13
13.1 Shor’s algorithm
13.2 The Fourier transform
13.3 Measurement and post-processing 13.4 Summary
Lecture 14
14.1 Post-quantum cryptography 14.2 Quantum Key Distribution (QKD)
Practice class 7 Shor and QKD