Post Quantum Cryptography – The Basics

Post-quantum cryptography aims to find schemes that can withstand an attack from a quantum computer. This is becoming an increasingly important field of research as the development of quantum computers intensifies and current cryptography schemes relying on the difficulty of factorisation can be broken in polynomial time by these quantum computers. So, researchers have tried to find other ‘hard’ problems in mathematics (take exponential time to solve) that can be exploited to create classical crypto schemes that withstand attack of quantum computers (at least for now).

In general post-quantum schemes require more resources compared to traditional cryptography, in particular Elliptic Curve cryptography; security against quantum computer attacks come at a cost. There are four different families of post-quantum schemes that are considered to be the best candidates, and in this blog post I will briefly discuss each of them.

Code-Based Cryptography

Traditionally, error-correction codes are used to detect and correct bit errors when messages are transmitted over an unreliable channel. The code can be chosen to fulfil the requirements of the channel; in particular the number t of correctable bit errors can be determined.

Decoding arbitrary codes is computationally hard and can be infeasible depending on the code parameters. However, there are specific codes for which efficient decoding algorithms are known. So in practice only such codes are used that have efficient decoding algorithms.

The main security assumption of code-based cryptography is the difficulty of decoding a random linear code. Even with quantum computers, only exponential-time algorithms are known.

The first code-based public key crypto system was proposed by McEliece in 1978 and has not been fundamentally broken since, however the main problem with this is the size of the keys: it requires key sizes of about 4MB in order to achieve post-quantum security. Niederreiter introduced a scheme that gave some improvements to the encryption and decryption cost and required smaller keys.

There have been many attempts to reduce key sizes by using different codes that have some redundant structure in the public key. But this structure has led to efficient classical attacks on the crypto-systems. 

There are also signature schemes, hash functions and random number generators based on code-based cryptography. 

Lattice-Based Cryptography

The underlying ‘hard’ problem is the shortest vector problem (SVP): a basis of a vector space V and a norm N are given for a lattice L and one must find the shortest non-zero vector in V, as measured by N, in L. It is believed that the SVP is computationally hard even for quantum computers.

NTRUEncrypt is a commercial public key encryption scheme based on lattices. Public key sizes of about 1.5kB to 2kB are required in order to achieve the desired security. Note that these are the requirements based on the algorithms that have (up to today) been developed to solve the SVP. These restrictions are called ‘parameters’.

Closely related is the signature scheme NTRUSign. However, the security of this is not yet well understood and so there are no recommendations for these signature schemes for post-quantum security.

There are also key exchange protocols that are built on lattice-based cryptography, such as NewHope that has been experimentally adopted by Google. NewHope is not symmetric and needs two rounds of agreement (unlike the Diffie-Hellman Key Exchange). Also, it does not include authentication, so this needs to be achieved by other means.

By switching to post-quantum key exchange now, an attacker in the future does not learn encryption kets even if he breaks long-term authentication keys. Therefore, combining a post-quantum key exchange with a classical authentication scheme provides a cost effective long-term secure authenticated key exchange for the interim period until all cryptographic primitives have been transitioned to post-quantum secure schemes.

Hash-based Cryptography

Hash functions are one-way functions tha tmap bit strings of an arbitrary length to relatively short, fixed length bit strings called hash values. There are three required properties:

  • Pre-image resistance: must be hard to compute a pre-image of a hash value i.e. a bit string that once hashed results in a given hash value.
  • Second pre-image resistance: given a bit string, it must be hard to find a different bit string that has the same hash value.
  • Collision resistance: it must be hard to find two arbitrary bit strings that have the same hash value.

Since by definition it is not computationally feasible to compute the inverse of a hash function it is not known how to construct public-key encryption schemes using hash functions. However, it is possible to construct signature schemes, where in general the required signature size increases if more signatures for the same public key are needed.

Hash-based signature schemes have been around for a long time and so the estimates of the required parameters to achieve post-quantum security are very reliable.

Multivariate Cryptography

This is based on the difficulty of the MQ-problem: solving multivariate quadratic systems of equations over finite fields is NP hard (no efficient algorithm for solving random multivariate polynomial systems). The difficulty depends on the size of the underlying field, the number of variables and the degree of the system. If the number of equations and variables is sufficiently large then even quadratic equations over a the field with two elements are hard to solve.

