MULT20015 Elements of Quantum Computing Lecture 11
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 11
Week 6
Lecture 11
11.1 Introduction to Cryptography 11.2 Public Key Cryptography 11.3 RSA Cryptography
11.4 Security of RSA
11.5 Factoring and Period Finding
Lecture 12
12.1 Quantum Phase Estimation 12.2 Quantum Fourier Transform 12.3 Phase as a periodic function
Practice class 6
RSA and Quantum Phase Estimation
MULT20015 Elements of Quantum Computing Lecture 11
Recap: Lecture 10
Deutsch-Jozsa Algorithm
Given a boolean function, f(x), determine if:
f(x) is constant (always gives the same result), or f(x) is balanced (gives equal numbers of 0s and 1s)
Classical algorithm (worst case) needs (2n/2)+1 queries f(n) = (2n/2)+1 = O(2n)
Simon’s Algorithm
Quantum algorithm needs just 1 query f(n) = 1 = O(1)
H
Uf
H
H
fx =f(x⊕𝑎𝑎)
Problem: given a 2-to-1 function, f, such that
x
Find a.
Classically, if there are N (=2n) dnifferent inputs we need
O N = O 22 = O(2 ) Quantum algorithm does the same with O(n) queries.
H
Uf
H
MULT20015 Elements of Quantum Computing Lecture 11
Why Cryptography
As we will see there are deep links between quantum computing and cryptography. In this subject we will examine two of these:
• Shor’s algorithm, which breaks RSA encryption
• Quantum Key Distribution (BB84), which provides a quantum
method to distribute cryptographic keys
In the next two weeks we will discuss both of these. First, we need to know the basics of cryptography, specifically RSA.
MULT20015 Elements of Quantum Computing Lecture 11
11.1 Introduction to Cryptography
MULT20015 Lecture 11
MULT20015 Elements of Quantum Computing Lecture 11
Story of Cryptography since ancient times
Alice
Bob
Eve
Let us meet in the alley today
Let us meet in the alley today
MULT20015 Elements of Quantum Computing Lecture 11
Story of Cryptography since ancient times
Eve
Let us meet in the alley today
Alice
Bob
key
XYZGKIU KNJKSSJ VFGU
E
key
C’
C
D
Let us meet in the alley today
How do they agree on the “key”?
-Chicken and Egg Problem
MULT20015 Elements of Quantum Computing Lecture 11
Fast forward: In Modern times
Eve
Bob
Alice
Alice and Bob cannot meet in advance for every situation Can Mathematics come to their aid?
The magic tool is the One Way function.
We will consider one such function based on prime numbers
MULT20015 Elements of Quantum Computing Lecture 11
11.2 Public Key Cryptography
MULT20015 Lecture 11
MULT20015 Elements of Quantum Computing Lecture 11
Story of Cryptography
Alice (Sender)
– Uses an Encryption Function (E)
m
(Plain Text)
Ke
Encryption Key (Public/Private)
Eve (Adversary)
– Uses network probes to attack communication
Tampering & eavesdropping
C
Bob (Receiver)
– Uses a Decryption Function (D)
Kd Decryption Key (Private);
m’
(Recovered Plain Text)
E
C’
E, D are public; c is the ciphertext, c’ is received ciphertext; ideally m=m’;
Cryptography involves many conceptual ideas, we look at the basic functions Images: General Internet resources
D
= Sent ciphertext
= Received Cipher Text (Could be in error)
MULT20015 Elements of Quantum Computing Lecture 11
11.3 RSA Cryptography
MULT20015 Lecture 11
MULT20015 Elements of Quantum Computing Lecture 11
RSA
The first Public key encryption algorithm
Ron Rivest, Adi Shamir and Leonard Adleman
Based on the assumption that factoring an integer which has an alleged factorization as a product of two prime numbers is a hard problem;
In other words, given an integer n which is constructed by two secret primes p and q, finding the factors is a hard problem.
Message and cipher text belong to Zn
How to construct a crypto system using the above hard problem?
Image from https://www.usc.edu/
MULT20015 Elements of Quantum Computing Lecture 11
Prime numbers
• A number is said to be a prime number if p > 1 and p has no positive divisors except 1 and p.
• Example: p = 2,3,5,7,11,13
• The numbers which are not prime numbers are referred as composite numbers.
• Foranyintegern,n>1,letZn ={0,1,2,…,n-1}beasetofnumbers.Thissetis called the set of residues modulo n, as the elements are remainders of integers divided by the number n.
• We define the following operations on the set Zn using the modulo operation.
Clock Arithmetic • In this lecture, n will only be a prime number or a product of two prime numbers.
• Example: (6 + 7) mod 12 = 1 ; 5 × 4 mod 12 = 8;
This Photo by Unknown Author is licensed under CC BY-SA
MULT20015 Elements of Quantum Computing Lecture 11
Modular Inverse
We can now define a cyclic group over nonzero elements of Zp when p is prime. Let Z*p = {1, 2, 3, …, (p-1)}. Let g be an element of Z*p such that
Z*p = {g, g2, g3, …, gp-1=1}, (*you can always find such an element g)
*We do not cover this idea here, it requires more study; those interested can see the textbook
MULT20015 Elements of Quantum Computing Lecture 11
Euler Phi function
MULT20015 Elements of Quantum Computing Lecture 11
Some Relations
This is easy to prove from first principles.
You can realize the above result by a simple counting. Consider numbers from 1 to pq. If you exclude all those numbers which are multiple of p and q:
MULT20015 Elements of Quantum Computing Lecture 11
RSA Idea
The basic RSA idea begins as follows:
• Alice claims that she knows the factorization of n = pq ; p, q Large Primes.
• Currently it is impossible for anyone to get p, q from n: Factorization is a hard problem.
• Let us work with some random x mod n.
• We will assume that gcd(x,n) = 1.
• Consider the group generated by x mod n.
• We can show that xφ(n)= 1 mod n.
• Alice needs to create a public encryption function that anyone can encrypt, but only she can decrypt.
MULT20015 Elements of Quantum Computing Lecture 11
xφ(n)= 1 mod n : how it works
1= xφ(N)
x
x2
Parameters in Green : Public
Parameters in red Private
xφ(N)-1
xe+1
xe
?
x3
The operations are in the group of numbers modulo n under multiplication The order of the group is φ(n)= number of integers less than n and relatively prime to n= (p-1)(q-1).
n – p – q +1
= pq – p – q +1 = (p-1) (q-1)
MULT20015 Elements of Quantum Computing Lecture 11
RSA Idea Cont
• Alicewillchooseearandomnumberbetween1andφ(n)andmakeitpublic.
• So,Bobcantake(e,n)andcompute:
-> xe mod n, as his encryption.
• No one else can work backwards from xe to x because it is another hard problem-
finding eth root mod n (also known as RSA problem). • ButhowdoesAlicerecoverx?
-> She will create a trapdoor as follows.
-> She will compute d such that e × d ≡ 1 mod φ(n). -> (xe)d mod n = x;
Parameters in Green : Public
Parameters in red Private
MULT20015 Elements of Quantum Computing
Lecture 11
Why does it work? Alice has a trapdoor
Parameters in Green : Public
Parameters in red Private
x2
Fast Exponentiation
xe+1
xe
x
1= xφ(N)
xφ(N)-1
(xe)d trapdoor
x3
The operations are in the group of numbers modulo n under multiplication
The order of the group is φ(n)= number of integers less than n and
relatively prime to n= (p-1)(q-1). φ(n) is only known to Alice, which allows her to find the trapdoor function yd from the public value .
MULT20015 Elements of Quantum Computing Lecture 11
RSA PKC (1978)
• Let n = p×q; p, q are primes. Let the plain text and cipher text belong to integers modulo n and let (e, d) pair be computed such that
e × d ≡ 1 mod φ(n)
(φ :Euler’s totient function)
• FortheRSAkeyparametersetK=(n,p,q,e,d),define
Parameters in Green : Public
Parameters in red Private
Ek(x) = xe mod n Dk(y) = yd mod n,
And
where (x,y in Zn). The values (n,e) are termed the public key, and the values p, q and
d form the private key.
public key:
m=(Cd modn) C=(me modn) Private key, n = pq, d
Alice
Bob
MULT20015 Elements of Quantum Computing Lecture 11
RSA Example
• Let n = 91; p=13, q=7 are primes. Let the plain text and cipher text belong to Z91 (residue Integers modulo 91). φ(n) = 12 × 6 = 72.
• For K = (n=91, p=13, q=7 , 5, 29), define
Ek(x) = xe mod n
And
Dk(y) = yd mod n,
• Verify 5 × 29 = 145 mod 72 = 1
• Message x = 11
• Ek(11) = C=115 = 72
• Dk(72) = 7229= 11
Parameters in Green : Public
Parameters in red Private
MULT20015 Elements of Quantum Computing Lecture 11
Real-world RSA
We only illustrated some toy examples so far. Let us look at more realistic RSA parameters.
• RSA-768: a 768-bit RSA modulus with 232-digit decimal representation:
n = 123018668453011775513049495838496272077285356959533479219732245215172640050726 365751874520219978646938995647494277406384592519255732630345373154826850791702 6122142913461670429214311602221240479274737794080665351419597459856902143413.
• RSA Laboratories had issued a challenge to factor the above modulus.
• In 2009, this was broken!*
n = 3347807169895689878604416984821269081770479498371376856891
2431388982883793878002287614711652531743087737814467999489 × 3674604366679959042824463379962795263227915816434308764267 6032283815739666511279233373417143396810270092798736308917
• The current key size on Internet for secure operations is greater than 4000 bits.
* Thorsten Kleinjung, et. al, Factorization of a 768-Bit RSA Modulus. CRYPTO 2010: 333-350
MULT20015 Elements of Quantum Computing Lecture 11
11.4 Security of RSA
MULT20015 Elements of Quantum Computing Lecture 11
Security of RSA
Brute Force attacks Mathematical attacks
Crypto-Security Attacks*
• Clearly, the security depends on the hardness of the factorization problem.
• If someone can obtain factors p or q, then they can find out φ(n) and can determine
the decryption exponent, d, itself.
• As a consequence of RSA encryption, a new problem emerges called the RSA
problem.
• It is stated as follows: Given (n, e, c = Me) determine eth root of c mod n.
• This problem is also considered to be hard. The complexity is sub exponential on the key size.
• In the next lecture, we will see how Quantum computing can help to factor n efficiently.
*: Not in this lecture
MULT20015 Elements of Quantum Computing Lecture 11
Factoring and Period Finding
We want to factor N=15. Take a number a=2 (say) relatively-prime to N (ie. no prime factors in common) and find the order r of a. That is the least r, such that ar = 1 mod 15:
After which the pattern repeats.
Formally, we say: the order of 2 mod 15 is 4. Or, if we defined a function:
We would say that the period of f is r, since f(x+r) = f(x).
MULT20015 Elements of Quantum Computing
Lecture 11
Example of finding factors from a period
In our case, we have a=2, N=15 and r=4. Happily r=4 is even. We can rearrange:
In our case,
and
MULT20015 Elements of Quantum Computing Lecture 11
Divisors of N
In our case 3 and 5 divide N=15 exactly, but we’re not guaranteed that always, only that:
ie. that
As long as neither factor is a multiple of N, then both will have non-trivial factors with N. To find these factors, we find the greatest common divisors (for which the Euclidean algorithm is efficient):
These give a non-trivial factor of N.
If r is even or if the factors found are trivial, we repeat the algorithm with a different choice of a.
MULT20015 Elements of Quantum Computing
Lecture 11
TLDR: Factoring and Period finding
If we can find the period of efficiently, we can factor efficiently.
f(k) = ak mod N
Classically, we do not have any efficient algorithm for the period finding problem.
Shor’s algorithm finds this period efficiently, and we can then use classical techniques to factor semi-prime numbers into their prime factors.
MULT20015 Elements of Quantum Computing Lecture 11
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 11
Week 6
Lecture 11
11.1 Introduction to Cryptography 11.2 Public Key Cryptography 11.3 RSA Cryptography
11.4 Security of RSA
11.5 Factoring and Period Finding
Lecture 12
12.1 Quantum Phase Estimation 12.2 Quantum Fourier Transform 12.3 Phase as a periodic function
Practice class 6
RSA and Quantum Phase Estimation