NIST (National Institute of Standards and Technology)-recommended crypto- graphic algorithms are approved after intense security analysis. This is an ongoing process where each algorithm is constantly being examined. Three classes of ap- proved algorithms are used: Hash functions; symmetric-key algorithms; asymmetric- key algorithms.

In 2017 NIST began the process of trying to select new cryptographic algorithms to augment already widely accepted schemes. One of the main aims of introducing these new schemes is to deal with the challenges of modern and near future security.

A new generation of security issues has begun with the rapid adoption of the internet of things (IOT). There are more connected devices than people on the planet. We are currently playing catch up trying to secure these devices. The problem is getting worse as the rate at which IOT is being adopted increases.

It was suggested in the 70s however that it may be possible to do more than just safely store data; in fact, useful operations could be performed on encrypted data [Rivest et al. (1978)]. This concept is known as homomorphic cryptography. Since the idea was presented, homomorphic encryption has been through a few evolutions [Acar et al. (2018)]. The first collection of homomorphic encryption methods are known as partial homomorphic encryption. These protocols are homomorphic with respect to a single operation. However, no meaningful computation can be performed using these properties alone.

Somewhat homomorphic cryptosystems are a class of cryptosystems that have encryption functions that are only approximately homomorphic. The problem here is that the errors in the approximations accumulate so that only finitely many operations are possible without the data becoming irretrievably corrupted. One of the advantages of these systems is that some allow both addition and multiplication to be performed on ciphertexts. In [Naehrig et al. (2011)] a somewhat homomorphic cryptosystem that takes advantage of the Ring Learning with Errors problem is presented.

The next important advance was the development of fully homomorphic encryp- tion systems. An encryption scheme is called fully homomorphic if we can perform as many operations of our choice on ciphertexts as we need. In the last 10 years, a few of these methods have been proposed [Acar et al. (2018)].

• The first of these methods is Gentry’s lattice-based scheme. To begin with, Gentry started with a somewhat homomorphic encryption scheme and developed a method to deal with the noise that comes with such schemes. This method came in two steps, first was known as squashing that reduces the degree of the ciphertexts to a point that the second step can handle. 

• The second step is known as bootstrapping which safely re-encrypts the data, resetting the error to the desired amount. Moving forward with the idea of a bootstrapping method, a new fully homomorphic encryption method was suggested, but this time set in the integers [Van Dijk et al. (2010)]. The beauty of this method is that simply being integers is much more conceptually simple.

• The third method is based on the ring learning with errors problem. The set- ting for this scheme is in Rq = Zq[x]/(f(x)), the ring of polynomials modulo some polynomial f with coefficients in Zq. This scheme, discussed in [Lyubashevsky et al. (2010)], has drawn a lot of attention due to two major factors. First, the learn- ing with errors problem is thought to be very difficult to solve even in a post-quantum world. Secondly, ciphertexts are relatively small a very impor- tant aspect of considering how quickly ciphertexts can grow when multiplication is performed.

A new threat to the world of security is quantum computing; which is quickly being accepted as a reality, not only in most of our lives but potentially in the next decade [Easttom (2017)]. In conventional computing, information is stored as a sequence of bits, each of which is a 0 or 1. Quantum computing in a similar sense deals with information that is stored as a sequence of qubits, each of which is 0, 1, or a quantum superposition of the two. When it comes to physically observe a qubit, a measurement is performed, and if in a superposition, the qubit will collapse down to either a 0 or 1. Although there is an infinite number of combinations of superposition for a qubit, an important restriction of quantum computing is that it is physically impossible to store a qubit in a superposition. This means that there is no increase in efficient storage compared to classical computing. One of the key areas where quantum computing does outperform classical is its speedup of various algorithms. One of the earliest examples of this is the Deutsch-Jozsa algorithm [Deutsch & Jozsa (1992)]. The algorithm solves the problem of determining if a function that outputs a single bit is constant or balanced (outputs a 0 for half its inputs and a 1 for the other half). In the classical version, a number, exponential in the size of the input, total queries to the function are required to solve the problem. However, the quantum Deutsch-Jozsa algorithm only requires a single query. This example of an exponential speedup is the motivation for quantum attacks in cryptography.