For constructing an asymmetric public-key scheme, the public-key itself is a set of multivariate quadratic polynomial and the private key often is the knowledge of a trapdoor that allows to efficiently solve the multivariate system. The construction of the scheme allows the use of systems with more variables than equations, so there may be more that one solution. Any of these solutions is a valid signature.

The confidence in multivariate systems is quite high however a relatively large public key is required. Attempts to reduce key sizes by using few variables over larger fields, but the security of such systems is not well understood. The second approach is to use sparse systems in order to compress the public key, but this often leads to a loss in security. 

For public key encryption, we need the resulting equation system to only have one solution and so we must have an over-defined system i.e. the public key must have more polynomials than variables. Currently there are not many multivariate public-key encryption schemes that are considered secure. 

Multivariate cryptography can also be used for pseudo random-number generators, cryptographic hash functions and symmetric encryption, e.g. the symmetric block gopher QUAD.

What about Elliptic-Curve Cryptography?

I have talked about elliptic curve cryptography in previous blog posts, so why isn’t this mentioned?

Due to the novelty of these cryptographic schemes there is not great confidence in them yet. So they are not currently consensually considered as candidates for post-quantum public-key encryption. 


This is the first installation in my series about post-quantum cryptography. Anything you want me to talk about in particular? M x

Is the COVID-19 Tracing App secure?

There has been a lot of talk about the COVID-19 tracing app that has been recently released. The simple premise is that the app will use Bluetooth signals to log on when smartphone owners are close to each other, so if someone develops COVID-19 symptoms, an alert can be sent to other users they may have infected. However, countries and organisation developing the apps have opted for two different types of systems to achieve this: centralised systems or decentralised systems. First, I will what these are in general.

Centralised Systems

Centralised systems rely on a single server as a core distribution centre in the communication with end users. From a functional perspective they often imply that each entity involved in the software stream has a specific, distinct role. For example, when streaming a movie on Netflix, Netflix’s central server provides the video; the user consumes it. However, this also means that if the central server is compromised, the entire network is.

Decentralised Systems

Decentralised systems eliminate the need for a central entity and rely on multiple servers or end-user devices to cooperate and undertake a given task. Each of these entities is tasked with a similar role. These systems are not a novel concept and in fact there are a vast array of places in which it has been implemented, such as blockchain technology. Most decentralised systems that preserve privacy focus on ensuring either the confidentiality and anonymity of personal data (such as ‘TOR’) or user control over your personal data (such as the MIT project ‘Enigma’).

In context of COVID-19 Tracing Apps

Centralised contact-tracing apps store a user’s Bluetooth ID in a central database as well as the Bluetooth IDs of phones they have come into contact with (and any other data that’s being collected), enabling better visibility of data by health services or governments.

Decentralised contact-tracing apps only stop a user’s Bluetooth ID (and any other data being collected) in a central database and contact-tracing is done at the phone level, without sharing the information centrally. This allows for stronger data privacy.

Source: BBC News

There is a key trade-off between these two approaches: do we want to maximise data availability to health services or do we want to protect privacy of individuals? Furthermore, should it be up to individual governments or companies to make this choice? This is especially important as these two systems don’t interact well with each other, meaning that the fact that various countries are opting for different systems may prove disastrous for allowing tracing across borders and so quarantine rules may have to stay in place even with the introduction of the app.

UK App – Apple and Google are involved?

NHS officials initially decided to build a centralised system, but the NHS could not get the same accuracy as if it was using Apple and Google’s software. The second version of England’s app uses Apple and Google’s technology and opts for the decentralised approach.

The ecosystems of Apple and Google are fundamental to the NHS app. The app uses the Apple and Google system to conduct the Bluetooth contact tracing. This is achieved through an API and require some of the latest versions of the Android and iOS operating systems to run. The companies have favoured the method that puts people’s privacy at the forefront in order to stop the technology from being used maliciously.


What are your thoughts on the COVID-19 tracing app? M x

Algorithms: PART 2

Read part 1 here!

QR Algorithm

From 1959-1961, John G.F Francis worked on finding a stable method to compute eigenvalues and thus created the QR algorithm. Eigenvalues are one of the most essential numbers associated with matrices, however they can be quite difficult to compute.

This algorithm is based on the fact that is relatively easy to transform a square matrix into a matrix that is almost upper triangular (one extra set of no-zero entries just below the main diagonal). Based on QR decomposition, which writes a matrix A as a product of an orthogonal matrix Q and an upper triangular matrix R, the QR algorithm iteratively changes Ai = QiRi to Ai+1RiQi

