Cryptanalysis and applications of lattice-based encryption schemes

The work presented in this thesis is focused around the security of the Learning with Errors (LWE) problem, as well as applications of homomorphic encryption schemes. In Chapter 1, we provide an overview of the topics discussed in this thesis: lattice-based cryptography, secure computation, cryptanalysis, and standardisation. In Chapter 2, we introduce necessary background concepts. Specifically, we outline some notions related to lattice-based cryptography and cryptanalysis. In Chapter 3, we consider trade-offs in "Batch Bounded Distance Decoding". We consider guess-and-verify decoding (g-v decoding), a porting of the decoding attack on LWE into the case of small and/or sparse secret vectors. This results in a combinatorial trade-off, where components of the secret vector are guessed before batches of BDD instances are solved in a smaller dimension. This attack technique has similarities with the hybrid latticereduction and meet-in-the-middle (hybrid-decoding) attack, and we compare and contrast these two techniques throughout. We conclude that, under certain assumptions, our g-v decoding technique outperforms a variant of the hybrid-decoding attack. In Chapter 4, we analyse submissions to the NIST standardisation process for post-quantum cryptographic algorithms. Specifically, we consider all parameter sets submitted to the first round, for every lattice-based scheme, as well as the cost models used for lattice reduction. We estimate the security of every parameter set, under every cost model, considering both the uSVP and dual attacks (where appropriate). This allows for individual schemes to be compared more easily. As a result of this analysis, we observe that cost models for the BKZ algorithm are not order preserving. That is, if scheme A is "more secure" than scheme B under cost model 1, the same is not necessarily true under cost model 2. Finally we outline the current state of the NIST standardisation process, and provide some estimates for the schemes which have reached the third round. In Chapter 5, we consider homomorphic encryption-style parameter sets, and explore hybrid attacks. Hybrid attacks are competitive in regimes where the LWE secret is small and/or sparse, so need to be considered for parameter sets used in homomorphic encryption schemes. We consider the effect of secret sparsity on security estimates, and consider the trade-off between bootstrapping complexity and security. Finally, in Chapter 6, we consider an application of homomorphic encryption: "Private Outsourced Kriging Interpolation". Kriging is a spatial interpolation algorithm which has applications in geoscience. We consider the outsourcing of this algorithm using homomorphic encryption, and outline techniques which can be used to protect the sensitive parameters in order to provide an efficient solution.