While considered secure from all known conventional attacks, integer factoriza- tion, discrete log, and elliptic curve methods each have been subject to efficient quantum attacks, for example the well known Shor’s algorithm [Shor (1994)] for solving the discrete logarithm problem. It is uncertain when access to a quantum computer will be available but, as already stated, many believe it to be in our life- time. As such alternative ”quantum-resistant” methods need to be kept in mind  and ready to go as soon as possible. Fortunately, while old methods may become obsolete, this emerging area of computing has already proven to bring with it new possibilities. Random numbers are required in many security methods. Unfortu- nately in classical computing, we aren’t able to generate genuine random numbers. We, therefore, have to rely on pseudorandom numbers which are generated from some algorithm. On the other hand, a qubit can be set up in a superposition of 0 or 1 where, after performing a measurement, there is an even chance of observing the 0 or the 1. Assuming no one has tampered with this qubit, this measurement will be truly random. Security initiatives in quantum computing therefore no longer need to worry about an attacker having malicious access to the pseudorandom number generator. There is still cause for concern with issues such that the qubits may still be tampered with, however, research has gone into testing for such malicious activity [Colbeck & Kent (2011)].

One of the most high profile cryptographic methods to emerge from quantum computing so far is the BB84 protocol [Shor & Preskill (2000)]. The symmetric key algorithms mentioned earlier, require two or more parties to have knowledge of a shared key that should be unknown to anyone else. Key exchange methods already exist in classical computing that makes this possible, however, many of the more well-used versions rely on the discrete log and other problems that we have already mentioned will become insecure in quantum settings. Alternatively, the BB84 protocol performs the key exchange and bases its security on the fundamental principles of quantum mechanics. The reason the scheme works is due to the fact that taking a measurement of a qubit requires a choice of basis in which to measure in. This is the secret that the parties looking to exchange keys don’t tell anyone. An eavesdropper can’t know what the choice of basis was used so an attempt to read the key has a non zero probability of altering the key in a noticeable way.

Lattice-based methods are based on a different difficult problem and are one of the front-runner candidates for cryptosystems in a quantum world. In particular, the NTRUEncrypt public key cryptosystem has accumulated a lot of interest since its initial development towards the end of the 90’s [Pecen et al. (2014)], in partic- ular two NTRU schemes have made it to the second round of NIST post-quantum competition earlier [Alagic et al. (2019)]. Another example of a lattice-based pro- tocol is the GGH (Goldreich-Goldwasser-Halevi) encryption scheme [Goldreich et al. (1997)]. This is an example of the somewhat homomorphic encryption meth- ods where the number of operations (in this case addition) that can be performed correctly is restricted by an error component. Although many schemes have these error terms, this one, in particular, has an error that can be easily represented by a random walk [Spitzer (2013)]. Because of this, after a given number of additions have been performed on a ciphertext, we can create a distribution of the potential accumulative error. Most importantly, there is a finite number of options each of which we know the probability of.

Rings are an appropriate choice of structure for this particular type of scheme due to the plus and multiplication operations available [Kahrobaei et al. (2019)]. They can be built up into more meaningful functions that would enable data analysis. In particular we will be interested in polynomial rings, much like in [Rai (2004)]. The work in [Kahrobaei et al. (2019)] uses rings to build a fully homomorphic encryption scheme using rings and ideals. Much like a lot of the lattice-based methods, encryption is performed by multiplying a plaintext by a secret key followed  by adding a random element. In this scheme in particular a message, m, is encrypted by multiplying by a random private idempotent, r, of a private idea followed by adding a random element, i, of that private ideal i.e. of the form mr + i. Any issue we discuss later is how to form a correct homomorphism. This scheme achieves an additive homomorphism by firstly using the distributive property of multiplying the plaintext by the same random idempotent m1r + m2r = (m1 + m2)r. Secondly the only requirement for the random element added during the encryption is that is an element of the private ideal, a property that will be maintained by adding two ideal elements together. The multiplicative homomorphism is achieved by taking advantage of those two points alongside the fact that r was an idempotent, namely m1r · m2r = m1m2r.