“The algorithm is numerically stable because it proceeds by orthogonal similarity transforms.”

-Wikipedia

Under certain conditions, the matrices Ai converge to a triangular matrix and the eigenvalues of a triangular matrix are listed on the diagonal so the eigenvalue problem is solved.

By the mid-1960s, the QR algorithm had turned once-formidable eigenvalue problems into routine calculations.

Quicksort

The Quicksort algorithm was developed by Tony Hoare in 1962. It puts N things in numerical or alphabetical order by using a recursive strategy:

  1. Pick one element as a pivot
  2. Separate the rest into piles of big and small elements, as compared with the pivot
  3. Repeat this procedure on each pile

Although you can get stuck doing all N(N-1)/2 comparisons, on average Quicksort runs on average with O(N logN) efficiency, which is very fast. Its simplicity has made Quicksort a “poster child of computational complexity“.

Fast Fourier Transform

The fast Fourier Transform was developed by James Cooley and John Tukey in 1965. The FFT revolutionised signal processing. Although the idea can be traced back to Gauss, it was a paper by Cooley and Tukey that made it clear how easily Fourier transforms can be computed. It relies on a ‘divide-and-conquer‘ strategy and hence reduces it from an O(N^2) to an O(N logN) computation.

Integer Relation Detection Algorithm

Given real numbers x1, …, xn, are there integers a1, …, an (not all 0) for which a1x1 + … + anxn = 0? Helaman Ferguson and Rodney Forcade found an algorithm – the Integer Relation Detection Algorithm – to answer this question. This is easily solved in the case where n = 2 by Euclid’s algorithm, computing terms in the continued-fraction expansion of x1/x2 – if x1/x2 is rational, then the expansion terminates.

The detection algorithm has, for example, been used to find the precise coefficients of the polynomials satisfied by the third and fourth bifurcation points of the logistic map.

Logistic Map | Source: geoffboeing.com

It has also proved useful in simplifying calculations with Feynman diagrams in quantum field theory.

Fast Multipole Algorithm

This algorithm overcomes one of the biggest problems of N-body simulations, which is the fact that accurate calculations of the motions of N particles interaction via gravitational or electrostatic forces seemingly requires O(N^2) calculations, i.e. one for each pair of particles. This algorithm, developed in 1987 by Leslie Greengard and Vladimir Rokhlin, does it with O(N) computations.

How does it do this? It uses multipole expansions to approximate the effects of a distant group of particles on a local group. Then we define ever-larger groups as distances increase. One of the big advantages of the fast multipole algorithm is that it comes with rigorous error estimates, a feature that a lot of other methods lack.

M x

10 Algorithms: PART 1

Click to access 637.pdf

Monte Carlo Method

At the Los Alamos Scientific Laboratory,  John von Neumann, Stan Ulam and Nick Metropolis created the Metropolis algorithm, also known as the Monte Carlo method. This algorithm obtains approximate solutions to numerical problems that has an unmanageable number of degrees of freedom and to combinatorial problems that have factorial size. It does this by mimicking a random process.

Read more here.

Simplex Method

In 1947, George Dantzig created the simplex method for linear programming. Linear programming dominated the world of industry, where “economic survival depends on the ability to optimise within budgetary and other constraints“. It’s widespread application makes Dantzig’s algorithm one of the most successful of all time.

The simplex method is a elegant way of arriving at optimal answers, and in practice it is highly efficient.

Krylov Subspace Iteration Methods

The development of the Krylov Subspace iteration methods was initiated by Magnus Hestenes, Eduard Stiefel and Cornelius Lanczos from the Institute for Numerical Analysis at the National Bureau of Standards in 1950. They address the simple task of solving the equations Ax = b. Although these seem simple, when A is a massive nxn matrix, the algebraic answer x = b/A is not easy to compute!

So, iterative methods, such as solving equations of the form Kxi + 1 = Kxi + b – Axi, were introduced.  This lead to the study of Krylov subspaces, which are named after Russian mathematician Nikolai Krylov. These subspaces are spanned by powers of a matrix that is applied to a initial remainder vector r0 = b – Ax0.

Lanczos found a way to generate an orthogonal basis for such a subspace when the matrix is symmetric, and then Hestenes and Stiefel proposed an even better method – conjugate gradient method – used when the system is both symmetric and positive definite.

Fortran Optimising Compiler

