Fully Homomorphic Encryption and Multilinear Maps

The area of lattice-based cryptography has become one of the most popular branches of post-quantum cryptography to date. One of the reasons for this is that some of the hard problems used in lattice-based cryptography can be proven to be as hard as worst-case instances of well-studied problems in the theory of lattices. Another reason is its versatility with a wide range of primitives, including many high-level primitives such as fully homomorphic encryption, being classed as lattice-based.

Fully homomorphic encryption allows a third party to perform computations on encrypted data and is thus a very powerful tool. Initially, schemes achieving this notion were incredibly inefficient and thus nowhere near practical. Continued improvements in how to construct them have led to practical implementations, however, they are still rather inefficient. One area of inefficiency is that, before being encrypted, the data to be computed on must first be encoded using a technique which is compatible with the computations that one wants to perform. For certain data types, such as real and complex numbers, previously published encoding techniques did not exploit the full extent of the plaintext spaces in popular fully homomorphic encryption schemes. The first results of this thesis are to present more efficient methods for encoding real and complex valued data in this scenario.

The second area this thesis deals with is the recent emergence of a number of cryptographic problems which are closely related to standard ring variants of the learning with errors problem or the NTRU problem. In all cases one can view the new problem as coming from a standard problem in which the ring structure has been modified in some way. This change in the ring structure is not merely cosmetic and can greatly affect the security of the problem.

One of these new problems, the multivariate ring learning with errors problem, promised to offer improved efficiency without losing security when used to construct fully homomorphic encryption schemes and used to compute on multidimensional data. However, we show that for the parameter choices used in the literature, the security of the problem is greatly compromised by a simple evaluation attack.

For the other problems, improving efficiency for a given security level was again a motivating factor. Here, the improved efficiency was claimed due to standard attacks no longer being applicable, however, new attacks quickly appeared which muted these gains in efficiency. In the final part of this thesis, we formally unify these new problems with the standard ones which allows us to formulate three generalised problems: one in the style of the learning with errors problem, one in the style of the short integer solution problem, and one in the style of the NTRU problem. In doing so, we also encounter parameter choices which give rise to novel instances of each problem.

Finally, we proceed to evaluate which of the current strategies to attack these types of problems can be made to work in our more general setting. This turns out to be highly dependent on the choice of parameters with some attacks generalising only to very specific choices while others are more widely applicable.