Testing for ideal membership has been used as a difficult problem forming the basis of cryptosystems proposed in rings [Albrecht et al. (2016)]. These protocols are at risk of being broken due to the existence of Gr ̈obner bases. While it is thought to be difficult to establish whether a ring element belongs to an ideal, based on the basis elements of the ideal, a Gr ̈obner basis is constructed in such a way that the problem is easy. Therefore, the security of these categories of schemes is reliant on not being able to find a Gr ̈obner basis.

In commutative polynomial rings it is known that any ideal basis has a corre- sponding Gr ̈obner basis and can be found using Buchberger’s algorithm [Buchberger & Winkler (1998)]. Commutative schemes base their security on the fact that some Gr ̈obner bases take an infeasible length of time to find. We will, however, be looking at a non-commutative scheme in section 4.2, the advantage being some bases for ideals have provably no Gr ̈obner basis. This will be done by looking at examples of where Mora’s algorithm [Mora (1985)] does not terminate. These initial examples will come from [Rai (2004)]. A lot of work in these Polly Cracker systems is based on Gr ̈obner bases that are infeasible to calculate but theoretically finite. Work with infinite Gr ̈obner bases isn’t as prevalent with Rai’s work typically being what is referred to when talking about infinite Gr ̈obner bases, for example in [Bulygin (2005)] and [Cort?es et al. (2007)].

We will use an ideal whose basis can’t be converted into a Gr ̈obner basis. From this we will build a key exchange protocol based on the Polly Cracker scheme that is covered in [Rai (2004)]. We wish to keep any encryption method as computa- tionally inexpensive as possible so the majority of the work will be done by the key exchange (if data is being streamed for example we can’t afford time-consuming en- cryption methods). The accompanying encryption function that will depend on the generated secret key is conceptually very simple. Although the simplicity of it is an excellent feature, two more advantages come with this specific choice of function; the first of which is the homomorphic property. Addition is preserved under the encryption function regardless of which polynomial space we work in. As for mul- tiplication, we discuss how that can also be preserved provided we are a little more careful in our choice of polynomial space. The remainder of this section will focus on our efforts to strengthen the scheme against a potential attack. Braid groups are another structure that have been studied for their cryptographic potential [Flores & Kahrobaei (2017)] and are the justification of the second advantage of our choice of encryption function which we will look at in more detail in section 4.4. Hecke al- gebras are connected to braid groups and having both addition and multiplication operations make it a good candidate for the choice of polynomial space to work in. It will show how we can upgrade our scheme. With this particular setup, the encryption function will output a polynomial that has similar properties to instances of the conjugacy problem from braid groups. This will hopefully give our method an extra level of security from other potential attacks.

Testing of the work can be done using the functional programming language Haskell. Using a language like this is helpful as programs are built up as a series of functions, a more natural way to express the methods we use than an object- oriented language like Java. This approach is of great importance as working with polynomials is much slower than working with integers like a lot of current protocols. In particular, MapReduce method [Dean & Ghemawat (2008)] can be utilised to help speed up operations over large amounts of ciphertexts.

We will study the complexity of finding partial Gr ̈obner bases. Although we will see that there are certain ideal bases that have an infinite number of polynomials in their Gr ̈obner basis, it is only important to find the correct finite subset. We, therefore, will look at the complexity of finding this subset as opposed to finding a complete Gr ̈obner basis.

When it comes to measuring complexity we need to be careful which measure we use. We will use the quicksort algorithm [Hoare (1961)] as an example to understand the various measures. While something like worst-case complexity will tell us if a particular hard problem does have hard instances, it isn’t much use if there is only one or a very small number of examples. It is therefore tempting to use something like average-case complexity which, as the name suggests, will give an indication of on average how hard a type of problem is. The issue here is the fact that in statistics it is well known that the mean value is rather sensitive to outliers. Just one example of an extremely hard instance of a problem may cause the average to come across as still hard. As such we will look at generic complexity as our measure. This will discount outlying difficult problems and give us a better idea of the complexity of the majority of instances. In order to gain confidence in the security of the protocol from the previous chapter, we want to show the complexity of the ideal membership problem is at least exponential. The algorithm for finding Gr ̈obner basis, known as Mora’s algorithm, is an iterative method made up of two main steps during each iteration. The first step is finding new candidates for the basis and adding them to a queue. The second step involves testing the polynomial next in the queue to see if it would be redundant to add to what will become the Gr ̈obner basis.