Developed in 1957 by a team at IBM lead by John Backus, the Fortran optimising compiler is said to be one of the most important innovations in the history of computer programming. After its development, scientists could tell a computer what they wanted it to do without having to “descend into the netherworld of machine code“.

Fortran I consisted of 23,500 assembly-language instructions, and although this is not a lot compared to modern compilers, it was capable of a great number of sophisticated computations.

The compiler “produced code of such efficiency that its output would startle the programmers who studied it.” 

– Backus

Part 2 coming soon! M x

Knapsack Problem

The knapsack problem is a problem in combinatorial optimisation.

Imagine you are going to visit your friends for whom you have bought lots of presents. So many, in fact, that you can’t fit them all in your luggage meaning you must leave some behind. If we decide to pack a combination of presents with the highest value but that doesn’t exceed the weight limit imposed by airline, how can we find such a combinations? This is the Knapsack Problem.

File:Knapsack.svg
Source: Wikipedia

We could solve this by trying all the possible combinations, calculating their value and weight and then picking one that is below the weight limit but maximises the value. Whilst this is okay when we are dealing with a small number of items, it is simply unfeasible when the number of items is large as the number of combinations is too big. So, is there an algorithm which can work for any number of items that doesn’t take too long?

Computer scientists have a way of measuring the complexity of a problem by how fast the time taken grows as the size of the input increases. Polynomial growth, i.e. if the size of the input is n then the time taken grows by a factor of n^k, describes and ‘easy problem’; the growth is nowhere near as “explosive” as  exponential growth, e.g. 2^n.

Whether or not a polynomial time algorithm exists to solve the knapsack problem is unknown, meaning it is in a class of problems called NP-Hard Problems.

Complexity classes
Source: plus.maths.org

Complexity Classes:

  • Class P: problems that can be solved in polynomial time
  • Class NP: a potential solution can be checked in polynomial time
    • NP-Complete: within the NP class but particularly hard
    • NP-Hard: as least as hard as the NP class.

It is possible that the NP class = P class, though this is still unknown (and is one of the Millennium Prize Problems), hence the two diagrams above.

M x

P.S. My posts may be more sporadic in the next month because I’m in exam term!

The Josephus Problem

The Josephus Problem is a problem in computer science based on a counting-out game. The problem is named after Flavius Josephus, a Jewish-Roman historian from the 1st century, who tells the story like this:

“A company of 40 soldiers, along with Josephus himself, were trapped in a cave by Roman soldiers during the Siege of Yodfat in 67 A.D. The Jewish soldiers chose to die rather than surrender, so they devised a system to kill off each other until only one person remained. (That last person would be the only one required to die by their own hand.)

All 41 people stood in a circle. The first soldier killed the man to his left, the next surviving soldier killed the man to his left, and so on. Josephus was among the last two men standing, “whether we must say it happened so by chance, or whether by the providence of God,” and he convinced the other survivor to surrender rather than die.”

This story gives rise to an interesting maths problem: If you’re in a similar situation to Josephus, how do you know where to stand so you will be the last man standing?

M x

The Halting Problem

To understand the process of computation, regardless of the technology available, we need to reduce it to its most basic elements. One way to model computation is to consider an input, operated on by a program which produces some output.

In 1936, Alan Turing constructed such a model and considered the question of determining whether a program will finish running or will continue to run forever i.e. halt. This is known as the Halting Problem.

Let us suppose that we write a program, let’s call it HALT, that, given another program and its associated input, can determine whether running that program with the input will halt or not. This can be represented in the following way:

