Getting Started with

Post Quantum Cryptography — Part 1

Part 1: Introduction and Motivation. In these series of blog posts, we will discuss the impact of quantum computing on cryptography and its implications on the world. Along with the aforementioned, we will discuss various types of post-quantum cryptographic algorithms in depth.

18 min readJun 11, 2020

Impact Of Cryptography

Before talking about post-quantum cryptography lets focus our attention on cryptography! What is is the significance of cryptographic systems in our day to day life?

Bitcoin one of the first blockchains makes use of SHA-256 a one-way hashing algorithm to create a linked list of blocks. It also makes use of ECDSA to sign transactions on the blockchain and to make sure only the rightful owners of the cryptocurrency can use it.
Our browsers make use of HTTPS to securely communicate and exchange information with web servers. HTTPS makes use of TLS(Transport Layer Security) an advanced version of SSL(Secure Sockets Layer) to encrypt and send data across a secure channel.
As the world is moving towards a digital age more and more documents are becoming digital in nature. They are signed using digital signatures to provide the authenticity and validity of the document.
These were just some of the examples! Cryptographic security is widespread and is in use in most of the major industries! Some examples are:- Electronic Money, Identity authentication, secure data transmission, storage secrecy, etc.

Essence Of Quantum Computing

The smartphones in our pockets are what would have been described as a supercomputer by a computer scientist in the late 1970’s. We have had the privilege of using these classical computing devices for almost every task of our lives. It would be very difficult to imagine our life without them. However, they have an inherent flaw! For problems above a “certain size and complexity”, even all the computational power on the earth will be feeble. This is where the power of quantum computing comes in. Unlike a classical computer, a quantum computer works on the laws of quantum mechanics. It leverages the quantum mechanical phenomena of superposition and entanglement to create states that scale exponentially with the number of quantum bits (qubits)! A classical bit can hold a value of 0/1 whereas a qubit holds superimposition of both values. So in a quantum computer, the computing power grows exponentially(doubles) with each qubit [2].

Many of the current challenging problems like drug design and discovery, simulation of physical and quantum mechanical systems, logistics and scheduling, quantum machine learning, etc can be solved by quantum computers. Recently there have been great strides in the development of quantum computers and a universal quantum computer can be possible in the next 20–30 years.

Cryptography in the Quantum World

