Search

Public-key cryptography in use today is based on classically hard problems such as factoring or solving discrete logarithms. These problems could be efficiently solved if an adversary had access to a sufficiently large quantum computer. The potential of such a quantum computer therefore represents a threat on current cryptography. The field of post-quantum cryptography aims to mitigate against this threat by proposing schemes based on alternative assumptions that are believed to be hard in both the classical and quantum setting. Lattice-based cryptography has emerged as a promising candidate for post-quantum cryptography. One reason for this is the wealth of applications that are possible, perhaps the most notable of which is Fully Homomorphic Encryption (FHE). This enables computations to be performed on encrypted data, without requiring access to the secret key, and for these computations to correspond to operations on the underlying data in a meaningful way. The Learning with Errors (LWE) problem and its variants, such as LWE with small secret, LWE with binary error, and Ring-LWE, are used as hardness assumptions in many lattice-based schemes. In this thesis we consider parameter selection in cryptosystems based on LWE. We begin with a focus on security by considering the concrete hardness of LWE. We comprehensively review the algorithms that can be used to solve LWE and its variants with a small secret. Turning our attention to an LWE variant where the error distribution is binary, we show there is an additional attack applicable in this setting. In applications, the selection of appropriate parameters is often very challenging due to the conflicting requirements of security, correctness and performance. We highlight this in the application setting of FHE by considering a scheme based on Ring-LWE. In particular, we discuss the selection of parameters in SEAL, an implementation of the scheme by Fan and Vercauteren.