\[  \mbox{\textbf{HALT}(program,input)}=\left\{  \begin{tabular}{l}\mbox{Output YES, if the program does halt on the input,}

\\ \mbox{Output NO, otherwise. } 

\end{tabular}  \]

Note that we do not have to consider how this program works, it is merely sufficient to assume that there does exist such a program. Now, consider a new program, call it OPPOSITE which does the opposite of halt. In other words, it analyses programs running with themselves as the input, acting in the following way:

\[  \mbox{\textbf{OPPOSITE}(program)}=\left\{  \begin{tabular}{l}\mbox{Halt, if \textbf{HALT}(program, program) returns NO, }

\\ \mbox{Loop forever, otherwise. } 

\end{tabular}  \]

Now, what happens when we run OPPOSITE on itself?

If OPPOSITE(opposite) halts, then it must loop forever, but if it loops forever then it must halt. Hence, there is a contradiction, highlighting how the program HALT cannot exist.

This was an incredible result. Firstly, in this proof a computer and a program were mathematically defined, paving the way to the creation of the Turing Machines. Furthermore, Turing had found a program whose existence is logically impossible, and showed that knowing whether a program halts on some input is undecidable.

“It is one of the first examples of a decision problem.”

I have included a video by Computerphile which I think describes the problem and proof very well:

M x

NEWS: World’s Largest Proof

Recently, a trio of mathematicians – Marijn Heule from the University of Texas, Victor Marek from the University of Kentucky, and Oliver Kullmann from Swansea University – have solved a problem in mathematics and the solution takes up 200 terabytes of basic text (just consider the fact that 1 terabyte can hold 337,920 copies of War and Peace)! This breaks the previous recorded of a 13-gigabyte proof, which was published in 2014.

The mathematics problem is named the ‘Boolean Pythagorean Triples problem’, and was posed by Ronald Graham in the 1980s, who offered a $100 prize for the solution.

The problem is part of Ramsey theory and asks:

“Is it possible to colour all the integers either red or blue so that no Pythagorean triple of integers a, b, c, satisfying a^2+b^2=c^2 are all the same colour. For example if you would colour a and b red, and c blue, this would successfully not satisfy the tested triple, but all triples would have to be tested.”

Andrew Moseman from Popular Mechanics details how:

“What makes it so hard is that one integer can be part of multiple Pythagorean triples. Take 5. So 3, 4, and 5 are a Pythagorean triple. But so are 5, 12, and 13. If 5 is blue in the first example, then it has to be blue in the second, meaning either 12 or 13 has to be red.

The proof found that it is only possible to colour the numbers in such a way up to the number 7,824 and that 102,300 such colourings exist. Hence, there is no solution to the problem question. The proof took a supercomputer two days to solve, and generated 200TB of data!

The paper describing the proof was published on arXiv on the 3rd of May 2016.

Although the computer has proved that the colouring is impossible, it has not provided the underlying reason why this is, or explored why the number 7,824 is important. This highlights the objection to the value of computer-assisted proofs; yes, they may be correct, but to what extent are they mathematics?

Sources: 1 | 2

Let me know what you think of computer assisted proofs below! M x

Boolean Algebra

Today I thought I would give you a short introduction on Boolean Algebra.

George Boole color.jpg
George Boole

Boolean Algebra was named after the English mathematician, George Boole (1815 – 1864), who established a system of logic which is used in computers today. In Boolean algebra there are only two possible outcomes: either 1 or 0.

It must be noted that Boolean numbers are not the same as binary numbers as they represent a different system of mathematics from real numbers, whereas binary numbers is simply a alternative notation for real numbers.

Operations

Boolean logic statements can only ever be true or false, and the words ‘AND’, ‘OR’ and ‘NOT’ are used to string these statements together.

OR can be rewritten as a kind of addition:

0 + 0 = 0 (since “false OR false” is false)
1 + 0 = 0 + 1 = 1 (since “true OR false” and “false OR true” are both true)
1 + 1 = 1 (since “true OR true” is true)

OR is denoted by:

Screen Shot 2016-05-04 at 5.49.41 PM.png

AND can be rewritten as a kind of multiplication:

0 x 1 = 1 x 0 = 0 (since “false AND true” and “true AND false” are both false)
0 x 0 = 0 (since “false AND false” is false)
1 x 1 = 1 (since “true AND true” is true)

AND is denoted by:

 Screen Shot 2016-05-04 at 5.49.36 PM.png

NOT can be defined as the complement:

If A = 1, then NOT A = 0
If A = 0, then NOT A = 1
A + NOT A = 1 (since “true OR false” is true)
A x NOT A = 0 (since “true AND false” is false)

This is denoted by:

Screen Shot 2016-05-04 at 5.49.45 PM

Venn diagrams these operations | Source: Wikipedia

Expressions in Boolean algebra can be easily simplified. For example, the variable B in A + A x B is irrelevant as, no matter what value B has, if A is true, then A OR (A AND B) is true. Hence:

A + A x B = A

Furthermore, in Boolean algebra there is a sort of reverse duality between addition and multiplication, depicted by de Morgan’s Laws:

(A + B)’ = A‘ x B‘ and (A x B)’ = A‘ + B

Uses

 

In 1938, Shannon proved that Boolean algebra (using the two values 1 and 0) can describe the operation of a two-valued electrical switching circuit. Thus, in modern times, Boolean algebra is indispensable in the design of computer chips and integrated circuits.

Sources: 1 | 2 | 3