So you may wonder, how is quantum computing and cryptography related? The defense of most of the public key encryption algorithms like RSA, ECDSA is based on the premise that it is computationally impossible to reverse engineer the multiplication of very large prime numbers. The security of most of these signing algorithms lies in the variants of the hard mathematical problem of Integer factorization and Discrete Logarithms. Though it can be categorized as an NP problem i.e computationally hard for classical computers it can be solved in polynomial times by Quantum computers. Peter Shor a Professor at MIT had written an algorithm that can find prime factors in polynomial time(O(log(n³)) [1]. This algorithm aptly named the Shor’s algorithm and its variants can break most of the public key encryption systems in use currently. Once universal quantum computers are feasible they can create havoc and crash global markets effectively leading to a crisis. Most of the blockchains make use of public key infrastructure for signing. Also, TLS, digital signatures, and other secure communication channels and applications make use of it. Thus quantum computers have the power to disrupt the cryptography world!

So should we be scared of this distant future? Well, worry not! There is still some speculation regarding the time it will take to create a universal quantum computer. Meanwhile, NIST(National Institute of Standards and Technology) had requested proposals for quantum-proof encryption algorithms in 2016. By 2019 for Round 2, 26 proposals were accepted, and by the last round(June 2020), 3–4 will be selected for standardization. We will start with a concise summary of some of the quantum algorithms which break our encryption methods.

Menacing Quantum Algorithms

In the following subsections, we take a concise overview of the quantum algorithms which are a threat to current cryptographic systems.

Shors algorithm

Currently, the fastest method to find prime factors is using the sieve method(Refer: [15] [16]). However, for very large numbers it can take years of computing time. Current asymmetric encryption methods rely on the difficulty of finding these prime factors. It is possible but highly unlikely to guess the numbers. So I will give a concise explanation of the shors algorithm which can find prime factors of a number n in O(log(n)³) time. The algorithms core crux lies in doing better guesses for the prime factors every iteration. The surprising part of the shors algorithm is that it is is a classical algorithm that makes use of quantum computing properties to speed up the calculations. Normally you can try to run this algorithm on a classical computer but it will take a lot of time like other traditional algorithms as the algorithm depends on using quantum computation to find the value “p” which will be mentioned in the next subsection. Thus it has nothing intrinsically quantum mechanical but its supplemented by a quantum computer for guessing the number “p” in ridiculously low computing time. Another important thing to note is we don’t always need to find the pure prime factors of a number. Finding number which shares some factors with n can be used to find these shared factors of n using Euclid’s algorithm. Quantum computers can simultaneously do multiple operations on a single input via a superposition. However, we can only measure one of the outputs called as the computational basis. Most quantum algorithms set up quantum gates in such a way that most of the incorrect answers are canceled out/ have low probability using destructive interference.

Process:

To find the prime factors of an integer n [9]:

Randomly choose an integer g | 0 < g < n. If g % n = 0 we are done Else go to step 2
Find period t of g, where t is the number of cycles before gˣmod(n) gives the same result.
If t is odd, go back to step 1
If gcd(g,n) = 1 use Euclid’s algorithm to find the factors and we are done.
If gcd(g,n) ≠ 1 ∃ {n ,g} | gᵖ = m.N+1 where g and p are coprime. This can be simplified as follows:

gᵖ⁻¹ = m.N
(gᵖ/²⁺¹) .(gᵖ/²⁻¹) = m.N

These two numbers will either be a factor of N or a multiple of m or N hence are an improved guess over g. Thus we can find more probable prime factors and numbers with shared factors with this method.

6. Now we need to calculate these two numbers(Better guesses). Finding this number p is computationally hard for a classical computer. P is calculated using a quantum computer. Here is how:

gˣ = m.N+r
gˣ⁺ᵖ = m’.N+r where m’ ≠ m

This means adding or subtracting p from the random number x keeps the same remainder r. Therefore gˣ, gˣ⁺ᵖ, gˣ⁺²ᵖ and so one will have the same remainder r. We can utilize this property to separate p from some random x+np for a remainder r. Hence we do a quantum superposition of all the possible exponents of p to g(i.e gᵖ) and their remainder r from the equation gᵖ=m.N+1. From this superposition, we measure those with a random remainder r we will get a superposition of all the powers of g with remainder r in the form of gˣ+np. Now we have a superposition of repeating powers of g with a period of p and frequency = 1/p. Hence we use a Quantum Fourier Transform(QFT) with a frequency of 1/p to cause destructive interference between the superpositions and finally give us the value p.

7. If g⁽ᵖ/²⁾⁻¹ or g⁽ᵖ/²⁾⁺¹ is a multiple of m/n, go to step 1.

Repeat this process for several iterations to get all the prime factors. Thus using Shors algorithms we can exponentially increase our time complexity for finding prime factors, endangering the principles of most of the current asymmetric key encryption algorithms like RSA, Diffie-Hellman Key Exchange. Here we lay the foundations for the following sections where we discuss these properties in length.

Grover’s Algorithm

The Quantum search or Grover’s algorithm is a quantum computing algorithm that searches an unsorted database in O(√n) time as compared to classical ones which take O(n) [1]. Thus it improves the cracking mechanism by a factor of 2(i.e √2ˢᶦᶻᵉ⁽ᵏᵉʸ⁾) [1]. Thus we need to double the size of the key for the same level of security. It is speculated that it can break DES(symmetric-key algorithm) which relies on its 56-bit key within 185 searches! Though not as fast as Shor’s it can be used to break symmetric key encryption schemes(eg: AES) in the post-quantum world. The only known way to prevent this is by increasing the size of the key which results in exponentially increasing the difficulty to find crack it!

Asymmetric Encryption

Asymmetric cryptography or public-key cryptography is an encryption system where keys come in pairs in the form of a public key and a private key. The public key can be obtained by anyone with enough privileges however the private key is known only to a few select people. Bob can encrypt his message using the public key and send it through a secure channel to Alice. Alice then uses her private key only known to her to decrypt the message. As the private key is only known to her it makes this encryption resilient to Man in the Middle and other types of crypto attacks. However, the main use of Asymmetric encryption is Digital certificates. Alice can sign a document with her private key and Bob can use the public key to verify the document. Symmetric cryptography is a cryptosystem where the same key is used to encrypt as well as decrypt the message. Hence if the key is leaked/compromised during the key exchange the whole system is compromised. To prevent this asymmetric cryptography is used during the key exchange(eg: Diffie Hellman Key Exchange during E2EE). The security of these encryption methods lies on the premise of one-way functions that are easy to calculate but computationally hard to invert. The main one way functions asymmetric cryptography depends on are:

Integer Factorization:

The difficulty of RSA and many other asymmetric crypto algorithms are based upon the difficulty of finding integer prime factors of very large numbers. Rivest, Shamir, and Adleman came up with a general-purpose solution called the RSA algorithm for public-key encryption systems in 1978.

The premise of the algorithm lies in the equation:

mᵉᵈ mod n ≡ m

Thus RSA relies on a periodic function to give us the message back with period ed(Order of the cyclic group). The numbers e and d are coprime obtained from phi(n) in the algorithm where n is the product of very large coprime numbers which are computationally impossible to factor [8].

Encryption: c = mᵉ mod n
Decryption: m = cᵈ mod n

Hence we require the period to crack the encryption and decryption.

Discrete log:

The difficulty of Diffie Hellman key exchange and ECC(Elliptic curve cryptography) are based upon the difficulty of finding solutions to the discrete log problem. Given an equation [8]:

gʳ = x mode p
r = (log𝓰(x)) mod p

Where the integer r is called the discrete log of x to the base g which is very hard to compute given large parameters.

How does Diffie Hellman work?

Alice and Bob choose a prime p and a number g which is primitive modulo root of g
Alice chooses a secret integer a and does A = gᵃ mod p and sends A to Bob
Bob chooses a secret b and finds B = gᵇ mod p and sends B to Bob
Alice computes s = Bᵃ mod p
Bob computes s = Aᵇ mod p
Thus the secret key s is exchanged as s = gᵃᵇ mod p is generated during the operation A*B = (gᵃ)ᵇ mod p

The above equation can be written as [8]

c = gᵃ mod p

If we know the period we can get back the cipher c after multiplying g (the message) a times. Modifying the equation we get:

f(x,y) = gˣ cʸ mod p

It will have two periods as follows [7]:

f(x+p,y) = f(x,y)
f(x+a,y-1) = f(x,y)

The second equation results because multiplying g with c again increases its power by a but it is negated by subtracting 1 from y which essentially removes a factor of c or is the same as dividing by c.

Why does Shor’s Algorithm break these systems?

In both the problems mentioned above, we need to find the period of the function to get back the original message. For RSA we can factor n using Shor’s algorithm to find p and q. Once we have p and q and e(public key) we use Extended Euclid’s algorithm to find d. Though not seen right away, DLP is essentially an integer factorization problem at its core and solving it solves DLP and vice versa. For DLP Shor’s algorithm converts the factoring problem into a period finding problem, and the quantum speedup lies in the finding the period using quantum Fourier transform as mentioned above [7].

Hashing(A Refresher)

Hash-based functions are one-way functions that can map data of any arbitrary size to a fixed-length hash value. These include MD5, SHA-0, SHA-1, RIPEMD-160 etc. Their desired properties are [4]:

Collision resistance: It should be hard to find two messages m1 and m2 having the same hash values, i.e h(m1) = h(m2)
Preimage resistance: For a given hash value H it should not be possible to find the message m where h(m) = H
Second Preimage resistance: Given a message m it should be impossible to find another message with the same hash value as m, i.e m1 ≠ m2 and h(m1) = h(m2)

Threats to Hashing

Birthday paradox

In a room of 23 people, there is approximately a 50 percent probability that at least two people have the same Birthday. This may seem surprising but we have still not fathomed a surprising fact. In a room of 75 people, there is a 75 percent probability that two people share the same birthday! You may be perplexed! How is that possible. Not digressing further the probability that two people hare the same birthday is 1/365 assuming even distribution(Actually most babies are born in the summer). The probability they don’t share the same birthday(D) is:

P(D) = 1-P(S)

where P(S) is the event where they share the same birthday.

P(D) = 364/365 = 0.99720

which is almost 99.7% percent. Extrapolating for the event D where 3 people have different birthdays

P(D) = 1-(364/365).(363/365)…

The explanation for this is the first person has his birthday decided for one day among the 365. The second person avoids that day and selects among the remaining 364 hence the probability of 364/365. Similarly, the 3 person avoids both these birthdays and chooses among the remaining 363 resulting in a probability of 363/365.

P(S)=(364/365).(363/365)
P(D)=1-P(S)

For 23 people

P(D) = 1 -(364/365).(363/365).(362/365)…(343/365) ≈ 0.492703

For 75 people

P(D) ≈ 99.9%

Alternatively, we can find all the possible pairs and find the probability they don’t share a birthday and then multiply all these combinations together. The possible combinations of handshakes will be ²³C₂.

P(75) = (364/365)²³ᶜ₂ ≈ 99.9%

Where P(n) is the number of people not sharing birthdays. Thus by the theory of probability, there is a higher likelihood of a hash collision by performing fixed degree permutations on the input as opposed to random attack attempts. Here we make a logical fallacy by assuming the events are not independent. If A and B have the same birthday and B and Chave the same birthday implies A and C have the same Birthday i.e they are not independent. However, if the sample sizes large it is not a bad approximation. Now we will try to simplify the expression.

P(n) = 1.(1–1/365).(1–2/365)…

For small values of x, we can take an approximation of the first-order Taylor series. for x ~ 0, eˣ = 1+x so,

1–1/365 ~ e⁽⁻¹/³⁶⁵⁾

Simplifying further:

P(n) = 1.e⁻¹/³⁶⁵.e⁻²/³⁶⁵…
P(n) = e⁽⁻¹⁻² ⁻³ ⁻⁴…⁾/³⁶⁵
P(n) = e⁻⁽⁽ⁿ⁽ⁿ⁺¹⁾/²⁾/³⁶⁵⁾

Here 365 is the number of different possible birthdays. Generalizing for a possible set H of probabilistic outputs and n inputs to the hash function we get:

P(n) = e⁻⁽ⁿ⁽ⁿ⁺¹⁾/²ᴴ⁾

1-P(n) = P(minimum number of inputs chosen uniformly randomly to have the same hash value) = P(N)

P(N) = 1-P(n)

Converting equation in terms of N [3]:

P(N) = 1-e⁻⁽ⁿ⁽ⁿ⁺¹⁾/²ᴴ⁾
ln(1-P(N)) = -(n(n+1) / 2H )
2.H.ln(1-P(N)) = -n²-n
Simplifying:
2.H.ln(1-P(N)) = -n²
2.H.ln(1-P(N)) = n²
n = √2.H.ln(1/(1 — P(N))

for a probability of 0.5 collisions where P(N) = 0.5 [3],

n ≈ 1.774√h

For a 64 bit hash, there are approximately 10 ¹⁹ outputs. If all these outputs are equally probable then it will take approximately 5.(10 ⁹) tries to get a hash collision. This same principle can be used in digital certificates where a man in the middle can intercept the message, change its content to generate a fake certificate and then change redundant Unicode characters like comma, space, etc causing uniform random permutations without changing the content with the birthday paradox to get a hash collision in O(2ⁿ/²) [3]time.

Rainbow Tables

In simple terms, a rainbow table is a dictionary of plaintext passwords and their pre-computed hash values. Hash values can be searched to find possible preimages i.e the plaintext passwords to break the encryption. Unlike a brute force attack that manually searches for collisions, a rainbow table has many possible plaintexts for a range of hashes. The exact preimage is not needed to be known as the hash will always be the same in the case of cracking passwords. However, it can easily be prevented by salting the input, i.e adding a random value with the input.

Grovers Algorithm

According to the aforementioned subsection, Grover’s algorithm can search an unsorted database of size n in O(√n). A hash function outputs a fixed-length message digest for any input message. Hence like symmetric encryption it also suffers from the risk of Grover’s algorithm being utilized to search for a collision in √n steps where n is the size of the message. It can be coupled with a birthday paradox resulting in an even stronger attack requiring 3n bit output for n bit security [1].

Hashing Algorithms

MD5

MD5 stands for message digest 5 is a hashing algorithm and a successor to MD4 [5]. It was once a popular algorithm mainly used to create salted database passwords and as a checksum to check for data integrity because of its low computational time. It produces a 32-byte digest. However today it is regarded as highly compromised due to its low collision resistance. Low powered off-shelf GPU’s can be used to generate millions of hashed in seconds and particular prefix attacks and can generate collisions in seconds for fixed prefix inputs. It is now deemed unfit for use and is replaced by better algorithms like SHA-3. It is also vulnerable to rainbow tables, Grover’s algorithm, and birthday paradox making its security almost non-existent.

SHA-1

The SHA-1 Hash stands for secure hashing algorithm 1 and is a crypto-based hash function which takes any sized input to produce a fixed 160-bit length or 20-byte output. It was designed by NSA and later adopted by the tech industry as a de facto security standard for SSL, TLS, SSH, etc, and for ensuring data integrity in git version control systems. It was made to cover the loopholes in md5 and is slower than md5. This is a good thing as a slower hash function takes a long time to crack but on the other hand, also takes a longer time in trivial data integrity processes. This results in a trade-off between speed vs security. So how does sha1 work? In an abstract sense, SHA-1 is a looping function that takes 512 blocks at a time(message blocks) and changes the internal state each loop. Once we have consumed the file we read the updated internal state which gives us the final hash value. The internal state of SHA-1 is h0- h1-h2-h3-h4- h5 which are five 32 bit words equal in length to the message digest. So in the first step, we have an initial state h1…h5 as mentioned above. Now the message block is consumed by a compression function that does many complex bitwise operations, like shuffling rotation, etc to randomize the bits and create a one-way state. This is repeated for 80 rounds(times) until we get a new state h0'-h1'-h2'-h3'-h4'-h5'. The initial state is added with the new state to form the final state. As this function does the same set of operations each time, we get the same hash output each time. It is almost impossible to reverse-engineer the process to get back the message due to the randomized and complex bitwise operations. Most of the hashing functions make use of the Merkle-Dåmgard structure. The concept of this structure is that if we can make a one-way hash function for a small input size it be interpolated to an input of any size by hash chaining [5].

Breaking SHA-1

SHA-1 is a very complicated algorithm hence using brute force to break it is impossible. Various cryptanalysis based methods were used to break SHA-1. The main method used is a differential attack. Here the analysts use multiple messages to see how the bits are moved, swapped, and changed to find a trend and track the differences called message differential path. In sha1 researchers have been able to figure this out till the 24 steps/rounds. Beyond that, they use powerful GPUs to predict the outputs due to unpredictability. There are mainly two attacks that are carried out with the help of this, Two Collision Block, and Fixed Prefix attack [7].

SHA-2 Family

Although SHA-1 was a very strong algorithm an attacker with enough resources(computing power) and the right tools could still break SHA-1. SHA-2 is a family of hash functions mainly known for the 256 bit and 512 version called sha256 and sha512 respectively along with the truncated versions of 224, 384 bits. SHA-2 generates a longer message digest effectively increasing its security. However, this is not the only aspect it improves on. The number of rounds is changed and improvements are made to them by using different additive constants and shift amounts in the compression function. These changes were made by the NSA to bury the loopholes posed by the previous generation of SHA algorithms. The best preimage attacks have only been able to break 52 out of the 64 rounds of SHA-256 making it uncracked to date [5] [6].

Google had announced in 2017 that they were able to successfully carry out a second preimage attack on SHA-1 essentially compromising its security, Along with this attack there have been many others who were able to break it and reduce its security to below 80 bits. We already know we can use Grover’s algorithm to half the bit security of any hashing algorithm. This combined with all the previous cryptanalysis techniques we have told, effectively renders SHA-1 crackable. The security of SHA-1 lies in its compression function. Many cryptanalysts were able to capitalize on the shortcomings of the functions to find loopholes to crack SHA-1. Although SHA-2 is safe against current attacks it is not safe against post-quantum algorithms. Currently, Grover’s algorithm with birthday paradox can reduce the strength of a 256-bit SHA hash to about 256/3 ≈ 85 bits of security [1]. A signature that provides the security of 80 bits and above is considered safe because of computationally inefficiency to crack it. In the future, better algorithms and crypt analytical methods may be used to crack the sha2. However, sha512 with a longer output will remain immune to quantum algorithms as of now until a better method is proposed. Similarly, SHA-3 having a Keccak based approach is a stronger version of sha2 that was standardized by NITS in 2015. It is also quantum-proof for large outputs [6].

So in the previous sub-sections, we laid the foundations for some of the post-quantum algorithms of interest, their need, and the basics of hashing. In the next post, we will cover hash-based signatures schemes and their post-quantum counterparts in depth.